2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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