Is the Universe a Computer?

1.

Everyone knows that electronic computers have enormously helped the work of science. Some scientists have had a grander vision of the importance of the computer. They expect that it will change our view of science itself, of what it is that scientific theories are supposed to accomplish, and of the kinds of theories that might achieve these goals.

I have never shared this vision. For me, the modern computer is only a faster, cheaper, and more reliable version of the teams of clerical workers (then called “computers”) that were programmed at Los Alamos during World War II to do numerical calculations. But neither I nor most of the other theoretical physicists of my generation learned as students to use electronic computers. That skill was mostly needed for number crunching by experimentalists who had to process huge quantities of numerical data, and by theorists who worked on problems like stellar structure or bomb design. Computers generally weren’t needed by theorists like me, whose work aimed at inventing theories and calculating what these theories predict only in the easiest cases.

Still, from time to time I have needed to find the numerical solution of a differential equation,¹ and with some embarrassment I would have to recruit a colleague or a graduate student to do the job for me. It was therefore a happy day for me when I learned to use a program called Mathematica, written for personal computers under the direction of Stephen Wolfram. All one had to do was to type out the equations to be solved in the prescribed code, press shift-enter, and, presto, the answer would pop up on the monitor screen. The Mathematica user’s manual now sits on my desk, so fat and heavy that it does double duty as a bookend for the other books I keep close at hand.

Now Wolfram has written another book that is almost as heavy as the Mathematica user’s manual, and that has attracted much attention in the press. A New Kind of Science describes a radical vision of the future of science, based on Wolfram’s long love affair with computers. The book’s publisher, Wolfram Media, announces “a whole new way of looking at the operation of our universe” and “a series of dramatic discoveries never before made public.” Wolfram claims to offer a revolution in the nature of science, again and again distancing his work from what he calls traditional science, with remarks like “If traditional science was our only guide, then at this point we would probably be quite stuck.” He stakes his claim in the first few lines of the book: “Three centuries ago science was transformed by the dramatic new idea that rules based on mathematical equations could be used to describe the natural world. My purpose in this book is to initiate another such transformation….”

Usually I put books that make claims like these on the crackpot shelf of my office bookcase. In the case of Wolfram’s book, that would be a mistake. Wolfram is smart, winner of a MacArthur Fellowship at age twenty-two, and the progenitor of the invaluable Mathematica, and he has lots of stimulating things to say about computers and science. I don’t think that his book comes close to meeting his goals or justifying his claims, but if it is a failure it is an interesting one.

The central theme of the book is easily stated. It is that many simple rules can lead to complex behavior. The example that is used repeatedly to illustrate this theme is a favorite toy of complexity theorists known as the cellular automaton, so I will have to say a bit about what cellular automata are.

Take a piece of white graph paper that has been cross-hatched into little squares. These are the “cells.” Blacken one or more of the cells in the top row, chosen any way you like, leaving all the others white. This is your input. Now blacken some cells in the second row, according to some fixed rule that tells you to make any cell black or leave it white depending on the colors of its three neighboring cells in the first row (that is, the cells in the first row that are either immediately above the cell in the second row or one cell over to the right or left.) Then use the same rule, whatever it is, automatically to color each cell in the third row according to the colors of its three neighboring cells in the second row, and keep going automatically in the same way to the rows below. The coloring rule used in this way is an elementary cellular automaton.

This may seem like a solitaire variation on tick-tack-toe, only not as exciting. Indeed, most of the 256 possible² elementary cellular automata of this sort are pretty boring. For instance, consider rule 254, which dictates that a cell is made black if the cell immediately above it, or above it and one space over to the left or right, is black, and otherwise it is left white. Whatever the input pattern of black cells in the top row, the black cells will spread in the rows below, eventually filling out an expanding black triangle, so that the cells in any given column will all be black once you get to a low-enough row.

