10

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
Community
  • 1
Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127
  • 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 05 '11 at 00: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 05 '11 at 00:44
  • 1
    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 05 '11 at 16:47

1 Answers1

10

Can't you use the same idea as what you have for the case of 4 symbols, 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.

Community
  • 1
Jukka Suomela
  • 11,500
  • 2
  • 53
  • 116
  • 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 Mar 05 '11 at 21:07