# “Print 'em all game” for Turing machines

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

• 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.) – Raphael Nov 21 '14 at 15:37
• @Raphael: do you have a link that explains it? – Vor Nov 21 '14 at 15:53
• 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?) – Raphael Nov 21 '14 at 16:45
• @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). – Vor Nov 21 '14 at 16:51
• @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. – Yuval Filmus Nov 21 '14 at 22:24

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$.

• Not every Gray code is equally efficient (in terms of enumeration) on TMs; do we have reason to believe that this one is "best"? – Raphael Nov 22 '14 at 10:52
• @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. – Yuval Filmus Nov 23 '14 at 1:47
• Well, the question explicitly asks for the minimum... – Raphael Nov 24 '14 at 14:09
• @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. – Yuval Filmus Nov 24 '14 at 15:03