Chapter 3: The World of Simple Programs

Section 4: Turing Machines

Number of [Turing machine] rules

With k possible colors for each cell and s possible states, there are a total of (2 s k)s k possible Turing machine rules. Often many of these rules are immediately equivalent, or can show only very simple behavior (see page 1120).

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