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?
Is it decidable whether a Turing machine will ever leave the start state on any input?
turing machines;reductions;undecidability
I would say decidable. Here is the idea.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.Here I had the assumption that we can have any initial tape as we want. If you consider only finite non empty input the problem becomes much harder.