# Is this language recognizable by a 3 symbols TM in O(n log n)?

I was playing with the very interesting and still open question "Alphabet of single-tape Turing machine" (by Emanuele Viola) and came up with the following language :

$L = \{ x \in \{0,1\}^n \text{ s.t. } |x| = n = 2^m \text{ and } count1(x) = k * m; \; n,m,k \geq 1 \}$

where $count1(x)$ is the number of $1$s in the string x.

For example, if x = 01101111 then n = 8, m = 3, k = 2; so $x \in L$

Can L be recognized by a Turing Machine with a single tape and a 3 symbols alphabet $\{ \epsilon, 0, 1 \}$ in $O(n \log{n})$ steps ?

If we use 4 symbols the answer is yes:

• check if $|x|=2^m$ replacing $0$s with $\epsilon$ and $1$s with $2$ and at the same time store $m$ $1$s on the right;
• then count the number of $2$s modulo $m$ in $O(n \log{n})$.

For example:

....01101111....... input x  (|x| = 8 = 2^3)
000.021.1212.0001.. div 2, first sweep (000. can safely be used as a delimiter)
000.022.1222.00011. div 2, second sweep
000.022.2222.000111 div 2, third sweep --> m = 3 (= log(n) )
000..22.2222....111 cleanup (original 1s are preserved as 2)
000..22.2221102.... start modulo m=3 calculation
000..22.2210022.... mod 3 = 2
000..22.2000222.... mod 3 = 0
000..22.0012222.... mod 3 = 1
000..20112.2222.... mod 3 = 2
000..11122.2222.... ACCEPT

• If $\vert x \vert = n = 2^m$ is the natural number represented by $x$ than $count1(x)$ is always equal to $1$ and so $L = \lbrace 10 \rbrace$? – Marc Bury Mar 5 '11 at 0:39
• Sorry |x| means length of string x. An example: x = 01101111, n = 8, m = 3, k = 2, and thus $x \in L$ – Marzio De Biasi Mar 5 '11 at 0:44
• By the way, this is an excellent candidate for Emanuele's question, since it is in $\Theta(n \log n)$: it is not regular by the pumping lemma, so cannot be $o(n \log n)$, but it is $O(n \log n)$. – Joshua Grochow Mar 5 '11 at 16:47

• In your "div 2" sweeps, mark a two-symbol block as "processed" by mapping $(00, 01, 10, 11) \mapsto (\epsilon0, \epsilon1, 0\epsilon, 1\epsilon)$. You still have $\epsilon\epsilon$ available as a "separator" that you can use at both ends, and you can recover the original data easily.
In general, you can squeeze in arbitrarily large amount of bookkeeping information with the help of the third symbol by processing $O(1)$ symbols at a time.