# Variations of the halting problem

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.

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.