Cellular Automata

Noticing that the figure consists of certain particle-like objects sprinkled on a more-or-less static background, the simplest (most natural?) thing for you to do (…) is to begin cataloging the various “particles” and their “interactions.” (…) What you almost assuredly will not have, is any idea that the underlying physics really consists of a single—very simple—local deterministic rule(…). How different is this alien two-dimensional world from our own? (Ilachinski 2001, p. 662).

This highlights how CA may generate situations that we naturally view as physically realistic. A philosopher would consider this more as a suggestion than as a full-fledged argument: that we cannot rule out a priori our universe's being, at its bottom level, a CA does not entail that it actually is a CA.

A firmer ground to explore the hypothesis comes from some independent reasons of theoretical dissatisfaction with contemporary physics. We will limit ourselves to what we may call conceptual complaints, as opposed to ones more closely related to scientific practice, such as the failure of reductions of quantum mechanics and relativity to a Theory of Everything. We will examine the following three: (i) the problem of infinity, (ii) the need for a transparent ontology,(iii) the physical role of information.

As for complaint (i): while infinite and infinitesimal quantities provide us with powerful tools to model and advance predictions on the physical world, it remains controversial what ontological conclusions should be drawn from this fact. Since Zeno's Paradox (see the related entry) the continuity of space-time, as well as other fundamental physical variables, have puzzled philosophers and scientists alike. In the words of the physicist Richard Feynman:

It bothers me that, according to the laws as we understand them today, it takes a computing machine an infinite number of logical operations to figure out what goes on in no matter how tiny a region of space, and no matter how tiny a region of time. How can all that be going on in that tiny space? Why should it take an infinite amount of logic to figure out what a tiny piece of space-time is going to do? So I have often made the hypothesis that ultimately physics will not require a mathematical statement, that in the end the machinery will be revealed and the laws will turn out to be simple, like the checker board with all its apparent complexities. (Feynman 1965)

One way theoretical physicists have approached the problem has been to postulate a further reality, one that is below what is described by current physics. This fundamental layer of reality has often been conceived along the lines of Edward Fredkin's “Finite Nature Hypothesis”:

Finite Nature is a hypothesis that ultimately every quantity of physics, including space and time, will turn out to be discrete and finite; that the amount of information in any small volume of space-time will be finite and equal to one of a small number of possibilities. (…) We take the position that Finite Nature implies that the basic substrate of physics operates in a manner similar to the workings of certain specialized computers called cellular automata. (Fredkin 1993, p. 116)

If a cellular automaton is a model satisfying this hypothesis, then “underneath the laws of physics as we know them today it could be that there lies a simple program from which all the known laws (…) emerge” (Wolfram 2002, p. 434). If there currently is no way of saying if physics is fundamentally continuous or discrete, at least the Finite Nature Hypothesis seems to be a no less falsifiable prediction (see Fredkin 1990) than many speculative metaphysical pictures. Unfortunately, although we have attempts to recapture field theory within CA theory (see e.g. Svozil 1987, Lee 1986), there is no agreed-upon derivation of today's continuous physics within a CA framework; it is therefore safe to say that no party has a clear advantage here.

As for complaint (ii): one reason to adopt the view of CA as models of a fundamentally discrete world is the desire for a transparent ontology. Take a materialist philosopher for whom the task of physics is to provide an ultimate description of reality on the basis of a handful of basic physical properties and relations. In this perspective, a CA-based physics may provide a neat and elegant ontological picture: one that would be describable in a first-order formal theory including the axioms of standard mereology (even of mereotopology, as presented e.g. in Casati, Varzi 1999), and whose theorems would be computable in finite time (see Berto, Rossi, Tagliabue 2010, pp. 73–87). Besides, CA make easier to reconcile seemingly contradictory properties of different physical laws, such as the reversibility of micro-laws and the irreversibility of the Second Law of Thermodynamics (see for example Wolfram 2002, pp. 441–457 and Berto, Rossi, Tagliabue 2010, pp. 43–46).

