1
$\begingroup$

The Halting problem proof can be seen as the following programs:

  1. Ends(P, I) is a program that detects (returns true or false) if the program P will halt or not with the input I

  2. Diag( P ): is a program that

    2.1 Halts if P( P ) doesn't halt

    2.2 Doesn't halt if P (P) halts

If we use (2) with input Diag it state:

  1. Diag(Diag) halts if Diag(Diag) doesn't halt
  2. Diag(Diag) doesn't halt if Diag(Diag) doesn't halt

Which by contradiction is proven that the program Ends can't exist.

Until here everything is fine. But What if instead of thinking on halt or never halt, we think in steps.

What if I do the following analogy:

  1. Ends( P, I, S ) is a program that detects (returns true or false) if the program P with the input I, it will halt in less or equal S steps.

  2. Diag( P, S) = Diag( P ): is a program that:

    2.1 That halts in less or equal than S steps if Ends( P, P, S ) doesn't halts in less or equal than S steps.

    2.2 That doesn't halts in less or equals than S steps if Ends( P, P, S ) halts in less or equal than S steps.

if we use (2):

  1. Diag( Diag) halts in less or equal than S steps if Ends( Diag, Diag, S ) doesn't halt in less or equal than S steps.

  2. Diag ( Diag ) doesn't halt in less or equals than S steps if Ends( Diag, Diag, S ) halt in less or equal than S steps.

Which is the almost the same contradiction, and in this case Ends is possible to build.

What I'm doing wrong?

Improve this question
$\endgroup$
1
$\begingroup$

The main problem with your analogy is the construction of Diag. The usual proof goes as follow:

  1. Assume Ends exists.
  2. Then we can construct Diag with a Turing machine calling Ends. As follows:

Diag(P) = If Ends(P,P) then Loop indefinitely Else Terminates.

  1. This leads to a contradiction thus Ends does not exist.

What you are doing is the following:

1'. Construct Ends(P,I,S).

2'. Construct Diag(P,S).

3'. This leads to a contradiction.

The main problem is that you do not provide the actual construction of Diag in step 2' as we did it in step 2. How can you implement Diag with a TM machine calling Ends? I do not think so as you need more than S steps to run the program Ends.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Diag can be build 1st. You don't need to run a number of steps in P to realise if is going to iterate more than S steps. 2nd Ends is less or equal, so you don't need S steps!. What you said though is important because that is something that I'm trying to prove with Turing proof. Because what you said with infinitive is tricky but with S steps is not. Another way to do Diag is that it can be a hook to the interpreter and when the number of steps is done it returns the answer. But you can't do it with infinitely is there where I think that exist the bug in Turing proof or I am missing something. $\endgroup$
    – titusfx
    Jan 4 '18 at 20:11
  • 1
    $\begingroup$ I do not really understand how you want to implement Diag. Try to write the pseudo code for it and you may realize that it is not possible. In your 2.1, to know that Ends(P,P,S) is true, you may need exactly S steps thus how can you make Diag halts in less or equal than S steps if Ends(P,P,S) is false? Even with a "hook", you will need an extra step to stop Diag after having simulated P, so you will end up with S+1 steps. $\endgroup$
    – holf
    Jan 5 '18 at 0:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.