The halting problem states that there is no Turing machine that can determine whether an arbitrary Turing machine halts on $\epsilon$. But I try to ask something different, can we find a specific Turing machine $M$ such that $L_M=\{ 0^n : M$ halts on $\epsilon \}$ is undecidable? Or at least can we prove there exists such $M$?

The language itself isn't the issue, it is either $L=\{0^n : n \in \mathbb{N} \}$ or $L=\phi$ and the way to distinguish the cases is only by the right side of the definition of $L$.

In other words, can we define a Turing machine such that we (or a Turing machine) can't determine whether it halts or not on $\epsilon$?


Suppose you had such a TM, namely a machine $M$ for which the problem was "Does $M$ halt on empty input?" Certainly that problem would be decidable: one of two algorithms must be correct, (1) Answer "yes" or (2) Answer "no". The fact that we might not know which one is the correct algorithm is immaterial here; the only thing that matters is that we're sure one of the algorithms is the right one, so we know the problem is decidable. In more general terms, any decision problem with a finite number of instances is decidable.

  • $\begingroup$ Well, ok. Then I must ask, can we find a Turing machine to decide if a Turing machine decides $L$ for arbitrary $M$? $\endgroup$ – oren1 Jan 30 at 5:17
  • 1
    $\begingroup$ @oren1 For a given specific TM, yes, as I explained above; for an arbitrary TM, no, since that's just the blank tape halting problem, which we know is undecidable. $\endgroup$ – Rick Decker Jan 30 at 16:49

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.