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.