# A Turing machine going to the right by the first $2 |w|$ steps

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.

• Your intuition is valid, but unfortunately your thoughts above do not constitute a proof. Try expressing these ideas as a formal proof. – Yuval Filmus Aug 1 '17 at 23:16
• @YuvalFilmus, I see that it is not formal proof. But, I cannot see what is the weakeast point of my reasoning? – Carol Aug 9 '17 at 8:27
• 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. – Yuval Filmus 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.