# Does there exist a Turing-machine that runs in time $o(n\log n)$, but not $O(n)$?

It is known that any (deterministic, single-taped) Turing-machine that runs in time $o(n\log n)$, decides a regular language (e.g., see this link). Thus, there exists an equivalent Turing-machine that runs in time $O(n)$. In other words, if $t(n)=o(n\log n)$ then $$\mathsf{DTIME}\left(t\left(n\right)\right)\backslash\mathsf{DTIME}\left(n\right)=\emptyset.$$

I was wondering whether there exists an example in which the original Turing-machine was not already running in time $O(n)$.

To sum up: Does there exist a Turing-machine that runs in time $o(n\log n)$, but not $O(n)$?

• You can make a Turing machine run in $O(n \log \log n)$ if you'd like to. However, do you need it to decide a regular language? – Pål GD Jun 4 '17 at 13:33
• @PålGD Sure, that's trivial. Do you mean $\Theta(n\log\log n)$? And is it a single-tape machine? – David Richerby Jun 4 '17 at 15:59