A one-tape Turing machine which operates in linear time can only recognize a regular language

Question

Show that A one-tape Turing machine which operates in linear time can only recognize a regular language

I have no idea how to solve it. Can you give me show how to solve it ? I am beginner at this subject so I ask for an indulgence.

Answer 1

The proof is not straightforward. This article Theory of one-tape linear-time Turing machines describes how it was proved. I quote them here :

Hennie [18] made the first major contribution to the theory of one-tape linear-time Turing machines in the mid 1960s. He demonstrated that no one-tape linear-time deterministic Turing machine can be more powerful than deterministic finite state automata. To prove his result, Hennie described the behaviors of a Turing machine in terms of the sequential changes of the machine’s internal states at the time when the tape head crosses a boundary of two adjacent tape cells. Such a sequence of state changes is known as a crossing sequence generated at this boundary. Using this technical tool, he argued that (i) any one-tape linear-time deterministic Turing machine has short crossing sequences at every boundary and (ii) if any crossing sequence of the machine is short, then this machine recognizes only a regular language. Using the non-regularity measure of Dwork and Stockmeyer [13], the second claim asserts that any language accepted by a machine with short crossing sequences has constantly-bounded non-regularity. Extending Hennie’s argument, Kobayashi [25] later showed that any language recognized by one-tape o(n log n)-time deterministic Turing machines should be regular as well. This time bound o(n log n) is actually optimal since certain one-tape O(n log n)-time deterministic Turing machines can recognize non-regular languages.