3

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.

domotorp
  • 13,931
  • 37
  • 93
  • 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 '20 at 16:09

2 Answers2

9

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.

Emil Jeřábek
  • 17,430
  • 3
  • 61
  • 90
  • 4
    or you can design a similar algorithm to accept iff |w| is a power of 2. – Denis Feb 18 '20 at 13:29
  • 1
    @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 '20 at 13:35
  • 2
    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 '20 at 09:36
  • More generally, one can decide in the same way whether $(#_a(w),#_b(w),\dots)\in L$, where $a,b,\dots$ are symbols of the alphabet. – Emil Jeřábek Apr 09 '23 at 05:49
3

The language $L=\{0^n1^n : n\geq 0\}$ is non-regular, but decidable in time $O(n\log n)$ on a one-tape Turing machine (one can either use a counter or iteratively remove every next 0 and 1 plus check parity).

QMath
  • 303
  • 1
  • 6