A single-tape Turing machine $M$ has the property that, for every input $w$, during the first $2 |w|$ steps, the head of $M$ moves only right (it does not move left nor stays in place); the machine is also allowed to halt at any moment during these first $2|w|$ steps. Prove that the language of $M$ is in $DTIME(n)$.

Perhaps I don't understand the problem because I don't know how to start. My intuition is following:

$L$ reconized by $M$ is $= K \cup M$ where $K$ is a set of such words $s$ that $|s| < |w|$. $M \cap K = \emptyset$.

We can consider two situation:

1) $M$ stops before $2|w|$ steps. It means that such word $w$ can be represented by regular expression. Therefore, such words can be accepted/rejected in $DTIME$.

2) $M$ stpes $2|w|$ to the right (or more) and now it can come back to the beginning. But, if machine is able to reach $2|w|$ steps without memory it means that $M$ can compute steps in any way. It cannot be "solved" using a tape- the machine cannot move left so the tape is useless. So, the information must be encoded in states. But, number of states is finite. So, let $|Q| = n$.

Then, there is limited number of such words that cannot be recognized using a deterministic automata. The limited language can be recognized in $DTIME$. Other words can be recognized by deterministic automata.

It is my idea. I am not sure if is ok.

1) Is it?

2) Probably there is a better (one-sentence) solution. Please say me.

  • $\begingroup$ Your intuition is valid, but unfortunately your thoughts above do not constitute a proof. Try expressing these ideas as a formal proof. $\endgroup$ Aug 1 '17 at 23:16
  • $\begingroup$ @YuvalFilmus, I see that it is not formal proof. But, I cannot see what is the weakeast point of my reasoning? $\endgroup$
    – Carol
    Aug 9 '17 at 8:27
  • $\begingroup$ The problem is exactly what you said - your argument doesn't constitute a proof. It's not a sequence of logical steps, each following deductively from previous ones. $\endgroup$ Aug 9 '17 at 9:44

Suppose that the Turing machine has $N$ states. We call a state $q$ reachable if for some word $w$ of size at least $N$, when the Turing machine runs on $w$, it finds itself in state $q$ after reading $w$. During the following $N$ steps, the machine must go to the right. If it doesn't halt during these $N$ steps, then some state is repeated, and so the machine never halts. Since we assume that it does always halt, it follows that when the Turing machine is in state $q$ with an empty symbol under the head, it stops within $N$ steps, during which it continues traveling to the right.

The discussion above shows that if $w$ has size at least $N$, then the Turing machine halts within $|w|+N$ steps. This shows that the machine runs in linear time $O(|w|)$, which implies your exercise.

With a bit more work, you can show that the language accepted by the machine is in fact regular. Indeed, if we only consider words of length at least $N$, then we have a machine moving only to the right, so we know that $L(M) \cap \Sigma^N \Sigma^*$ is regular. Since $L(M)$ differs from this language by finitely many words, it follows that $L(M)$ is regular.


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.