Chapter 3: The World of Simple Programs

Section 4: Turing Machines

Counter [Turing] machine

Turing machine (f) operates like a base 2 counter: at steps where its head is at the leftmost position, the colors of the cells correspond to the reverse of the base 2 digit sequences of successive numbers. All possible arrangements of colors are thus eventually produced. The overall pattern attains width j after 2^j - j steps.

From Stephen Wolfram: A New Kind of Science [citation]