I fail to see a contradiction in the halting machine proposed by Alan Turing.

Definition of halting machine
H = all possible programs that terminates
N = all possible programs that do not terminate
$N_p$ = a program that does not terminate e.g.while True do x:=0
T = true
F = false
if a program outputs T or F then it also means that the program terminates
f is a program
h(f) is the halting machine
n(x) is the negator
\begin{equation*} h(f) = \begin{cases} T & \text{if } f \subset H \\ F & \text{if } f \subset N \end{cases} \quad \end{equation*}

\begin{equation*} n(x) = \begin{cases} N_p & \text{if } x = T \\ F & \text{if } x = F \end{cases} \quad \end{equation*}

\begin{equation} \begin{aligned} nh(f) &= n(h(f)) \\ & = \begin{cases} N_p & \text{if } f \subset H \\ F & \text{if } f \subset N \end{cases} \quad \end{aligned} \end{equation}

[$nh_0, nh_1, nh_2$ are all the same program as $nh$]
Showing contradiction - finding output of $nh_2(nh_1(nh_0))$

\begin{equation} nh_2(nh_1(nh_0))= n_2(h_2(n_1(h_1(nh_0)))) \end{equation}
[Step by step execution of $n_2(h_2(n_1(h_1(nh_0))))$]
let $nh_0 \subset N$ [we make an assumption that $nh_0$ do not halt]
$h_1(N)=>F \equiv h_1(nh_0)=>F$
$h_2(F)=>T \equiv h_2(nh_1)=>T$
Alan Turing's argument
$nh_0$ and $nh_1$ is the same program, therefore output of the halting machine should be the same when the programs are passed in as an input but they contradict, therefore halting machine can not be made.
\begin{equation} nh_0 \equiv nh_1 \\ h_1 \equiv h_2\\ \therefore h_1(nh_0) = h_2(nh_1)\\ \text{However, } h_1(nh_0)=F \text{ and }h_2(nh_1)=T\\ \therefore \text{logical contridiction and thus halting machine can not exist} \end{equation}
Objecting Alan Turing's argument
$h_1(nh_0)$ and $h_2(nh_1)$ gives different output not because halting machine can not exist but because $nh_0$ and $nh_1$ are not the same.
$nh_0$ and $nh_1$ is the same program, but in this case they are receiving different input, therefore they represent a different thing.
The halting machine gives different output for the same program because they are analyzing different part of the same function.
h(if(f==H)Then func1 else func2) $\equiv$ if(f==H)Then h(func1) else h(func2))
I think this idea is backed up by Professor Eric C.R. Hehner's paper - Reconstructing the Halting Problem and Problems with the Halting Problem.
To summarize my question.

  1. Is my understanding of Alan Turing's take on halting problem correct?
  2. Is my objection to Alan Turing's idea correct?
  3. Is Professor Eric C.R. Hehner's objection and my objection agreeing / the same thing?
  • $\begingroup$ I apologize in advance that my description is very informal and is technically incorrect way of representing my idea. e.g. I treated "machines" as a function. This is something that I couldn't get my head around ever since my high school computer science and have not pursued the field ever since so I would appreciate if someone could edit my question to make it more formal. $\endgroup$ Aug 12, 2018 at 20:26
  • $\begingroup$ I understand that this is a big and time consuming question. So I would appreciate any comment of opinion on any part of the question. $\endgroup$ Aug 12, 2018 at 20:41
  • $\begingroup$ I suggest taking a look at some of the other questions which contain objections to this proof. For example, this one. There are many others, and it is highly likely that your objection is covered by one of them. $\endgroup$ Aug 12, 2018 at 21:40
  • 14
    $\begingroup$ The proof you give isn't Turing's: it's your own retelling of Turing's proof. You think you've found a hole in your version of the proof and you're blaming Turing for it. That hardly seems fair. If you want to convince people that Turing's proof is wrong, you need to find an error in his work, not in yours. $\endgroup$ Aug 13, 2018 at 15:39
  • $\begingroup$ Please note that I have nothing personal against Alan Turing. The question here is intended to clear what I find ambiguous area of the proof and gain better understanding. I appreciate your opinion but I would appreciate a more specific argument. e.g. your idea is different from Turing's in such and such ways. I understand that this is a controversial topic as stated in the conclusion of "Problems with the Halting Problem". $\endgroup$ Aug 13, 2018 at 16:02

1 Answer 1


Alan Turing's proof of incomputability(the Original Proof) is presented in the last paragraph in this paper that is cited by OP. A sketch of the proof (Wikipedia Proof) at wikipedia are more or less the same as as the original proof. I will assume that OP is talking about (some version of) the Original Proof or the Wikipedia Proof. Either proof should fit for OP's question and this answer, although the latter one might be easier for us modern readers.

"1. Is my understanding of Alan Turing's take on halting problem correct?"
"2. Is my objection to Alan Turing's idea correct?"

I doubt.

