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?

  • $\begingroup$ 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. $\endgroup$ – David Richerby Nov 29 '16 at 0:51
  • $\begingroup$ @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. $\endgroup$ – Robin Nov 29 '16 at 1:10

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.

  • $\begingroup$ 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$? $\endgroup$ – Robin Nov 29 '16 at 4:15
  • $\begingroup$ We should be very careful here what do you mean by the input. If I am allowed to have a tape without empty symbols then machine you wrote won't recognize this kind of tape. Are you restricted to only finite non empty segments of the tape? $\endgroup$ – Eugene Nov 29 '16 at 4:34
  • 1
    $\begingroup$ The tape of a Turing Machine is an infinite amount of empty cells (they contain nothing, i.e. the empty symbol), and the tape head initially points to the first cell on the tape. When running the Machine on some input w of size k, the first k cells of the tape will be filled by the characters that compose w, and the machine will start running. So a tape must contain the empty symbol, since it is infinite and initially empty. $\endgroup$ – Robin Nov 29 '16 at 5:05
  • $\begingroup$ I see the flaw here, if you say the input is only bounded. Still I'd say that for all inputs that's a pretty strong condition so my intuition tells it is decidable. Even if you play tricks like using symbols on the tape for different moves so machine actually loops in some intricate way, there should be an input which breaks the logic. Still not sure. $\endgroup$ – Eugene Nov 30 '16 at 3:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.