3

This is another question related to the (still open) nice question "Alphabet of single-tape Turing machine" by Emanuele Viola. I describe the question very informally (perhaps it has a trivial solution, so I will delete it).

Idea: build a TM that sweeps the input tape from left to right, and right to left "adding" to each symbol an incremental value (and trying to use all available symbols).

Let $\Sigma_4 = \{.,0,1,2\}$ be a 4 symbols alphabet.

We map each pair of symbols to an integer according to the following table:

00->0    10->4    20->8    .0->12
01->1    11->5    21->9    .1->13
02->2    12->6    22->10   .2->14
0.->3    1.->7    2.->11

Informally, the dot "." is used like the symbol "$3$". So, we can encode an integer in [0..14] using two symbols. The pair "$..$" will be used as a separator.

We informally define a function that "sweeps" the input from left to right - processing 2 symbols at once - and adds the last integer written on the tape to the current one modulo 15. For example (left-right sweep):

>01  00  11  01  10  11   Decoded: >1  0  5  1   4  5
 01 >00  11  01  10  11            [1  0] 5  1   4  5
 01  01 >11  01  10  11             1 [1  5] 1   4  5
 01  01  12 >01  10  11             1  1 [6  1]  4  5
 01  01  12  13 >10  11             1  1  6 [7   4] 5
 01  01  12  13  2. >11             1  1  6  7 [11  5]
 01  01  12  13  2.  11             1  1  6  7  11  1

Then it do the same thing from right to left (right-left sweep):

 01  01  12  13  2.  11<   Decoded: 1  1   6  7  11  1<
 01  01  12  13  2.< 11             1  1   6  7 [11  1]
 01  01  12  13< .0  11             1  1   6 [7  12] 1
 01  01  12< 10  .0  11             1  1  [6  4] 12  1
 01  01< 22  10  .0  11             1 [1  10] 4  12  1
 01< 2.  22  10  .0  11            [1 11] 10  4  12  1
 .0  2.  22  10  .0  11            12 11  10  4  12  1

Now we define:

$\displaylines{ L = \{ x \in \{0,1\}^* \, s.t. \, |x| = 2^k \text{ and after } k \text{ left-right + right-left sweeps} \cr \text{ the tape contains the same number of 1s and 2s } \} } $

$L$ can be recognized by a TM using alphabet $\Sigma_4$ in $O(N \log{N})$ :

  1. check the length of the input string ($|x|=2^k$) and store $k$ in unary format on the left,
  2. make $k$ left-right, right-left sweeps
  3. compare the number of 1s and 2s using the usual $O(N \log{N})$ technique
Can we build a Turing machine TM3 that uses only 3 symbols $\Sigma_3 = \{.,1,2\}$ and recognizes $L$ in $O(N \log{N})$ ?

Steps 1 and 3 can be performed by a 3-symbols TM (see my previous question for details).

But step 2 seems to add "more information" and the extra symbol $2$ cannot be stored by TM3, so it must expand the input (and the resulting time complexity is $O(N^2)$).

I say "more information" because the value of each pair of symbols (at the end of the sweeps) depends on $k$ and on the number of 1s in the original input tape (at both sides).

Furthermore the bookkeeping tecnique (using the "." symbol) seems not to work in this case because the symbol itself is used in the encoding during the sweeps.

Community
  • 1
Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127
  • 1
    Vor, I don't know if this is a good way of using the site, it seems to me that you are trying to answer another question by posting ideas you come up as questions for others. (ps: I guess that Emanuele's question doesn't have an easy answer, experts in simulation results should have thought about this case. I asked a few seniors and they don't remember if there is a positive/negative result. Of course it might be the case that they haven't spend much time on it since the model is not very interesting in general because of non-robustness, e.g. provability of quadratic lowerbounds (more) – Kaveh Mar 15 '11 at 03:30
  • , but IMHO we can consider it an open-problem.) – Kaveh Mar 15 '11 at 03:36
  • 1
    @Kaveh: While I think I agree with you in general, here's a partial counterargument (and maybe after this the discussion, if there is one, should move to meta): I think if someone posted a family of graphs and asked if any of the known GraphIso algorithms could decide isomorphism for this family in polynomial time, that would be a valid and potentially interesting question. It could result in any of: a reference, potentially learning about how an old technique applies to new examples, a new technique, or new hard test cases. (I recognize this case is slightly different, but still...) – Joshua Grochow Mar 15 '11 at 04:27
  • @Joshua, I agree with what you say. I have just some doubts about this way of using the site in this particular case (as it seems to me as proposing ideas about solving another question as new questions for others to check those ideas, I feel that it might be better to submit them as answers/comments to the original question), but it doesn't mean there is a problem with this way of using the site, it is just my personal taste as a user. – Kaveh Mar 15 '11 at 04:41
  • 3
    @Kaveh: Ah. I thought you were suggesting removing it altogether. But I like this idea: first post the proposed solution as an actual answer on the question. If it turns out through comments that the proposed solution is trivial, then great, and now that is there for all people perusing the OQ to see. If it turns out through comments that it's more complicated, then perhaps opening a new question to allow non-character-limited responses to the proposed solution would be appropriate. – Joshua Grochow Mar 15 '11 at 04:58
  • 4
    I think this is completely valid use of the site. The question stated is derivative, but also focused, research-level and has a clear answer. If it does not receive an answer, all the better: keeping track of open questions is as important as collecting answers, imho. – Raphael Mar 15 '11 at 18:03

0 Answers0