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
Improve this question
$\endgroup$
3
  • $\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, 2011 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, 2011 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, 2011 at 16:47

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\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, 2011 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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