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

oren1

Posted 2020-01-28T22:05:50.747

Reputation: 45

You might want to take a look at How can it be decidable whether π has some sequence of digits?

– Aaron Rotenberg – 2020-01-29T03:25:17.530

Hang on a minute, what does $0^n$ mean in the definition of $L_M$? – Rick Decker – 2020-01-30T16:46:50.637

A string of zeros of length $n$ – oren1 – 2020-01-31T07:31:04.373

Answers

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.

Rick Decker

Posted 2020-01-28T22:05:50.747

Reputation: 14 063

Well, ok. Then I must ask, can we find a Turing machine to decide if a Turing machine decides $L$ for arbitrary $M$? – oren1 – 2020-01-30T05:17:16.610

1@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. – Rick Decker – 2020-01-30T16:49:56.863