2. A short history

The game isn't over until it's over.

— Yogi Berra

Ulam [4] and von Neumann [5] gave birth to the field of cellular automaton models and of universal cellular automata in the late 40's. Then it slowly withered away. For many years, no one knew of a simple and symmetric UCA, or believed that there could be a reversible CA that was also uni­versal. The intuitive reasoning was simple; first, universality seemed tied to an irreducible amount of ad hoc complexity, as in a Turing machine and second, a reversible CA seems by its nature to be very constrained in what it can do while a UCA can do anything. By the 60's and early 70's, very few people were interested in this field. In 1975, a leading computer science theoretician at MIT made the following pointed remark: "You can tell that a person is out of it if he doesn't real­ize that cellular automata is a dead field." How­ever, slow but steady progress took place, start­ing with the discovery of the XOR rule in 1962, and followed by Zuse [6], Banks [7], Toffoli [8] and Margolus [9,10]. More recently many others have plunged into this greatly revitalized field, helped to make it more of a science, and discovered many simple, highly symmetric, useful, interesting and provocative UCA and RUCA. In particular, Wol­fram carefully explored the one-dimensional cellular automaton [11,12] and wrote an important se­ries of papers that put many of the existing obser­vations about cellular automata onto a firmer ba­sis [13]. CAs were prematurely pronounced dead.

Our approach, since 1958 when this work be­gan, has been to enlarge the numbers and kinds of physics-like properties and behaviors that we can demonstrate within a computer model, while look­ing for fundamental principles that could guide our search. In nature, for example, we have 3 plus 1 space-time, particles, fields, conserved quanti­ties, charge, computation universality, spin, etc. CAs can deal naturally with Euclidean space-time, but finding CA Systems that model aspects of the real physical world is work in progress. What is true is that most serious attempts to find a way to incorporate a property of nature into the CA environment have met with progress; today we see ways of incorporating dozens of character­istics of the real world into CA models. At one time, it seemed unlikely that a simple and sym­metric universal rule could be found. In the 60's, Marvin Minsky challenged the author to find a way to demonstrate any form of spherical propa­gation.

Fortunately, ways around many of the apparent limitations of CA models have been found as more people have begun working in this field. When it appears to be true that some essential prop­erty of physics cannot be modelled by CA, then many observers feel justified in not looking fur­ther. For example, it once seemed that a CA could neither model Lorentz invariance nor be quantum-mechanically correct. Since then we have learned that it is naive to state what a UCA cannot do! Given finite nature, universality has the power to overcome every objection; we just have to figure out how to do it. Unfortunately, knowing it can be done is very far from doing it.

Those criticals of DM often state "A UCA will never be able to do X", where X is some part of physics. Normally, it is that the speaker, quite rea­sonably, does not subscribe to finite nature. Some­times the speaker has tried to think of a way for a UCA to do X and has come up empty handed. Sometimes we do not believe that X is a prop­erty of nature. It is hard to imagine a rigorous proof about what kind of finite problem cannot be solved by a finite UCA. Of course, for DM to make sense we must assume finite nature. Finite nature may or may not be true, but surely the assump­tion is not known to be false. If finite nature turns out to be false then DM is irrelevant as an exact model, but it might be useful as an approximate model (the way computers are presently used to model physics).

What is most interesting is not what DM is to­day, but the steady progress that the field has made in overcoming a series of limitations that each appeared insurmountable in its day.

[4]  S. Ulam, Random Processes and Transformations, Proceedings of the International Congress on Mathe­matics, 1950, Vol.2 (1952) pp.264-275.

[5]  J. von Neumann, Theory of Self-Reproducing Au­tomata, edited and completed by A. Burks (Univer­sity of Illinois Press, Champaign, IL, 1966).

[6]    K. Zuse, Rechnender Raum (Vieweg, Braunschweig, 1969); translated as "Calculating Space", AZT-70-164- GEMIT MIT Project MAC (1970).

[7]    E. Banks, Information processing and transmission in cellular automata, Doctoral Dissertation and Techni­cal Rep6rt MAC TR-81, MIT Project MAC (1971).

[8]  T. Toffoli, Cellular automata mechanics, Technical Report 208, Computer and Communication Sciences Department, University of Michigan (1977).

[9]  N. Margolus, Physics-like models of computation, Physica D 10 (1984) 81-95.

[10]  N. Margolus, Physics and computation, Technical Re­port 416, Laboratory for Computer Science, MIT (1987).

[11]  S. Wolfram, Statistical mechanics of cellular au­tomata, Rev. Mod. Phys. 55 (1983) 601-644.

[12]  S. Wolfram, Universality and complexity in cellular automata, Physica D 10 (1984) 1-35.

[13] S. Wolfram, Computation theory of cellular automata, Commun. Math. Phys. 96 (1984) 15-57.