3
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\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$
    – Marzio De Biasi
    Feb 19, 2020 at 16:09

2 Answers 2

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ or you can design a similar algorithm to accept iff |w| is a power of 2. $\endgroup$
    – Denis
    Feb 18, 2020 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$
    – Emil Jeřábek
    Feb 18, 2020 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$
    – Emil Jeřábek
    Feb 19, 2020 at 9:36
  • $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Apr 9 at 5:49
3
$\begingroup$

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).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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