Number of inputs in undecidability proof of halting problem

Question

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^+)$?

Answer 1

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.

Answer 2

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.