But wait. Wolfram’s prize automaton is number 110 in his list of 256. Rule 110 dictates that a cell in one row is left white if the three neighboring cells in the row above are all black or all white or black-white-white, and otherwise it is made black. Figure A shows the result of applying this rule twenty times with a very simple input, in which just one cell is made black in the top row. Not much happening here. Wolfram programmed a computer to run this automaton, and he ran it for millions of steps. After a few hundred steps something surprising happened: the rule began to produce a remarkably rich structure, neither regular nor completely random. The result after 700 steps is shown in Figure B. A pattern of black cells spreads to the left, with a foamy strip furthest to the left, then a periodic alternation of regions of greater and lesser density of black cells which moves to the right, followed by a jumble of black and white cells. It is a dramatic demonstration of Wolfram’s conclusion, that even quite simple rules and inputs can produce complex behavior.

Wolfram is not the first to have worked with cellular automata. They had been studied for decades by a group headed by Edward Fredkin at MIT, following the ground-breaking work of John Von Neumann and Stanislas Ulam in the 1950s. Wolfram is also not the first to have seen complexity coming out of simple rules in automata or elsewhere. Around 1970 the Princeton mathematician John Horton Conway invented “The Game of Life,” a two-dimensional cellular automaton in which cells are blackened according to a rule depending on the colors of all the surrounding cells, not just the cells in the row above. Running the game produces a variety of proliferating structures reminiscent of microorganisms seen under a microscope. For a while the Game of Life was dangerously addictive for graduate students in physics. A decade later another mathematician, Benoit Mandelbrot, the inventor of fractals, gave a simple algebraic prescription for constructing the famous Mandelbrot set, a connected two-dimensional figure that shows an unbelievable richness of complex detail when examined at smaller and smaller scales.

There are also well-known examples of complexity emerging from simple rules in the real world. Suppose that a uniform stream of air is flowing in a wind tunnel past some simply shaped obstacle, like a smooth solid ball. If the air speed is sufficiently low then the air flows in a simple smooth pattern over the surface of the ball. Aerodynamicists call this laminar flow. If the air speed is increased beyond a certain point, vortices of air appear behind the ball, eventually forming a regular trail of vortices called a “Von Karman street.” Then as the air speed is increased further the regularity of the pattern of vortices is lost, and the flow begins to be turbulent. The air flow is then truly complex, yet it emerges from the simple differential equations of aerodynamics and the simple setup of wind flowing past a ball.

What Wolfram has done that seems to be new is to study a huge number of simple automata of all types, looking specifically for those that produce complex structures. There are cellular automata with more than two colors, or with coloring rules like the Game of Life that change the colors of cells in more than one row at a time, or with cells in more than two dimensions. Beyond cellular automata, there are also automata with extra features like memory, including the Turing machine, about which more later. From his explorations of these various automata, Wolfram has found that the patterns they produce fall into four classes. Some are very simple, like the spreading black triangle in the rule 254 elementary cellular automaton that I mentioned first. Other patterns are repetitive, such as nested patterns that repeat themselves endlessly at larger and larger scales. Still others seem entirely random. Most interesting are automata of the fourth class, of which rule 110 is a paradigm. These automata produce truly complex patterns, neither repetitive nor fully random, with complicated structures appearing here and there in an unpredictable way.

So what does this do for science? The answer depends on why one is interested in complexity, and that depends in turn on why one is interested in science.

2.

Some complex phenomena are studied by scientists because the phenomena themselves are interesting. They may be important to technology, like the turbulent flow of air past an airplane, or directly relevant to our own lives, like memory, or just so lovely or strange that we can’t help being interested in them, like snowflakes. Unfortunately, as far as I can tell, there is not one real-world complex phenomenon that has been convincingly explained by Wolfram’s computer experiments.

Take snowflakes. Wolfram has found cellular automata in which each step corresponds to the gain or loss of water molecules on the circumference of a growing snowflake. After adding a few hundred molecules some of these automata produce patterns that do look like real snowflakes. The trouble is that real snowflakes don’t contain a few hundred water molecules, but more than a thousand billion billion molecules. If Wolfram knows what pattern his cellular automaton would produce if it ran long enough to add that many water molecules, he does not say so.

