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

cs.stackexchange https://cs.stackexchange.com/questions/120071

  •  28-09-2020
  •  | 
  •  

Question

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$?

Was it helpful?

Solution

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.

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top