In fact, it is not easy for me to understand your symbols and logic unambiguously. For example, is $N$ in your exposition a set of programs or just a single specific program or either one depending on which line(or context) it appears? For example, you have not introduced $h_0$ before using it. For example, you are using "$\Rightarrow$" (or its not-formatter form "=>") to mean output, while all (modern) textbooks on logic or computer science or mathematics (that I know) use that symbol to mean implication. For example, I fail to see exactly why you choose to use $\equiv$ in some occasion and $=$ in other occasions(although I did have some clue).

Your objection to Alan Turing's argument seems to be resting on the statement "The halting machine gives different output for the same function because they are analyzing different part of the same function". That statement alone makes it hard for me to believe you understand fully Alan Turing's construction and argument. By the rigorous definition of the (imaginary) halting machine, it must have the same well-defined output every time when it is given the same well-defined input, no matter what else may happen. To ensure that the halting machine is getting exactly the same well-defined input, Turing employs his well-defined mapping from machines (or programs as you call them) (or algorithms as we may call) (that have been defined precisely by Turing for purpose thereof and much beyond) to natural numbers.

So I have to wonder and I could not understand that you believe "The halting machine ... are analyzing different part of the same function" and "The halting machines are both receiving representation of the same program as an input but they are representation of same program with different parameter." Let me state again. The input to the halting machine used in Turing's proof is the same (although imaginary) program (with the same parameter, if one considers some part of it as its parameter). There has been one specific and concise description of that input.

In fact, I would venture to say that you miss one simple point of the Original Proof or the Wikipedia Proof or, simply, the proof of concept at wikipedia. However, I cannot find which simple point you missed. I have failed to actually fully understand your notation and semantics after many attempts (which, you can say, render (part of) my answer useless). Well, I welcome other answers that can claim to understand your approach and logic. I do claim that I understand professor Eric's objection to the Original Proof (and some of his later work on "Objective and Subjective Specification")

I recommend strongly that you find some knowledgeable guy around you (or remotely) to have an interactive discussion, perhaps learning a bit of rigorous logic and notations. That is the best reasonable answer to your question I believe. Or you can try reading some popular textbooks beyond "my high school computer science". ( I did several). Or, as Yuval Filmus suggested, (if you have not), try taking a look at some of the other questions on this site or on the web which contain (discussion on or) objections to Turing's proof. (I did). By the way, sorry if I sound insincere, but do you believe that you are able to explain the Original Proof to any fellow round you (or to yourself)? I would also suggest that you raise a new question instead of updating this one after you have followed my advice seriously.

"3. Is Professor Eric C.R. Hehner's objection and my objection agreeing / the same thing?"

I would not believe that. Note that it takes quite some writing effort for Professor Eric C.R. Hehner (even in his second paper where he presents "a drastically shortened version" of his first paper) to explain his proposition that because of a logic gap, Alan Turing's famous reasoning on halting problem does not prove the incomputability of the halting problem.

Profess Eric argues that the halting machine constructed by Turing is logically inconsistent in the same way as (or in a similar way to) Bertrand Russell's definition of a barber. That inconsistency exists before we even have the notion of incomputability. That inconsistency exists both with and without the concept of incomputability. Hence Turing's argument does not prove the incomputability of the halting problem. He does not object that the input to the halting machine is unique. He does notice or emphasize that that there is some logic inconsistency about that input (which is sort of the halting machine itself).

On the other hand, apparently, regardless of how you have been reasoning, you are trying to show that there is actually no (real or unresolvable) inconsistency in the specification or the behavior of the halting machine. That is very different from Eric's view. That is exactly the opposite of Eric's clear belief in the (immediate) inconsistency of the halting machine. Neither could I see the possibility that Eric's argument and your argument is just two different sides of the same coin (that is, the same perspective or the same argument but described differently).

To readers with more formal logic and computer science background, please excuse me that I am not writing in rigorous formal logic. That would not be necessarily more helpful here, anyway. Indeed, if needed, we can just read Eric's wonderful papers.

  • $\begingroup$ I first thank you for a very constructive answer. I appreciate your suggestion on more ambiguous definitions and I made some changes regarding it. I also appreciate your advice on doing more further reading around the topic $\endgroup$ Aug 13, 2018 at 13:25
  • $\begingroup$ To clarify my argument on "You objection to Alan Turing's argument...." part. I agree that (imaginary) halting machine should give the same output for the same input. However, my argument here is that though it appears as if the halting machine is relieving the same input they are actually different inputs. The halting machines are both receiving representation of the same program as an input but they are representation of same program with different parameter. Therefore you have two different outputs with two different inputs, which does not result in a contradiction. $\endgroup$ Aug 13, 2018 at 13:36
  • $\begingroup$ Even though I am highly thankful for your opinion on question 3. I must say that only argument being made here is that Professor Eric C.R. Hehner's paper contains longer description than my description. Though, this may be true I would like you to bring your attention to page 1 and 2 of "Problems with the Halting Problem", the second paper. Where there is a very consist arguments being made on the halting problem $\endgroup$ Aug 13, 2018 at 13:39
  • $\begingroup$ @WantingtobeanAndroidDevelor, it is fair enough to say that the only argument in my answer was Eric's paper is longer. I just updated my answer. $\endgroup$
    – John L.
    Aug 14, 2018 at 20:25

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.