Or take complex systems in biology, like the human nervous or immune systems. Wolfram proposes that the complexity of such systems is not built up gradually in a complicated evolutionary history, but is rather a consequence of some unknown simple rules, more or less in the way that the complex behavior of the pattern produced by cellular automaton 110 is a consequence of its simple rules. Maybe so, but there is no evidence for this. In any case, even if Wolfram’s speculation were correct it would not mean that the complexity of biological systems has little to do with Darwinian evolution, as Wolfram contends. We would still have to ask why organisms obey some simple rules and not other rules, and the only possible answer would be that natural selection favors those rules that generate the kind of complex systems that improve reproductive fitness.

Wolfram even tackles the old conflict between belief in a deterministic view of nature and in the existence of free will. He suggests that free will is an illusion that arises from the apparent unpredictability of the complex behavior produced by those simple rules of biology that he imagines to govern the human organism. This is odd, because we certainly don’t attribute free will to other unpredictable complex phenomena like earthquakes or thunderstorms. Surely the impression of free will arises instead from our personal experience of actually deciding what to do, an experience that we are unwilling to suppose is enjoyed by earthquakes or thunderstorms. This is not to say that I have any enlightenment to offer about free will either, because I have never been able to understand the inconsistency that other people find between free will and a completely deterministic view of nature. Free will to me means only that we sometimes decide what we do, and we know that this is true by the same sort of mental experience that convinced Descartes that he existed, but we have no mental experience that tells us that our decisions are not inevitable consequences of past conditions and the laws of nature.

3.

Other scientists like myself study phenomena that may not be intrinsically very interesting, because they think that studying these phenomena will help them to understand the laws of nature, the rules that govern all phenomena. In such work, we tend to study the simplest possible phenomena, because it is in these cases that we can most easily calculate what our theories predict, and compare the results with experimental data to decide whether our theories are right or wrong. Wolfram makes it seem that physicists choose simple rather than complex phenomena to study because of long habit or mathematical flabbiness, but in seeking the laws of nature it is the essence of the art of science to avoid complexity.

My own work has been mostly on the theory of elementary particles, but I have never found these particles very interesting in themselves. An electron is featureless, and much like every other electron. Most of those of us who study elementary particles do so because we think that at this moment in the history of science it is the best way to discover the laws that govern all natural phenomena. Because of this special motivation, we don’t generally care whether we can calculate everything that happens to elementary particles in complicated situations, only whether we can calculate enough to check the validity of our theories. In collisions of elementary particles at moderate energy the energy of the collision goes into complex showers of particles. No one can predict the details of these showers, even where the underlying theory is known, and hardly anyone cares. At higher energies things are simpler: the energy goes into well-defined jets, each containing particles that travel in the same direction, in a way that can be calculated theoretically and compared with experiment to test our theories of elementary particles. It is the laws, not the phenomena, that interest us.

Unlike elementary particles, planets have historically seemed interesting for religious and astrological reasons. But it was the simplicity of planetary motions that allowed Newton to discover the laws of motion and gravitation. The planets move in empty space and to a good approximation under the influence of a single motionless body, the sun. Newton would never have discovered his laws by studying turbulence or snowflakes.

Wolfram himself is a lapsed elementary particle physicist, and I suppose he can’t resist trying to apply his experience with digital computer programs to the laws of nature. This has led him to the view (also considered in a 1981 article by Richard Feynman) that nature is discrete rather than continuous. He suggests that space consists of a network of isolated points, like cells in a cellular automaton, and that even time flows in discrete steps. Following an idea of Edward Fredkin, he concludes that the universe itself would then be an automaton, like a giant computer. It’s possible, but I can’t see any motivation for these speculations, except that this is the sort of system that Wolfram and others have become used to in their work on computers. So might a carpenter, looking at the moon, suppose that it is made of wood.

