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


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 ?

  • $\begingroup$ 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.) $\endgroup$ – Andrej Bauer Nov 3 '20 at 23:12
  • $\begingroup$ sure, please go ahead ... I will change back if I consider that the essence of the question was lost though! $\endgroup$ – C Marius Nov 3 '20 at 23:12
  • $\begingroup$ In the meanwhile, you might find it helpful to watch this excellent video about Halting Problem. $\endgroup$ – Andrej Bauer Nov 3 '20 at 23:13
  • $\begingroup$ I have seen the video already ... I think it glides over the core of my concerns expressed here in this question ... $\endgroup$ – C Marius Nov 3 '20 at 23:15
  • $\begingroup$ @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 ? $\endgroup$ – 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$.

  • $\begingroup$ 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. $\endgroup$ – C Marius Nov 4 '20 at 0:16
  • $\begingroup$ 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$). $\endgroup$ – Andrej Bauer Nov 4 '20 at 9:16
  • $\begingroup$ 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 ? $\endgroup$ – C Marius Nov 4 '20 at 9:42
  • $\begingroup$ $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 ? $\endgroup$ – C Marius Nov 4 '20 at 10:01
  • $\begingroup$ 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. $\endgroup$ – Andrej Bauer Nov 4 '20 at 10:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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