# Faults in the halting problem reasoning

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 ?

• Your transcription of the proof has several errors. It confuses $A_0$, $A_1$ and $A_2$ in several places. Would you like me to fix it? (I would start by not calling these $A_0$, $A_1$ and $A_2$, as that is quite unreadable.) – Andrej Bauer Nov 3 '20 at 23:12
• sure, please go ahead ... I will change back if I consider that the essence of the question was lost though! – C Marius Nov 3 '20 at 23:12
• In the meanwhile, you might find it helpful to watch this excellent video about Halting Problem. – Andrej Bauer Nov 3 '20 at 23:13
• I have seen the video already ... I think it glides over the core of my concerns expressed here in this question ... – C Marius Nov 3 '20 at 23:15
• @andrejBauer I do not think I confused $A_0, A_1, A_2$ anywhere though ... and $A$ stands for algorithm. Why you think is unreadable ? – C Marius Nov 3 '20 at 23:17

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

• would you agree with defining the oracle $H$ as $H(M(I)) \in \{ YES, NO\}$ with obvious choice of yes and no ? Then $X(I) = N(H(I(I)))$ and $X(X) = N(H(X(X)))$ through definition. – C Marius Nov 4 '20 at 0:16
• I would not. The halting oracle takes two inputs: a machine and the input to be fed to the machine, and you need to explain what $H$ does withour referring to $H$ (because you are trying to define $H$). But you are suggesting that we should define what $H$ does on input $(M,I)$ by saying that it does $H(M(I))$ - this is not a valid definition because you referred to $H$. And also, $H(M(I))$ is wrong because $H$ takes two inputs, but "$M(I)$" is just a single input (namely the output of $M$ when run with intput $I$). – Andrej Bauer Nov 4 '20 at 9:16
• ok but why wouldn't you agree that for any halting oracle $H: \{machines\} \times \{ inputs\} \to \{Y,N\}$ you can consider a function $\bar{H}: \{ machines\} \to \{Y,N\}$. Since $M(I)$ is a machine still, we define $\bar{H}(M(I)) = H(M,I)$ (for those other machines $M^{0}$, which can not written as $M(I)$ consider $M^{0} = M^{0}(\emptyset)$ ) Now I wonder if $H(M, \emptyset)$ is defined actually ? – C Marius Nov 4 '20 at 9:42
• $H(M, \emptyset)$ is actually trivial to define $H(M,\emptyset) = YES$ if $M$ halts and $H(M, \emptyset) = NO$ if it doesn't. I have therefore "converted" your definition of oracle to mine, haven't I ? – C Marius Nov 4 '20 at 10:01
• When you write $H(M(I))$ that does not make sense. You must write $H(M,I)$. When you write $\emptyset$ as input, you are confusing the type of input and its value, so $H(M, \emptyset)$ makes no sense. What does it mean that the input to a machine is the empty set? It has to be something written on a tape. – Andrej Bauer Nov 4 '20 at 10:43