Notes

Chapter 11: The Notion of Computation

Section 12: Universality in Turing Machines and Other Systems


States versus colors [in Turing machines]

The total number of possible Turing machines depends on the product s k. The number of distinct machines that need to be considered increases as k increases for given s k (see note above). s=1 or k=1 always yield trivial behavior. The fraction of machines that show non-repetitive behavior seems to increase roughly like (s-1)(k-1) (see page 888). More complex behavior—and presumably also universality—seems however to occur slightly more often with larger k than with larger s.

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