There is another reason for studying complex phenomena—not because the phenomena are interesting, which they sometimes are, or because studying complex phenomena is a good way to learn the laws of nature, which it isn’t, but because complexity itself is interesting. Maybe there is a theory of complexity waiting to be discovered, that says simple things about complex behavior in general, not just about the rule 110 cellular automaton or turbulent air flow or the human nervous system.

There are other examples of what I like to call free-floating theories, theories that are applicable in a wide (though not unlimited) variety of very different contexts. The theory of chaos, which has captured the public imagination, deals with systems, from the weather to the pebbles in the rings of Saturn, whose behavior exhibits an exquisite sensitivity to initial conditions. Thermodynamics, the science of heat, is a less trendy example. Concepts of thermodynamics like temperature and entropy are applicable to black holes as well as to steam boilers. A less familiar example is the theory of broken symmetry. Many very different substances, including superconductors, magnetized iron, and liquid helium, are governed by equations that have some symmetry, in the sense that the equations look the same from certain different points of view, and yet the substances exhibit phenomena that do not respect this symmetry.

There is a low-intensity culture war going on between scientists who specialize in free-floating theories of this sort and those (mostly particle physicists) who pursue the old reductionist dream of finding laws of nature that are not explained by anything else, but that lie at the roots of all chains of explanation. The conflict usually comes to public attention only when particle physicists are trying to get funding for a large new accelerator. Their opponents are exasperated when they hear talk about particle physicists searching for the fundamental laws of nature. They argue that the theories of heat or chaos or complexity or broken symmetry are equally fundamental, because the general principles of these theories do not depend on what kind of particles make up the systems to which they are applied. In return, particle physicists like me point out that, although these free-floating theories are interesting and important, they are not truly fundamental, because they may or may not apply to a given system; to justify applying one of these theories in a given context you have to be able to deduce the axioms of the theory in that context from the really fundamental laws of nature.

This debate is unfortunate, for both kinds of science are valuable, and they often have much to teach each other. My own work in elementary particle physics has benefited tremendously from the idea of broken symmetry, which originated in the study of the solid state but turned out to be the key both to understanding reactions involving particles called pi mesons at low energy and to the unification of some of the forces acting on elementary particles. The theory of complexity might also have lessons for elementary particle theory (or vice versa) but it is not likely to be fundamental in the same sense as elementary particle physics.

Lately particle physicists have been having trouble holding up their end of this debate. Progress toward a fundamental theory has been painfully slow for decades, largely because the great success of the “Standard Model” developed in the 1960s and 1970s has left us with fewer puzzles that could point to our next step. Scientists studying chaos and complexity also like to emphasize that their work is applicable to the rich variety of everyday life, where elementary particle physics has no direct relevance.

Scientists studying complexity are particularly exuberant these days. Some of them discover surprising similarities in the properties of very different complex phenomena, including stock market fluctuations, collapsing sand piles, and earthquakes. Often these phenomena are studied by simulating them with cellular automata, such as Conway’s Game of Life. This work is typically done in university physics departments and in the interdisciplinary Santa Fe Institute. Other scientists who call themselves complexity theorists work in university departments of computer science and mathematics and study the way that the number of steps in a computer calculation of the behavior of various systems increases with the size of the systems, often using automata like the Turing machine as specific examples of computers. Some of the systems they study, such as the World Wide Web, are quite complex. But all this work has not come together in a general theory of complexity. No one knows how to judge which complex systems share the properties of other systems, or how in general to characterize what kinds of complexity make it extremely difficult to calculate the behavior of some large systems and not others. The scientists who work on these two different types of problem don’t even seem to communicate very well with each other. Particle physicists like to say that the theory of complexity is the most exciting new thing in science in a generation, except that it has the one disadvantage of not existing.

It is here I think that Wolfram’s book may make a useful contribution. Wolfram and his co-workers have been able to show that numerous simple “class four” automata that produce complex behavior, like the rule 110 cellular automaton, are able to emulate each other. That is, by setting up a suitable input pattern of black and white cells in the rule 110 cellular automaton, one can produce the same complex pattern that would be produced by other class four automata, and vice versa. (In this emulation, blocks of cells in one automaton represent a single cell in the automaton being emulated.) What makes this particularly interesting is that one of the automata that can be emulated in this way is the universal Turing machine.³

