Faults in the halting problem reasoning

Question

I find very interesting the problem of existence of a machine $H$ which given as input any algorithm $P$ outputs whether $P$ halts or not. Alan Turing disproved the existence of such an $H$ machine in the following way:

"Assume $H$ exists. The input of $H$ is any algorithm $P$. The output of $H$ is $YES$ if $P$ halts and $NO$ if $P$ doesn't. Create another machine $N$ with input in the set $\{YES,NO\}$ and without output. The machine $N$ does this: if the input is $YES \to \text{loop for ever}$ otherwise, if input is $NO \to \text{halt}$. Let us call the composition of $H$ followed by $N$ as $X$. We will simply write $X(P) = N(H(P))$. Now $X$ has as input a machine and no output (it either halts or loops forever). What Turing does is to "feed" $X$ with itself ... and reason as follows: if $X(X)$ halts then $X(X) = N(H(X)) = N(YES) = \text{loops for ever}$ from which somehow the contradiction arises ..." but here one should assume (in order to obtain a contradiction) that $X(X) = X$ ...

Question

I do not know why such an assumption, $X = X(X)$ would be made. In fact, in my opinion, $X \neq X(X)$ for any input $P$ (that is all Turing is proving actually). Indeed assume $P$ is a machine which halts (runs for ever). Then $X(P)$ does not halt (does halt) when $X(X(P))$ does (does not). I do not understand therefore, why $H$ cannot exist! Where is my mistake ?

Answer 1

The proof you wrote in the question is faulty, because it uses the wrong definition of the Halting oracle. You tried to fix the proof by inserting the assumption $X(X) = X$, but that is not the way to do it. Here is the correct proof.

Definition: A halting oracle is a machine $H$ which takes as input a pair $(M,I)$ where $M$ is the (description of) a machine and $I$ an input. $H$ always halts and outputs:

• "yes" if $M(I)$ halts,
• "no" if $M(I)$ does not halt.

Theorem: A halting oracle does not exist.

Proof. Suppose $H$ exists. We shall derive a contradiction.

Let $N$ be a machine which does the following upon receiving an input $I$:

• if $I$ is "yes" then $N$ loops forever,
• otherwise $N$ halts.

Let $X$ be the machine which takes an input $I$ and then acts as $N(H(I, I))$. We now prove two contradictory facts:

1. $X(X)$ does not halt.
2. $X(X)$ halts.

To prove the first claim, suppose $X(X)$ halts. Then $H(X,X)$ outputs "yes", therefore $X(X) = N(H(X,X)) = N(\text{yes})$, but $N(\text{yes})$ does not halt. Therefore it is not true that $X(X)$ halts.

To prove the second claim, suppose $X(X)$ does not halt. Then $H(X,X)$ outputs "no", therefore $X(X) = N(H(X,X)) = N(\text{no})$, but $N(\text{no})$ halts. Therefore it is not true that $X(X)$ does not halt, so it halts. $\Box$.