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.



Image Source Notebooks:

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