As for point (iii), concerning the physical role of information: CA can accommodate a hypothesis endorsed by a growing number of scientists and philosophers, namely that information is not just one aspect of the physical world, but, in a sense, the most fundamental. For instance, Fredkin's Finite Nature Hypothesis not only stresses the importance of the informational aspects of physics, but “it insists that the informational aspects are all there is to physics at the most microscopic level” (see Fredkin 1993).

One way in which this idea has been developed is the so-called “it from bit” theory (see for example Wheeler 1990). In David Chalmers' words, this approach “stems from the observation that in physical theories, fundamental physical states are individuated as informational states” (Chalmers 1996, p. 302). Physics is silent on what accomplishes the specified functional roles, so “any realization of these information states will serve as well for the purpose of a physical theory” (Chalmers 1996, p. 302). The “it from bit” approach is particularly appealing to Chalmers (as a philosopher of mind committed to qualia being intrinsic, non-reducible properties) because it allows for a simple unification: we need intrinsic properties to make sense of conscious experience, and we need intrinsic properties to ground the informational states that make up the world's physics. If we claim that all the informational states are grounded in phenomenal (or proto-phenomenal) properties, we “get away with a cheap and elegant ontology, and solve two problems in a single blow” (Chalmers 1996, p. 305). The cell states in a CA fit the bill: if we interpret them as proto-phenomenal properties, we obtain the intrinsic structure of some sort of computational neutral monism (for an historical introduction, see the related entry)

Albeit individually controversial, taken together the three points support a simple and elegant metaphysical picture which is not evidently false or incoherent. Supposing that the actual physical world is a giant, discrete automaton, are there philosophically interesting conclusions to be drawn?

A first conclusion has already been partially explored in connection with Life: if nature is a CA, it has to be a universal CA, given that universal computers (e.g., the one on which you are reading this entry) uncontroversially exist in the physical world. Then its evolution is algorithmically irreducible, given the Halting Problem. Notwithstanding the opportunity of devising approximate forecast tools, we are left with a universe whose evolution is unpredictable for a reason quite different from the ones commonly adduced by resorting to standard physics, such as quantum effects or random fluctuations: it is unpredictable just because of its computational complexity.

A second philosophical topic is the connection between a CA-world and one of the most famous contemporary metaphysical theses, namely David Lewis' Humean Supervenience (HS). Using Ned Hall's characterization, we can state HS as the collection of these four claims about the structure of our world:

(HS₁) There are particulars (space-time points).  
(HS₂) They are, or are wholly composed of, simples — particulars that have no other particulars as parts.  
(HS₃) These simples have various perfectly natural monadic properties.  
(HS₄) They stand in various spatiotemporal relations to one another.

If we substitute “space-time points” with “cells”, HS gets very close to a CA ontology: cells are arranged in a lattice, have various spatiotemporal relations to one another (e.g., being a neighborhood of), and have monadic properties (states) which can be considered perfectly natural, i.e., the basic properties out of which any other can be construed. A CA universe is thus a prima facie abstract model of Lewis' HS and can be fruitfully used to illustrate Lewis' original point, which was a reductionist one:

The point of defending Humean Supervenience is not to support reactionary physics, but rather to resist philosophical arguments that there are more things in heaven and earth than physics has dreamt of. (Lewis 1994, p. 474).

There are, however, two differences between the ontology naturally suggested by CA theories and Lewis' view. First, for Lewis space-time is an essentially continuous, four-dimensional manifold, eternalistically conceived (see the entry on eternalism and four-dimensionalism for an introduction), while in a standard CA-driven ontology, it is not. Second, Lewis reduces laws of nature to particulars while, as we have seen in Section 2 above, CA rules are always included as a further specification of the model.

The first disagreement may not be very substantial. A CA-world is compatible, for instance, with an eternalist conception. The idea that the world's next state is computed at any time step can be seen as a merely heuristic device, a “shortcut” for a more proper eternalist description in which the cell's states are once and for all “stuck” in their space-time position (we did this ourselves when describing the first picture in this section as the complete space-time evolution of a micro-universe).