The Turing machine is the most important automaton in the history of computer science, and the forerunner of today’s digital computers. It was invented in 1936 by Alan Turing, who in World War II became one of Britain’s ace cipher-breakers and was later the hero of Hugh Whitemore’s play Breaking the Code. Turing’s purpose was to answer a classic question of mathematical logic known as the Decision Problem: given some deductive mathematical system like arithmetic or Euclidean geometry or symbolic logic, is there any logical method that, when applied mechanically to any statement of that system, is guaranteed to decide whether that statement can be proved by following the rules of that system?⁴

To answer this question, the Turing machine was designed to capture the essence of mechanical logical methods. Just as a person going through a mathematical proof works with a string of symbols, focusing on just one at a time, the Turing machine works on a one-dimensional sequence of cells, each containing a symbol taken from some finite list, with only one “active” cell that can be read and possibly changed at each step. Also, to correspond to the fact that a person working out a proof would keep some memory of previous steps, Turing gave his machine a memory register, which can be in any one of a finite number of “conditions.”

Each type of Turing machine obeys a fixed rule that tells it at each step how to change the symbol in the active cell, how to change the condition of the memory register, and whether to move the active cell one step to the left or right, according to the symbol in the active cell and the condition of the memory register. It makes no difference what symbols we choose to use or what conditions are possible for the memory register; their significance arises only from the rules of the machine. The problem to be solved and the data to be used are fed into the machine as an initial string of symbols, and the answer appears as the string of symbols found when the memory register reaches a condition that tells the machine to stop.

Turing never actually built such a machine (though he did go on to build some special-purpose computers), but if you like you can think of the cells in a Turing machine as forming a paper tape, with the symbols just a sequence of colored dots on the tape, read and written by a scanning device that moves up or down the tape from one active cell to another. In this example the memory register is a simple mechanical pointer which can take any of two or more positions. The decision how to change the color of the active cell and the position of the memory register and how to move the tape is made according to the color of the cell being read and the position of the pointer, following rules that are hard-wired into the machine. A specific Turing machine is entirely characterized by the number of possible colors on the cells of the tape, the number of possible positions of the pointer, and by the rules wired into the machine.

The important thing about Turing machines is that some of them are universal. Turing was able to prove that any of these universal Turing machines could calculate or prove anything that could be calculated or proved by any other Turing machine. For instance, at least one of the huge number (96 to the power 48) of the possible Turing machines that use two colors and have a memory register with twenty-four positions is universal. Further, from the way that Turing machines were designed to imitate the way humans mechanically do calculations, Turing argued that universal Turing machines could calculate or prove anything that could be calculated or proved by any purely mechanical procedure. This is often called the Church-Turing thesis, because at about the same time the Princeton mathematician Alonzo Church reached similar conclusions about a more abstract but equivalent mathematical method of his own. Incidentally, Turing and Church found that the answer to the Decision Problem in most mathematical or logical systems is “no”: there is no mechanical procedure that is guaranteed to decide whether any given statement can be proved by following the rules of that system.

Since universal Turing machines can be emulated by the rule 110 cellular automaton, it follows that this cellular automaton, and all the other automata that can emulate it, are also universal—they can do any computation that can be done by any computer. The program for the calculation and the data to be used would be fed into a rule 110 cellular automaton as a pattern of black cells in the top row, and the answer would appear as a pattern on a lower row. Wolfram says that all these automata are computationally equivalent, but that is only true in a limited sense. The simpler the design of a universal computer, the more steps it takes to emulate each single step of a practical computer. This is why Dell and Compaq do not sell Turing machines or rule 110 cellular automata.

