# Is it decidable whether a Turing machine will ever leave the start state on any input?

Is $L=\{ M | M\text{ leaves the start state on every input}\}$ decidable?

I have an intuition that the following language is undecidable, since the complement $L^C$ seems to not be recursively enumerable. Some TM might remain on the start state for $k$ steps, but then leave at $k+1$ steps, so we can't get a definitive answer whether it will ever leave the start state.

What known non-decidable TM can be reduced to A to show that a contradiction arises?

• In any case, consider what the computation can do if it stays in the start state -- the answer is, "not a lot". You can, as I recall, make a universal Turing machine with just two states; but you can't with only one. – David Richerby Nov 29 '16 at 0:51
• @DavidRicherby on any input. I know this question was answered for a blank tape already. For instance, A three state TM (start, accept reject) could move to accept when it reads "a", move to reject when it reads "b" and remain on the start state while moving the tape head to the right on any other character read. So on input "ddddffffa" would leave the start state eventually, but not on input "fffffffff". Therefore this TM would not be accepted by A. – Robin Nov 29 '16 at 1:10

Firstly, let your alphabet be $\Sigma$, including the empty symbol. I claim that unless you have in the transition function $(s_0, x) \to (s_i, \dots)$ for every $x \in \Sigma$ and $i \neq 0$ your machine is not the desired one. Why this is true? Suppose there is such $x$ for which TM doesn't change the initial state. Fill the tape with all these $x$'s. Done.
• What if the TM moves the tape head to the right on any non-empty symbol while staying in the start state, and once it reaches an empty symbol under the tape head moves to the second state. Then this TM would recognize every input it receives, but the transition function from s0 to s1 would only have a single transition, namely$(s_0, \epsilon)\rightarrow s_1$? – Robin Nov 29 '16 at 4:15