Universal automaton code#

And among these details it is certainly possible that a few errors still remain.

Like most proofs of universality, the final proof he found is conceptually quite straightforward, but is filled with many excruciatingly elaborate details. Many details were filled in over the next year, some mistakes were corrected in 1998, and the specific version in the note below was constructed in 2001. Using this he was then in 1994 successfully able to find the main elements of the proof. I insisted, however, that he keep on trying, and over the next several years he developed a systematic computer-aided design system for working with structures in rule 110. His initial results were encouraging, but after a few months he became increasingly convinced that rule 110 would never in fact be proved universal. The general outline of what had to be done was fairly clear-but there were an immense number of details to be handled, and I asked a young assistant of mine named Matthew Cook to investigate them. And when I started working on the writing of this book in 1991, I decided to try to establish this for certain. Following my ideas about class 4 cellular automata I had come by 1985 to suspect that rule 110 must be universal. In 1989 Kristian Lindgren and Mats Nordahl constructed a 7-color nearest-neighbor cellular automaton that could emulate Minsky's 7,4 universal Turing machine, and showed that in general a rule with s + k + 2 colors could emulate an s-state k-color Turing machine (compare page 658).

A piece published in Scientific American in 1985 describing my interest in finding simple 1D universal cellular automata led me to receive a large number of proofs of the fact (already well known to me) that 1D cellular automata can in principle emulate Turing machines.

Universal automaton code#

In 1984 I suggested that cellular automata showing what I called class 4 behavior should be universal-and I identified some simple rules (such as k = 2, r = 2 totalistic code 20) as explicit candidates. ( Roger Banks also mentioned in 1970 a 17-color cellular automaton that he believed was universal.) But without any particular reason to think it would be interesting, almost nothing was done on finding simpler universal 1D cellular automata. The fact that 1D cellular automata can be universal was discussed by Alvy Ray Smith in 1970-who set up an 18-color nearest-neighbor cellular automaton rule capable of emulating Marvin Minsky's 7-state 4-color universal Turing machine (see page 706).