<p>Can't you use the same idea as <a href="https://cstheory.stackexchange.com/questions/4928/alphabet-of-single-tape-turing-machine/5012#5012">what you have for the case of 4 symbols</a>, with the following modifications:</p>

<ul>
<li>Always process a pair of symbols simultaneously.</li>
<li>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.</li>
<li>Use a similar trick for "mod 2" steps.</li>
</ul>

<p>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.</p>

CC BY-SA 2.5
2011-03-05T21:07:26.343Z
You're right! ... now I suspect that the answer to Emanuele's question is yes ... but it is still open so probably it's not too easy to prove it formally :-( Thanks!
Marzio De Biasi
CC BY-SA 2.5
2011-03-05T11:41:53.190Z
2011-03-05T11:41:53.190Z
2017-04-13T12:32:28.053Z
Jukka Suomela
<p>I was playing with the very interesting and still open question "<a href="https://cstheory.stackexchange.com/questions/4928/alphabet-of-single-tape-turing-machine">Alphabet of single-tape Turing machine</a>" (by Emanuele Viola) and came up with the following language :</p>

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

<p>where $count1(x)$ is the number of $1$s in the string x.</p>

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

<blockquote>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 ?
</blockquote>

<p>If we use 4 symbols the answer is yes:</p>

<ul>
<li>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;</li>
<li>then count the number of $2$s modulo $m$ in $O(n \log{n})$.</li>
</ul>

<p>For example:</p>

<pre><code>....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 --&gt; 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
</code></pre>

CC BY-SA 2.5
2011-03-05T00:39:50.183Z
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
CC BY-SA 2.5
2011-03-05T00:44:36.280Z
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
CC BY-SA 2.5
2011-03-05T16:47:52.443Z
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
<cc.complexity-theory><turing-machines><time-complexity>
Is this language recognizable by a 3 symbols TM in O(n log n)?
Marzio De Biasi
# Is this language recognizable by a 3 symbols TM in O(n log n)?

(Asked by: username_0 on 2011-03-05)

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

**Tags:** cc.complexity-theory, turing-machines, time-complexity

> **Comments:**
> **username_1**: 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$?  
> **username_0**: Sorry |x| means length of string x. An example: x = 01101111, n = 8, m = 3, k = 2, and thus $x \in L$  
> **username_2**: 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)$.  

---

## 1 answers

### Answer by username_3 on 2011-03-05. Score: 10 | Accepted answer

Can't you use the same idea as [what you have for the case of 4 symbols](https://cstheory.stackexchange.com/questions/4928/alphabet-of-single-tape-turing-machine/5012#5012), with the following modifications:

* Always process a pair of symbols simultaneously.
* 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.
* Use a similar trick for "mod 2" steps.

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.

> **Comments:**
> **username_0**: You're right! ... now I suspect that the answer to Emanuele's question is yes ... but it is still open so probably it's not too easy to prove it formally :-( Thanks!  

---

