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

CC BY-SA 4.0
2023-04-08T22:00:08.190Z
2023-04-08T22:00:08.190Z
QMath
<p>For example, I think you can decide if <span class="math-container">$\lfloor\log_2|w|\rfloor$</span> is even in time <span class="math-container">$O(n\log n)$</span>: you first overwrite the input string with all 1s, and then do <span class="math-container">$\log n$</span> 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.</p>

CC BY-SA 4.0
2020-02-18T13:29:46.490Z
or you can design a similar algorithm to accept iff |w| is a power of 2.
Denis
CC BY-SA 4.0
2020-02-18T13:35:57.173Z
@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
CC BY-SA 4.0
2020-02-19T09:36:45.950Z
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
CC BY-SA 4.0
2023-04-09T05:49:14.130Z
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
CC BY-SA 4.0
2020-02-18T13:17:29.973Z
2020-02-18T13:37:29.513Z
2020-02-18T13:37:29.513Z
Emil Jeřábek
<p>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!</p>

<p>Related paper: <a href="https://www.sciencedirect.com/science/article/pii/0304397585901653" rel="nofollow noreferrer">On the structure of one-tape nondeterministic turing machine time hierarchy</a> by Kobayashi.</p>

<p>Related question: <a href="https://cstheory.stackexchange.com/questions/10990/why-do-we-use-single-tape-turing-machines-for-time-complexity">Why do we use single tape Turing machines for time complexity?</a> by Kaveh.</p>

CC BY-SA 4.0
2020-02-19T16:09:06.350Z
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
<cc.complexity-theory><turing-machines><hierarchy-theorems><time-hierarchy>
$DTIME_1(o(n^2))\setminus$ REGULAR
domotorp
# $DTIME_1(o(n^2))\setminus$ REGULAR

(Asked by: username_0 on 2020-02-18)

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](https://www.sciencedirect.com/science/article/pii/0304397585901653) by Kobayashi.

Related question: [Why do we use single tape Turing machines for time complexity?](https://cstheory.stackexchange.com/questions/10990/why-do-we-use-single-tape-turing-machines-for-time-complexity) by Kaveh.

**Tags:** cc.complexity-theory, turing-machines, hierarchy-theorems, time-hierarchy
> **Comments:**
> **username_1**: 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.  

---

## 2 answers

### Answer by username_3 on 2020-02-18. Score: 9 | Accepted answer

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.

> **Comments:**
> **username_4**: or you can design a similar algorithm to accept iff |w| is a power of 2.  
> **username_3**: @Denis Indeed. More generally, if $L$ is a regular language, you can decide if $|w|\in L$ (written in some base $b\ge2$).  
> **username_3**: 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)$.  
> **username_3**: 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.  

---

### Answer by username_2 on 2023-04-08. Score: 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).


---

