Stephen Wolfram's: A New Kind of Science | Online
Jump to Page
Look Up in Index

Chapter 11 Notes > Section 12 > Page 1120 > Note (a) Previous note-----Next note
Notes for: The Notion of Computation | Universality in Turing Machines and Other Systems

*Turing machine enumeration

Of the 4096 s=2, k=2 Turing machines (see page 888) 560 are distinct after taking account of obvious symmetries and equivalences. Ignoring machines which cannot escape from one of their possible states or which yield motion in only one direction or cells of only one color leaves a total of 237 cases. If one now ignores machines that do not allow the head to move more than one step in one of the two directions, that always yield the same color when moving in a particular direction, or that always leave the tape unchanged, one is finally left with just 25 distinct cases.

Of the 2,985,984 s=3, k=2 machines, 125,294 survive after taking account of obvious symmetries and equivalences, while imposing analogs of the other conditions above yields in the end 16,400 distinct cases. For s=2, k=3 machines, the first two numbers are the same, but the final number of distinct cases is 48,505.


Page image


Pages related to this note:


All notes on this page:

* Rule 60 Turing machines
* Turing machine enumeration
* States versus colors [in Turing machines]
* s=2, k=2 Turing machines
* [Turing] machine 596440
* s=3, k=2 Turing machines
* [Universal] tag systems
* [Methods of] encoding sequences by integers
* All notes for this section
* Downloadable programs for this page
* Downloadable images
* Search Forum for this page
* Post a comment
* NKS | Online FAQs
From Stephen Wolfram: A New Kind of Science [citation] Previous note-----Next note