Problem Detail: Is $L={ M | Mtext{ 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?
Asked By : Robin
Answered By : Eugene
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/66627 Ask a Question Download Related Notes/Documents