The second disagreement concerning the laws of nature, on the other hand, may be a thorny issue. According to Lewis 1973, laws of nature are the true generalizations found in the deductive system that best describes our world (where “best” basically refers to the optimal trade-off between strength and simplicity; see the related entry for an introduction to, and further details on, this debate): laws of nature supervene on the four-dimensional arrangement of particulars and their properties. To the contrary, the standard description of a CA does not take the space-time evolution for granted: it takes the automaton's initial conditions as given, and generates the system evolution over time via the CA transition function. Particulars depend on laws, not vice versa. A CA world is not laid out in advance, but it grows as long as the laws are applied to particulars (a similar point is also made in Wolfram 2002, pp. 484–486).

On the other hand, one may tentatively interpret, in Lewisian fashion, the laws of a CA as the generalizations contained within the deductive system that best describes the CA behavior. Let us consider one last time our micro-universe from Rule 110:

A suitable deductive system for this space-time diagram may be obtained with just two axioms, one stating the initial conditions of the system, and one phrased as a conditional expressing the CA transition rule. If this conditional is a true generalization embedded in the deductive system that best describes our toy universe, then Rule 110 can count as a Lewisian law of nature in this universe, as expected.

4. Concluding Remarks

Although some CA topics are still relatively untouched by philosophers (e.g., the nature of space and time (see Wolfram 2002, pp. 481–496), the representation of knowledge in Artificial Intelligence (see Berto, Rossi, Tagliabue, pp. 15–26), the relationship between information and energy (see Fredkin, Toffoli 1982)), there are many conceptual challenges raised in connection with CA. While in some cases the CA contribution was indeed overrated by practitioners, in others CA proved to be useful and transparent models of important phenomena.

As a final comment: what is left, from a purely scientific perspective, of the NKS Argument? Let us go through it again:

(NKS₁) The observation of CA evolution leads to a scientific discovery: “very simple rules produce highly complex behavior” (Wolfram 2002, p. 39). 
(NKS₂) This discovery—the “new intuition”—promises to explain old and new phenomena and uncover important regularities. 
(NKS₃) Therefore, the core of our current scientific practices (based on the “old intuition”) should be radically changed to accommodate this discovery.

Even granting the truth of the two premises (that is, even granting the troublesome Principle of Computational Equivalence), it is doubtful the desired conclusion would follow. Surely, CA have provided new intuitions and explanations for a set of phenomena—Wolfram quite succesfully applies his “discovery” to biology, computer science, physics, finance. However, there is no evidence that many of our best scientific explanations will soon be reduced to the CA framework, and indeed many aspects of complexity itself still lie outside the CA paradigm, with no unification in sight. Paradigm shifts usually require the new paradigm to explain the same phenomena the old one did, and some more. CA are a promising field, but many developments are still needed for (NKS₃) to be true.

Bibliography

Miller, Page 2007 and Mitchell 2009 both contain a chapter devoted to CA: they are accessible introductions written by notable scholars. Ilachinski 2001 is an excellent starting point for the exploration of the CA literature: although not up-to-date on some technical points, the volume nicely introduces the field and covers its most important applications. Wolfram 2002 took some twenty-years and 1200 pages to be finished and is a passionate journey including bold speculations on the role of CA for understanding the universe and our place in it.

