Cellular automata can be simulated in software, or built as highly parallel hardware. Stephen Wolfram of Princeton believes they provide simple but powerful computer models of the physical world.
Cellular automata have been known since John von Neumann investigated them in his search for self-reproducing systems. Most research in the subject has centred on two-dimensional cellular automata, where the cells are spaced regularly on a plane surface.
At each 'tick' of the clock, every cell switches to a new state determined only by its former state and the states of its neighbours.
For the past few years Stephen Wolfram, an English theoretical physicist, has been investigating the behaviour of simpler arrays where the cells are lined up in a single row. With his colleagues at the Institute for Advanced Study in Princeton, New Jersey, Wolfram has shown that these one-dimensional cellular automata exhibit almost the same interesting behaviour as that seen in two dimensions.
Wolfram still expresses amazement at the way simple rules, and simple beginnings, can lead to enormously complex events. 'I find it really remarkable that such simple things can make such complicated patterns,' he says.
Some rules give rise to fractal patterns, which reproduce themselves repeatedly on ever larger scales. On other occasions the evolution is chaotic, with no visible regularity either in space or in time. Yet other rules yield a harvest of static and moving 'objects' which might be used to construct a universal computer within the cellular automaton microworld.
Wolfram believes that cellular automata can provide useful models of natural systems.
Cellular automata often give rise to areas of single colour or uniform texture. Wolfram refers to these as 'phases', the word used by physicists for specific solid, liquid or gaseous forms of matter.
Sometimes a 'seed' of a particular phase, injected into a cellular automaton, will grow and grow, like a seed crystal dropped in a crucible of molten metal.
The branching (dendritic) crystal growth seen in snowflakes has been modelled at Princeton by Norman Packard, using a two-dimensional cellular automaton. Wolfram says this is the best-yet cellular automaton model of a physical process.
Fluid flow, electromagnetic fields and other physical systems are usually modelled with partial differential equations. Quantities change smoothly with space and time.
Occasionally an exact solution can be found by manipulating the equations algebraically and plugging in numerical values at the end. More commonly, partial differential equations are solved approximately, by number-crunching techniques which would be very laborious without computers.
Smooth, continuous space and time are approximated by a closely spaced mesh of points. At each point, in a typical numerical solution, physical quantities such as temperature, pressure, or velocity are represented by 32-bit numbers.
A cellular automaton model would probably use the same fine mesh of points in space and time, or possibly a finer one. But the amount of information stored for each point would be drastically reduced, perhaps to only two or three bits.
The resulting model can be run much faster than a model based on partial differential equations and floating point variables. But it will be of little use if it no longer behaves like the physical world.
Wolfram believes that a cellular automaton can be 'a good first model' of a physical system. 'My belief is that in fact it will turn out that most of the qualitative and many of the quantitative aspects of partial differential equations are preserved even in the limit of extreme discretisation,' he says.
The vertical midline of the triangle records the subsequent history of the original non-zero cell. The sequence of cell values along this midline often appears completely random.
'If you run all kinds of statistical tests on it, they just say it's random, which I find rather interesting because it clearly isn't random in the sense that it was made by this extremely simple procedure,' says Wolfram.
There are some cellular automata whose behaviour can never be reduced to a formula. The only way to find out what they do is to simulate them step by step. No simpler computation provides a significant short cut.
This property is known as computational irreducibility. Universal computers such as general Turing machines are among the systems which possess it.
At least two cellular automata are known to be universal computers. They can be programmed to solve any computer-soluble problem, by setting up an appropriate initial configuration of cells.
But a system need not be a universal computer, to be computationally irreducible. Though he cannot yet prove it, Wolfram believes that computational irreducibility is widespread among cellular automata and other systems with complicated behaviour. Turbulent fluid flow, and other systems exhibiting 'chaotic' behaviour are obvious candidates.
This means that certain questions about cellular automata--and about the physical world--may be intrinsically difficult or even impossible to answer.
Suppose you wanted to know whether a particular cellular automaton will ever halt. The obvious way to find out is to start the system and see what happens.
With luck, it will either halt, or go into a loop (proving it never halts) within a fairly short time. But it may go on for a month without doing either of these things. It may go on for a million years. In fact, no finite computation can guarantee to answer the 'halting problem'.
If the system is computationally irreducible, there is no short cut to knowing its ultimate fate. The halting problem must then be one of the undecidable problems whose existence was first proved by the logician Kurt Gödel.
Wolfram expects that physics, like mathematics, may prove to be full of undecidable problems. 'It would be a very remarkable thing if the kind of mathematics that crops up in theoretical physics is just that special kind that happens to avoid the pieces where there are undecidable propositions,' he says.
It is perhaps no surprise that we cannot always expect to know the infinite future. But even the next year, or the next microsecond in the life of a computationally irreducible system, may be impossible to predict in practice.
Many problems appear to be intractable in the sense that the computer time or memory size needed to solve them grows explosively as 'bigger' versions of the problem are attempted. Wolfram argues that intractability, like undecidability, is likely to be common in the physical world.
There are some experiments, he suggests, that theory simply can't handle. 'You just have to try it and see,' he says.
Wolfram thinks it unlikely that genetic engineers will ever be able to sit at a computer terminal and design new creatures to order. He points out that there may be no quick way to predict the effect of a particular modification to the creature's DNA.
'If this process of getting from the DNA to the finished creature is computationally irreducible,' he says, 'then you expect that effectively the only way to find out what the creature looks like overall is to let the thing grow and see what it looks like.'
Scientists have always sought to reduce the behaviour of the universe to simple laws. But cellular automata demonstrate graphically that simple laws can lead to extremely complex behaviour. This behaviour not only looks complex, it is complex in the absolute sense that a vast amount of computation is needed to predict or 'explain' it.
Wolfram believes that cellular automata will help scientists to explore the areas where the rules are simple but the calculations are not. This belief rests on two hunches.
One hunch is that much of the real world is computationally irreducible. That is to say, if we want to understand it we have no alternative to doing very large computations.
The other hunch is that cellular automata have the power to handle these computations. At the moment, the constructions that have been used to make cellular automata function as universal computers are elaborate, contrived, and of no practical utility.
In practice, a cellular automaton need not be a universal computer to provide a useful model of physics. But it will be a great boost to the morale of Wolfram and his colleagues, if some very simple cellular automaton can be proved, by natural and elegant methods, to be a universal computer.
Wolfram believes intuition and serendipity may be more productive than a carefully planned assault on this problem. The 'game of life', a two-dimensional cellular automaton, sparked a craze among computer hackers in the 1970s.
Bill Gosper, then at MIT, managed to prove that 'life' is a universal computer. The only one-dimensional cellular automaton known to have universal powers has 18 states per cell. Wolfram is sure that a much simpler candidate can be found, and he thinks that microcomputer users could join in the search. 'There are a lot of kids and hackers out there,' he points out.
|
Copyright (C) 1996, 1997, 1998 Stephen Wolfram |