The halting problem is undecidable, i.e. $\not \exists$ $M$ Turing machine s.t. for every $(M_0,w_0)$ input where $M$ is the description of a Turing machine and $w_0$ is an input word, the output of $M$ is "$1$" if $M_0$ will halt on $w_0$ and "$0$" if it will not.

From this statement only, it does not follow that there must be an ($M_0,w_0$) pair for which it is impossible to predict if $M_0(w_0)$ halts or not. It only means there is no general way to decide this question for all ($M_0,w_0$) pairs.

So my question is the following: Does there exist a ($M_0,w_0$) pair for which it is known that it is impossible to predict whether $M_0(w_0$) halts or not? If yes, is there a known example or construction for an ($M_0,w_0$) pair such that?

  • 1
    $\begingroup$ What do you mean by "impossible to predict"? $\endgroup$ Commented Apr 3, 2020 at 22:22
  • 2
    $\begingroup$ Here is one suggestion: you want an example of a Turing machine for which it cannot be proved (in some fixed proof system) that the machine halts, and also it cannot be proved that the machine doesn’t halt. $\endgroup$ Commented Apr 3, 2020 at 22:50
  • 3
    $\begingroup$ I don’t think we’re making any progress here. $\endgroup$ Commented Apr 3, 2020 at 22:55
  • 2
    $\begingroup$ The halting problem says no one machine can decide weather every given input pair halts or not. It seem's you're asking is there one input for which no machine, when run on that input, halts and accepts IFF the input pair halts. There is no such input for a trivial reason. A given input pair either halts or loops. If it halts the machine that accepts all inputs "makes the correct prediction" (if you can call it that). If it loops the machine that always rejects suffices.. $\endgroup$
    – Jake
    Commented Apr 3, 2020 at 23:20
  • 2
    $\begingroup$ @YuvalFilmus: I think it would be worth writing an answer in which you make the two points you made in the comments, namely that (1) for any specific machine $M$ and input $w$ there is a machine $T$ which "decides" whether $M(w)$ halts, but we can't compute $T$ from $M$ and $w$, and (2) for any formal system $F$ within which we want to carry out proofs about machines there exists a machine $M$ such that halting of $M$ is undecidable in $F$ (and we can compute $M$ from $F$. It's really the best answer the OP can get, given the question. $\endgroup$ Commented Jan 23 at 12:09

1 Answer 1


For any specific machine $M_0$ and input $w_0$, there is a machine that decides whether $M_0$ halts on $w_0$. Indeed, one of the following machines works:

  • The machine that outputs "Yes".
  • The machine that outputs "No".

However, there is no program $P$ that given arbitrary $M$ and $w$ produces a machine $T_{M,w}$ that correctly decides whether $M$ halts on $w$, since such a program can be used to solve the halting problem. Indeed, given $M$ and $w$, run $P$ on the input $\langle M,w \rangle$, and then run the machine $T_{M,w}$ that $P$ outputs.

We can go further, and for every reasonable proof system $\Pi$ (one for which Gödel's incompleteness theorems apply) which is sound and consistent, we can construct a machine $M_\Pi$, accepting no input, such that $\Pi$ cannot "decide" whether $M_\Pi$ halts, in the sense that there is neither proof that $M_\Pi$ halts nor a proof that it doesn't halt. The machine $M_\Pi$ simply enumerates all proofs in $\Pi$, halting if there is a $\Pi$-proof of contradiction. Since $\Pi$ is consistent, $M_\Pi$ doesn't halt, and so, since $\Pi$ is sound, it cannot prove that $M_\Pi$ halts. On the other hand, $\Pi$ cannot prove that $M_\Pi$ doesn't halt, since this contradicts Gödel's second incompleteness theorem.

(I hope that I got this proof right — mathematical logic is often quite confusing.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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