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$?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
6
  • $\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, 2017 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, 2017 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$
    – user35837
    Apr 25, 2017 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, 2017 at 18:47
  • $\begingroup$ incredibly... what? $\endgroup$
    – Ben I.
    Apr 25, 2017 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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Wait, aren't $g$ and $\mathtt{g}$ the same program? $\endgroup$
    – Ben I.
    Apr 25, 2017 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, 2017 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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