Variations of the halting problem

Question

Let $M$ be an arbitrary Turing machine and $w \in \{0, 1\}^{*}$ be a binary string.

The language $\text{HALT} = \{\langle M, w \rangle : M ~\text{halts on input} ~w \}$ is undecidable by the famous diagonalization proof.

But what happens when we either fix the Turing machine $M$ or the input $w$?

Formally, for a fixed $M_{0}$ in the first case and a fixed $w_{0}$ in the second case, are these two languages still undecidable? Is there any dependence on the nature of $M_{0}$ or $w_{0}$?

• $\text{HALT}_{M_{0}} = \{w : M_{0} ~\text{halts on input} ~w \}$

• $\text{HALT}_{w_{0}} = \{\langle M \rangle : M ~\text{halts on input $w_{0}$} \}$

For the first language, I found a proof online (Proposition 17.2), but it seems specific to the nature of $M_{0}$ which is probably intuitive. I am more intrigued by the second case.

Answer 1

Whether $\mathsf{HALT}_{M_0}$ is decidable or not depends on $M_0$. For example, if $M_0$ always halts, the $\mathsf{HALT}_{M_0}$ is trivially decidable, whereas if $M_0$ interprets its input as a Turing machine $M$ which it runs on the empty input, then $\mathsf{HALT}_{M_0} = \mathsf{HALT}_\epsilon$ is undecidable (see below).

The language $\mathsf{HALT}_{w_0}$ is always undecidable, as a simple diagonalization shows. Suppose that $M$ could solve $\mathsf{HALT}_{w_0}$. Using the recursion theorem, one can construct a machine $M'$ which acts as follows:

• Run $M$ on $M'$. If $M$ returns YES, go into an infinite loop, otherwise halt.

Notably, $M'$ doesn't depend on its input. Considering what happens when it is run on $w_0$, we reach a contradiction just as in the standard proof of undecidability of the halting problem.