10
$\begingroup$

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
$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Marc Bury Mar 5 '11 at 0:39
  • $\begingroup$ Sorry |x| means length of string x. An example: x = 01101111, n = 8, m = 3, k = 2, and thus $x \in L$ $\endgroup$ – Marzio De Biasi Mar 5 '11 at 0:44
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Joshua Grochow Mar 5 '11 at 16:47
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Marzio De Biasi Mar 5 '11 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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