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.

  • $\begingroup$ 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. $\endgroup$ Feb 19 '20 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.

  • 4
    $\begingroup$ or you can design a similar algorithm to accept iff |w| is a power of 2. $\endgroup$
    – Denis
    Feb 18 '20 at 13:29
  • 1
    $\begingroup$ @Denis Indeed. More generally, if $L$ is a regular language, you can decide if $|w|\in L$ (written in some base $b\ge2$). $\endgroup$ Feb 18 '20 at 13:35
  • 2
    $\begingroup$ 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)$. $\endgroup$ Feb 19 '20 at 9:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.