COMPUTING SCIENCE

# Computational Creationism

# The World as Machine

The vision of a cosmic computer has inspired literary and philosophical speculation, but the roots of the idea lie in the everyday practice of computer science. It's the sort of notion that might occur to anyone who spends enough time twiddling bits—especially late at night in a caffeine frenzy. There are two versions of the idea, one belonging to the hardware hacker and the other to the software wizard. The distinction between them is this: In the first case the world is *computing something*; in the second the world is computed *by* something.

The hardware variant springs from the observation that even though computers are complicated and finicky devices, you can build one out of almost anything. The beige box on your desk runs on microelectronic circuits, but in principle all of its functions could be performed by hydraulic or pneumatic or photonic devices. Danny Hillis and his friends built a computer out of Tinker Toys and string. Leonard Adleman performed a computation with strands of DNA in a test tube. Other schemes would compute with enzymes or living bacterial cells or spinning atomic nuclei.

The counterpoint to all this technological diversity is theoretical equivalence. Provided that a machine never runs out of memory and that you're willing to wait long enough for an answer, almost all computers can compute exactly the same set of mathematical functions (and they fail on the same set of uncomputable problems). The proof of equivalence relies on the idea of an emulator: a program that allows one machine to run programs written for another. The usual practice is to show that a given computer can emulate a Turing machine, the theoretical computing device invented by Alan Turing in the 1930s, whose underlying technology is the marking of paper tape.

Should we be surprised that so many kinds of machines can all compute the same things? Forty years ago Eugene Wigner wrote of "the unreasonable effectiveness of mathematics in the natural sciences," asking why differential equations should work so well to describe the physical world. The converse question is just as intriguing. Why do all the resources of the material world lend themselves so readily to computing mathematical functions? Why is it you can pick up just about any spare parts lying about the universe and turn them into logic gates or binary adders?

One answer is that the world *is* a computer. It was designed to have exactly this property. The most celebrated speculation along these lines is found in Douglas Adams's *Hitchhiker's Guide to the Galaxy*. Adams reveals that the planet Earth was constructed as a gigantic computer meant to carry out a five-billion-year inquiry into "the meaning of life, the universe and everything."

Others imagine computers on an even grander scale, reaching beyond this little wet rock of ours to fill the entire universe. One visionary of the cosmos-as-computer was the late Konrad Zuse, who was also among the earliest of all hardware hackers (he had a digital computer up and running years before ENIAC). Zuse conjectured that the ground fabric of the universe might be a kind of computer called a cellular automaton. This same idea has been pursued with even greater vigor by Edward Fredkin, a free spirit of computer science who led the Information Mechanics Group at MIT in the 1980s.

A cellular automaton is an array of many simple processors arranged in a lattice. Think of a tiled floor with a processor on every tile. Each processor (or cell) has only a finite number of possible states and can communicate with only a finite number of neighboring cells. At each tick of a master clock, every cell chooses its next state according to a fixed "transition rule." The best-known example of a cellular automaton is the Game of Life, invented 30 years ago by John Horton Conway of Princeton University. The cells in Life have two states—alive or dead—and the transition rule simply counts the number of living neighbor cells.

At first glance a cellular automaton doesn't look much like our world. For one thing, our space appears to be continuous: Where are the cells? Fredkin suggests they are simply too fine to see—perhaps as small as the Planck scale, 10^{–33} centimeter. A subtler objection is that our world teems with fast-moving particles, such as electrons and protons whizzing around inside atoms, whereas only signals travel through the lattice of a cellular automaton; the cells are immobile. Here too Fredkin has an answer. A fairly simple transition rule creates packets of information that glide frictionlessly through the cellular automaton like idealized billiard balls, rebounding elastically when they collide. Maybe what we perceive as motion has a similar basis, and elementary particles are made of nothing more substantial than information.

Cellular automata are a natural choice for a computational universe because they require only local communication between nearby processors. There is no need for wires or other long-distance rigging. The deepest laws of nature also seem to be strictly local, making for a good match between physics and computation. These aspects of cellular automata—the dual ideas of "programmable matter" and "computable physics"—have been explored in great detail by Tommaso Toffoli and Norman Margolus, who were both members of the Information Mechanics Group.

In the absence of compelling evidence—and this is a case where we have a compelling absence of evidence—why would anyone choose to believe that the universe is busy churning out calculations? The Douglas Adams fantasy suggests the allure of a hidden purpose. Why are we here? To compute the meaning of life, the universe and everything. All those events that seem so random and pointless will be explained when the cosmic computer prints out the final answer. (Either that, or the computer crashed ages ago, and we've been waiting all this time for someone to reboot us.)

Fredkin's vision of the universe as cellular automaton is a little different. His computer isn't necessarily searching for bits of wisdom; it may simply be computing its own next state, over and over, with no goal in mind. Yet Fredkin too wonders about invisible undercurrents and mysteries of purpose. He points out that since most of space is empty, most of the cells in the automaton have nothing to do most of the time. He calls this "the problem of the missing workload"; by his estimate, the computing capacity of the universe is greater than needed by a factor of 10^{63}. "Either something else is going on . . .," he comments, or "God was incompetent on a scale that boggles the mind."

EMAIL TO A FRIEND :

**Of Possible Interest**

**Feature Article**: In Defense of Pure Mathematics

**Feature Article**: Candy Crush's Puzzling Mathematics

**Computing Science**: Clarity in Climate Modeling