Wolfram goes on to make a far-reaching conjecture, that almost all automata of any sort that produce complex structures can be emulated by any one of them, so they are all equivalent in Wolfram’s sense, and they are all universal. This doesn’t mean that these automata are computationally equivalent (even in Wolfram’s sense) to systems involving quantities that vary continuously. Only if Wolfram were right that neither space nor time nor anything else is truly continuous (which is a separate issue) would the Turing machine or the rule 110 cellular automaton be computationally equivalent to an analog computer or a quantum computer or a brain or the universe. But even without this far-reaching (and far- out) assumption, Wolfram’s conjecture about the computational equivalence of automata would at least provide a starting point for a theory of any sort of complexity that can be produced by any kind of automaton.

The trouble with Wolfram’s conjecture is not only that it has not been proved—a deeper trouble is that it has not even been stated in a form that could be proved. What does Wolfram mean by complex? If his conjecture is not to be a tautology, then we must have some definition of complex behavior independent of the notion of universality. The pattern produced by the rule 110 cellular automaton certainly looks complex, but what criterion for complexity can we use that would tell us that it is complex enough for Wolfram’s conjecture to apply?

There is a well-known parallel problem in defining randomness. The most common precise definition of the randomness of a string of digits or of a sequence of black and white cells on a tape is that it is random if there is no way of describing it with a string of shorter length. The trouble is that according to this definition the string of digits in a number like the square root of two would not qualify as random, because it can be described very simply—it is the square root of two—even though it surely looks random. (Mathematica gives the first thirty digits as 1.41421356237309504880168872420.) In the same way, it wouldn’t do to define the output (shown in Figure B) of a cellular automaton like rule 110 with a single black cell in the top row as complex only if it can’t be described in simple terms, because it can be described in simple terms—it is the output of rule 110 with a single black cell in the top row. There are other definitions of randomness, such as the absence of correlations: the digits in the square root of two can be said to be random because, as far as is known, being given one digit at an unidentified decimal place tells you nothing at all about what the next digit is likely to be. Wolfram has not even begun to formulate a similar definition of complexity.

In fact, as he admits, for Wolfram the real test of the complexity of a pattern is that it should look complex. Much of his discussion of complexity is anecdotal, relying on pictures of the patterns produced by specific automata that he has known. In this, Wolfram is allying himself with one side in the ancient struggle between what (with much oversimplification) one might call cultures of the image and cultures of the word. In our own time it has surfaced in the competition between television and newspapers and between graphical user interfaces and command line interfaces in computer operating systems.

The culture of images has had the better of it lately. For a while the culture of the word had seemed to have scored a victory with the introduction of sound into motion pictures. In Sunset Boulevard, Norma Desmond recalls that in silent films, “We didn’t need dialogue. We had faces.” But now movies can go on for long stretches with no words, only the thunk of cars running into each other and the sizzle of light sabers. The ascendancy of the culture of the image has been abetted by computers and the study of complexity, which have made possible the simulation of complex visual images.

I am an unreconstructed believer in the importance of the word, or its mathematical analogue, the equation. After looking at hundreds of Wolfram’s pictures, I felt like the coal miner in one of the comic sketches in Beyond the Fringe, who finds the conversation down in the mines unsatisfying: “It’s always just ‘Hallo, ‘ere’s a lump of coal.'”

Wolfram’s classification of the patterns produced by cellular automata dates from the early 1980s, and the discovery that the rule 110 elementary cellular automaton is a universal computer was made in the early 1990s. Since then, none of this work has had much of an impact on the research of other scientists, aside from Wolfram’s employees. The strongest reaction I have seen by scientists to this new book has been outrage at Wolfram’s exaggeration of the importance of his own contributions to the study of complexity. Wolfram’s survey of the complex patterns produced by automata may yet attract the attention of other scientists if it leads to some clear and simple mathematical statement about complexity. I doubt if even Wolfram cares what picture is produced by the rule 110 cellular automaton after a billion steps. But if Wolfram can give a precise statement of his conjecture about the computational equivalence of almost all automata that produce complex patterns and prove that it is true, then he will have found a simple common feature of complexity, which would be of real interest. In the study of anything outside human affairs, including the study of complexity, it is only simplicity that can be interesting