2
$\begingroup$

Suppose that we have a tape restricted to $n$ cells on binaryalphabet $\Sigma = \{0,1\}$ and initially filled with zeroes.

We want to build a Turing machine $M_n$ (or better a Linear Bounded Automata) that "prints" all the $2^n$ numbers on the tape, i.e. for all $x \in [0..2^{n-1}]$ there is a time $t_x$ during the computation in which the tape content is exactly $x$. Note that we can build an "optimized" Turing machine for every $n$.

At every step the head must move left or right.

What is the minimum number of steps $T(n)$ required?

We can easily see that $2^n-1 \leq T(n) \leq n 2^n$.

But how much can we "optimize" it?

For example for $n=3$ there is an optimal $2^n-1$ sequence:

t0:  >0 0 0
t1:   1>0 0
t2:   1 1>0
t3:   1>1 1
t4:  >1 0 1
t5:   0>0 1
t6:   0 1>1
t7:   0>1 0
$\endgroup$
  • $\begingroup$ Doesn't something like undulating lexicographic enumeration always yield the optimal sequence? (I seem to remember my baby sister telling me about a mathematics exercise problem to that effect.) $\endgroup$ – Raphael Nov 21 '14 at 15:37
  • $\begingroup$ @Raphael: do you have a link that explains it? $\endgroup$ – Vor Nov 21 '14 at 15:53
  • $\begingroup$ No, sorry. The basic idea is to start with $0^n$, fix the first symbol and enumerate the remainder recursively and increasingly. The last number is then $0b^{n-1}$. Now you increase the first bit to $1$ and enumerate the remainder recursively but decreasingly. Iterate until the first bit $b$ is completd. This way, you enumerate all words by changing only one bit at a time. (It occurs to me that this does not immediately mean that the minimal number of TM moves is indeed attained. I think this does not waste moves, though?) $\endgroup$ – Raphael Nov 21 '14 at 16:45
  • $\begingroup$ @Raphael: I tried with 4 bits, but I cannot figure out the sequence. Remember that the TM at each move MUST invert a bit, otherwise it "wastes" one step. If you think it works, try with 5 bits (and post an answer because, in that case it probably works for all n). $\endgroup$ – Vor Nov 21 '14 at 16:51
  • $\begingroup$ @Raphael What you're describing is also known as a Gray code. A Gray code is any permutation of all $n$-bit sequences in which adjacent words differ in one bit. There is a specific recursive construction of such a sequence which is also known as "the" Gray code, and is described in the Wikipedia article and analyzed in my answer. This is probably the construction you're referring to. $\endgroup$ – Yuval Filmus Nov 21 '14 at 22:24
1
$\begingroup$

If you use a Gray code then you can get $O(2^n)$. The Gray code described in the Wikipedia article modifies at time $t$ the position $p_t$ which is the index of the right-most 1 bit in $t$. The resulting position sequence is $$ 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, \ldots $$ You are interested in $\sum_t |p_{t+1}-p_t|$: $$ 1,1,2,2,1,1,3,3,1,1,2,2,1,1,4,4,\ldots. $$ We can see that half the time this is $1$, a quarter of the time it's $2$, one eighth of the time it's $3$, and so on. The total average value is roughly $$ \sum_{n = 1}^\infty \frac{n}{2^n} = 2. $$ So the head moves roughly $2^{n+1}$ times compared to your lower bound of roughly $2^n$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Not every Gray code is equally efficient (in terms of enumeration) on TMs; do we have reason to believe that this one is "best"? $\endgroup$ – Raphael Nov 22 '14 at 10:52
  • $\begingroup$ @Raphael Not at all. This is just the first one I thought of. There are several other suggestions in Wikipedia, and some of them could be better. $\endgroup$ – Yuval Filmus Nov 23 '14 at 1:47
  • $\begingroup$ Well, the question explicitly asks for the minimum... $\endgroup$ – Raphael Nov 24 '14 at 14:09
  • $\begingroup$ @Raphael Sometimes you have to settle for less then the exact answer. This is the case in many combinatorial problems. Also, it's possible that you can prove a non-trivial lower bound, though I haven't tried. $\endgroup$ – Yuval Filmus Nov 24 '14 at 15:03

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.