# Can we find a Turing machine such that there is no Turing machine to decide whether it halts on $\epsilon$?

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.
• Well, ok. Then I must ask, can we find a Turing machine to decide if a Turing machine decides $L$ for arbitrary $M$? – oren1 Jan 30 at 5:17