1
$\begingroup$

Here is my Halting Problem proof, that largely mirrors other (non-diagonalizing) proofs that I've seen.

  1. $H(p,i)$ returns $1$ if program $p$ halts on input $i$.
  2. $H(p,i)$ returns $0$ if program $p$ does not halt on input $i$.
  3. Let $f(t,t)$ be an interface for any program that returns a $0$ or a $1$.
  4. $g(x)$ is $0$ if $f(x,x)$ is $0$, infinite loop if $f(x,x)$ is $1$

  5. Now use $H$ in place of $f$:

4b. (modified) $g(x)$ is $0$ if $H(x,x)$ is $0$, infinite loop if $H(x,x)$ is $1$

  1. Run $g(g(i))$ which runs $H(g(i),g(i))$ If $H(i,i)=0$, then $g(i) = 0$ If $H(i,i)=1$, then $g(i)$ is undefined
  2. If $g$ halts, then $H(g(i),g(i))$ must return $1$ (line 1).

    But then $g$ won't halt. (line 4b)

  3. If $g$ doesn’t halt, then $H(g,g)$ must return $0$ (line 2).

    But if $H(g(i),g(i))$ is $0$, then $g$ halts. (line 4b)

My issue is with $g(g(i))$. I understand that the idea of the proof is to feed the machine into itself, but what, exactly, is the contents of the $i$?

$\endgroup$
1
$\begingroup$

It is an unspecified input. Halting program proofs show that, for any given program that one claims can solve the halting problem, there exists an input for which it does not. The proofs typically do not try to find what that input actually is, merely to prove that one must exist.

$\endgroup$
  • $\begingroup$ So is it safe to say, then, that is is unrelated to the $i$ in lines 1 and 2, and could be more clear, then, as a different letter? $\endgroup$ – Ben I. Apr 25 '17 at 17:17
  • $\begingroup$ You could say so. Personally I find the idiomatic idea of i being "some arbitrary input" to be reasonable, but you are correct that you could change it to j if you felt it was causing confusion. $\endgroup$ – Cort Ammon Apr 25 '17 at 17:22
  • $\begingroup$ @ Cort Ammon Sorry I did not get what do you mean by " The proofs typically do not try to find what that input actually is, merely to prove that one must exist " To me it appears that it depends we are trying to come up with an input ( i.e. Turing machines encoding as an input) for which Turing machine does not halt . $\endgroup$ – aaag Apr 25 '17 at 17:55
  • $\begingroup$ @ShivDuttSharma You can't actually find an input for which the Turing machine doesn't halt unless you specify the Turing machine. Even then, it's easy to create programs for which it is incredibly find a counterexample which proves that they don't solve the halting problem. Instead, what you show is that, for any given program that claims to solve the halting problem there must be an input with a particular set of properties, and you can use those properties to show that the program does not actually solve the halting problem. $\endgroup$ – Cort Ammon Apr 25 '17 at 18:47
  • $\begingroup$ incredibly... what? $\endgroup$ – Ben I. Apr 25 '17 at 18:55
1
$\begingroup$

In $g(\mathtt{g})$, $\mathtt{g}$ is an encoding of $g$ as a program. As such, it needs no concrete arguments.

As it happens, the proof shows that not all functions that can be defined can be encoded as programs. In this particular case, while $g$ exists, $\mathtt{g}$ does not.

$\endgroup$
  • $\begingroup$ Wait, aren't $g$ and $\mathtt{g}$ the same program? $\endgroup$ – Ben I. Apr 25 '17 at 17:16
  • $\begingroup$ Hipothetically, yes. The proof shows that the encoding cannot exist for that function, though. The function is not computable. $\endgroup$ – André Souza Lemos Apr 25 '17 at 17:19

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.