"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:  &gt;0 0 0
t1:   1&gt;0 0
t2:   1 1&gt;0
t3:   1&gt;1 1
t4:  &gt;1 0 1
t5:   0&gt;0 1
t6:   0 1&gt;1
t7:   0&gt;1 0
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$.