1
$\begingroup$

So first, just to make sure that I understand the proof, here is the proof as I understand it:

Take a program $H(x,y)$, which determines whether $x(y)$ will halt or not halt: if $x(y)$ halts then $H$ returns true, and otherwise it returns false. If $H$ exists, we can construct a new program $H'$ which has one input $x$, defined by $H'(x) = H(x,x)$. Using $H'$ we create a final function $H^+$, which loops forever if $H'$ returns true, and halts otherwise.

With this information, we can feed $H^+$ into itself — $H^+(H^+)$. If the inside halts, then the outside must loop, but due to the definition of $H'$, $H^+(H^+)$ is the same as $H^+(H^+,H^+)$. The outside is the same as the inside, and so must halt. This is a contradiction, so $H(x,y)$ cannot exist.

The thing I find confusing about this, is that it assumes that the interior $H^+$ is the same as the exterior $H^+$, whereas to me it seems that they would be different by virtue of one being the input to the other.

Another question is what is the input for the interior $H^+$? by un-nesting the $H^+$’s, and unrolling the definition of $H'$, we get $H^+(H^+,H^+)$, then $H^+(H^+(H^+))$, then $H^+(H^+(H^+(H^+)))$, and so on, so what is the first input? If there is no input then the question of whether $H^+(H^+)$ halts, that is, whether $H^+$ halts with input $H^+$, makes no sense for the same reason that the question what is the number answer to $x^2$ doesn't make sense – the function requires an input and if the input is just a function, you are asking if a function halts without knowing the input. An example of this is $H^+(x)$, where $x$ is

If input = 1 
    Halt 
Else 
    Loop

Will this program halt? The answer is obviously that it depends on the input, so why is it not the same with the function $H^+(H^+)$?

$\endgroup$
2
  • $\begingroup$ I did my best to make sense of your prose. $\endgroup$ Sep 29, 2021 at 13:57
  • $\begingroup$ Thank you very much. $\endgroup$
    – Mercury
    Sep 29, 2021 at 14:00

2 Answers 2

1
$\begingroup$

First of all, Turing machines have no input specification per se. They have an "input convention" which allows us to interpret them as accepting inputs. However, this makes little difference for the argument, so below I will assume that Turing machines do have a specified number of inputs.

The starting assumption is that there is a two-input Turing machine $H(x,y)$ which return whether the one-input Turing machine encoded by $x$ halts on the input $y$. From it, we construct a one-input Turing machine $H'(x)$ which computes $H(x,x)$. Finally, we construct a one-input Turing machine $H^+(x)$ which computes $H'(x)$, enters an infinite loop if $H'$ returned true, and halts otherwise.

We then consider what happens whether $H^+$ halts when run on $\# H^+$, which is the encoding of $H^+$. There are two possibilities:

  1. Suppose that $H^+$ halts when run on $\# H^+$. Then $H'(\#H^+) = H(\#H^+,\#H^+)=\text{True}$, and so $H^+$ enters an infinite loop when run on $\#H^+$, contradiction.
  2. Suppose that $H^+$ does not halt when run on $\# H^+$. Then $H'(\#H^+) = H(\#H^+,\#H^+)=\text{False}$, and so $H^+$ halts when run on $\#H^+$, contradiction.

In both cases we reach a contradiction, and so we conclude that $H$ cannot exist.

$\endgroup$
18
  • $\begingroup$ Sorry, so are you saying that $#H+$ represents the code of H+? What does that mean exactly? $\endgroup$
    – Mercury
    Sep 29, 2021 at 14:32
  • $\begingroup$ A Turing machine is an abstract concept. In order to present it as input, we first need to encode it somehow, as a string. I denote by $\#T$ the encoding of the Turing machine $T$. $\endgroup$ Sep 29, 2021 at 14:33
  • $\begingroup$ Ok understood. So why when $H+$ when run on $\#H+$ do we get $H′(#H+)=H(#H+,#H+)=True$, surely it should be $H(#H+, #H+)=False$ as H+ does the opposite of H. I dont understand why when you have said that when you run $H+$ on $\#H+$ your line of reason holds true. $\endgroup$
    – Mercury
    Sep 29, 2021 at 14:38
  • 2
    $\begingroup$ "$H^+$ does the opposite of $H$" — right, that's the point of the construction, and the reason that the proof works. $\endgroup$ Sep 29, 2021 at 14:42
  • 1
    $\begingroup$ I'm afraid that your intuition is wrong. We don't assume anything on how $H$ operates. The only assumption is that $H(x,y)$ returns True iff the machine encoded by $x$ halts on input $y$. How $H$ accomplishes it is up to $H$. $\endgroup$ Sep 30, 2021 at 14:30
0
$\begingroup$

Let H (x, y) be a Turing machine that returns true if the Turing machine with encoding x halts on input y, and returns false if that machine doesn't halt on input y. If H (x, y) exists then the halting problem is solved. If H (x, y) doesn't exist then the halting problem cannot be solved.

H' (x) returns true if the Turing machine with encoding x halts on input x, and returns false if the machine doesn't halt on input x.

$H^+$ (x) loops forever if the Turing machine with encoding x halts on input x, and halts if the machine doesn't halt on input x.

Let #$H^+$ be the encoding of the Turing machine $H+$. We try what happens if we use #$H^+$ as the x in the previous part: $H^+$ (#$H^+$) loops forever if the Turing machine with encoding #$H^+$ halts on input #$H^+$, and halts if the machine doesn't halt on input #$H^+$.

In other words, $H^+$ (#$H^+$) loops forever if $H^+$ halts on input #$H^+$, and halts if $H^+$ loops forever on input #$H^+$. $H^+$ (#$H^+$) loops forever if $H^+$ (#$H^+$) halts, and $H^+$ (#$H^+$) halts if $H^+$ (#$H^+$) loops forever.

In the last line, we had one calculation which loops forever if it halts, and halts if it loops forever. That's not possible. Therefore H doesn't exist.

$\endgroup$

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.