A Turing machine for which it is impossible to predict whether it halts or not on a fixed input

Question

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?

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