# $DTIME_1(o(n^2))\setminus$ REGULAR

Maybe this is well-known, but I couldn't find any example of a non-regular lanugage that is decidable on a single-tape Turing machine in subquadratic time. Help!

Related paper: On the structure of one-tape nondeterministic turing machine time hierarchy by Kobayashi.

Related question: Why do we use single tape Turing machines for time complexity? by Kaveh.

• Also note that for one tape TMs $DTIME( o(n \log n)) \subseteq REG$ so there is no hope to find a non regular language that is not "hooked" in some manner to the length of the input. – Marzio De Biasi Feb 19 at 16:09

For example, I think you can decide if $$\lfloor\log_2|w|\rfloor$$ is even in time $$O(n\log n)$$: you first overwrite the input string with all 1s, and then do $$\log n$$ passes over the string where you turn every other 1 into a 0 (while skipping 0s that are already there). You keep track of the number of passes modulo 2.
• @Denis Indeed. More generally, if $L$ is a regular language, you can decide if $|w|\in L$ (written in some base $b\ge2$). – Emil Jeřábek Feb 18 at 13:35
• Or better, if you keep a binary counter at one end of the string, you can just compute $|w|$ itself in time $O(n\log n)$, and then you can do whatever you want with it. That is, if $L\subseteq\{0,1\}^*$ is any language decidable in time $O(2^{\alpha n})$ for some $1<\alpha<2$, you can decide if $|w|\in L$ in time $O(n^\alpha)$. – Emil Jeřábek Feb 19 at 9:36