• Batty, M., 2005, Cities and Complexity, Understanding Cities with Cellular Automata, Agent-Based Models, and Fractals, Cambridge, MA: MIT Press.
• Bedau, M., 1997, “Weak Emergence,” in Philosophical Perspectives, 11: Mind, Causation, and World, J. Tomberlin (ed.), Oxford: Blackwell Publishers, pp. 375–399.
• Berto, F., Rossi G., Tagliabue J., 2010, The Mathematics of the Models of Reference, London: College Publications.
• Berlekamp, E., Conway J., Guy R., 1982, Winning Ways for Your Mathematical Plays, Vol. 2, London: Academic Press.
• Casati, R., Varzi A., 1999, Parts and Places, Cambridge, MA: MIT Press.
• Chalmers, D., 1996, The Conscious Mind, Oxford: Oxford University Press.
• –––, 2002, “Strong and Weak Emergence,” in The Re-Emergence of Emergence, P. Clayton and P. Davies (eds.), Oxford: Oxford University Press, pp. 244–255.
• Chen, H., Chen S., Doolen G., Lee Y.C., 1983, “Simple lattice gas models for waves,” Complex Systems, 2: 259–267.
• Clark, A., 1996, Being There, Cambridge, MA: MIT Press.
• Cook, M., 2004, “Universality in Elementary Cellular Automata”, Complex Systems, 15: 1–40.
• Creutz, M., 1986, “Deterministic Ising dynamics,” Annals of Physics, 167: 62–76.
• Crutchfield, J. P., 1994a, “The Calculi of Emergence: Computation, Dynamics, and Induction,” Physica D 75: 11–54.
• –––, 1994b, “Is Anything Ever New? Considering Emergence,” in Complexity: Metaphors, Models, and Reality, G. Cowan, D. Pines, D. Melzner (eds.), SFI Series in the Sciences of Complexity XIX, Redwood City, CA: Addison-Wesley, pp. 479-497.
• Crutchfield, J. P. , Hanson J. E., 1993, “Turbulent Pattern Bases for Cellular Automata,” Physica D 69: 279–301.
• Crutchfield, J. P., Mitchell M., 1995, “The evolution of emergent computation,” Proceedings of the National Academy of Sciences, 92(23): 10742.
• Dennett, D., 1991, “Real Patterns”, Journal of Philosophy, 88: 27–51.
• –––, 2003, Freedom Evolves, New York: Viking Penguin.
• Hedlund, G.A., 1969, “Endomorphisms and Automorphisms of the Shift Dynamical System”, Mathematical Systems Theory, 3: 51–59.
• Epstein, J.M., 1999, “Agent-based computational models and generative social science,” Complexity, 4(5):41–60.
• Feynman, R. P., The Character of Physical Law, Cambridge, MA: MIT Press.
• Franceschetti, D. R., Campbell B. W., Hamneken J. W., 1992, “Hamming nets, Ising sets, cellular automata, neural nets and random walks,” American Journal of Physics, 61: 50–53.
• Fredkin, E., Toffoli T., 1982, “Conservative logic,” International Journal of Theoretical Physics, 21:219–253.
• Fredkin, E., 1990, “Digital Mechanics: An Information Process Based on Reversible Universal Cellular Automata,” Physica D, 45:254–270.
• –––, 1993, “A New Cosmogony,” in PhysComp '92: Proceedings of the Workshop on Physics and Computation, IEEE Computer Society Press, pp. 116–121.
• Gell-Mann, M., 1994, The Quark and the Jaguar, New York: W.H. Freeman and Company.
• Hanson, J. E., Crutchfield J. P., 1992, “The Attractor-Basin Portrait of a Cellular Automaton,” Journal of Statistical Physics, 66: 1415–1462.
• Hordijk, W., Crutchfield J. P., Mitchell M., 1996, “Embedded Particle Computation in Evolved Cellular Automata,” in Proceedings of the Conference on Physics and Computation.
• Ilachinski, A., 2001, Cellular Automata, Singapore: World Scientific Publishing.
• Ingerson, T.E., and R.L. Buvel, 1984, “Structure in asynchronous cellular automata,” Physica D 10:59–68.
• Kauffman, S., 1984, “Emergent properties in random complex automata,” Physica D 10: 145–156.
• Kim, J., 1999, “Making Sense of Emergence,” Philosophical Studies, 95: 3–36.
• Land, M., Belew R., 1995, “No Perfect Two-State Cellular Automata for Density Classification Exist”, Physical Review Letters, 74: 1548–1550.
• Landauer, R., 1961, “Irreversibility and Heat Generation in the Computing Process”, IBM Journal of Research and Developmen, 5: 183–191.
• Langton, C., 1990, “Computation at the Edge of Chaos: Phase Transitions and Emergent Computation,” Physica D, 42:12–37.
• Lee, T.D., 1986, “Solutions of Discrete Mechanics Near the Continuum Limit,” in Rationale of Being, K. Ishikawa et al. (eds.), Singapore: World Scientific Publishing.
• Lewis, D., 1973, Counterfactuals, Oxford: Blackwell Publishers.
• –––, 1994, “Humean Supervenience Debugged,” Mind, 103: 473–490.
• Miller, J., Page S., 2007, Complex Adaptive System, Princeton: Princeton University Press.
• Mitchell, M., 1998, An Introduction to Genetic Algorithms, Cambridge, MA: MIT Press.
• –––, 2009, Complexity: A Guided Tour, Oxford: Oxford University Press.
• Mitchell, M., Crutchfield J. P., Das R., 1996, “Evolving Cellular Automata with Genetic Algorithm: A Review of Recent Works,” in Proceedings of the First International Conference on Evolutionary Computation and Its Applications, Russian Academy of Science.
• Mitchell, M., Hraber P. T., Crutchfield J. P., 1994, “Revisiting the Edge of Chaos: Evolving Cellular Automata to Perform Computations,” Complex Systems, 7: 89–130.
• Moore, C., “Recursion Theory on the Reals and Continuous-Time Computation,” Theoretical Computer Science, 162: 23–44.
• Moore, E. F., 1962, “Machine Models of Self-Reproduction”, Proceedings of Symposia in Applied Mathematics , 14: 17–33.
• Myhill, J., 1963, “The Converse of Moore's Garden-of-Eden Theorem”, Proceedings of the American Mathematical Society, 14: 685–686.
• Packard, N., 1988, “Adaptation toward the Edge of Chaos,” in Dynamic Patterns in Complex Systems, J.A.S. Kelso, A.J. Mandell and M.F. Schlesinger (eds.), Singapore: World Scientific Publishing, pp. 293–301.
• Poincaré, H., 1914, Science and Method, New York: Nelsons and Sons.
• Putnam, H., 1988, Representation and Reality, Cambridge, MA: MIT Press.
• Richards, F., Meyer T., Packard N., 1990, “Extracting Cellular Automaton Rules Directly from Experimental Data,” Physica D, 45:189–202.
• Searle, J. R., 1992, The Rediscovery of the Mind, Cambridge: MIT Press.
• Svozil, K., 1987, “Are Quantum Fields Cellular Automata?,” Physics Letters, 119: 153–6.
• Teller, P., 1992, “A Contemporary Look at Emergence,” in Emergence or Reduction?, A. Beckermann, H. Flohr and J. Kim (eds.), Berlin: Walter de Gruyter.
• Thompson, E., 2007, Mind in Life. Biology, Phenomenology, and the Sciences of Mind, Cambridge: Harvard University Press.
• Toffoli, Т., 1977, “Computation and Construction Universality of Reversible Cellular Automata”, Journal of Computer and System Science, 15: 213.
• Turing, A., 1936, “On Computable Numbers with an Application to the Entscheideungproblem,” Proceeding of the London Mathematical Society, 42: 230–265.
• Von Neumann, J., 1951, “The General and Logical Theory of Automata,” in Cerebral Mechanisms in Behavior: The Hixon Symposium, New York: John Wiley & Sons.
• Wheeler, J.A., 1990, “Information, Physics, Quantum: The Search for Links,” in Complexity, Entropy, and the Physics of Information, W. Zurek (ed.), Boston: Addison-Wesley.
• Wolfram, S., 1983, “Statistical Mechanics of Cellular Automata,” Reviews of Modern Physics, 55: 601–644.
• –––, 2002, A New Kind of Science, Champaign, IL: Wolfram Media.
• Zuse, K., 1982, “The Computing Universe,” International Journal of Theoretical Physics, 21: 589–600.