So we have the classification of the CAs but this isn’t new.
Where can this new theory take us from here?
Most accounts of what is sometimes called "digital physics" are just long accounts of particular examples of CAs that produce interesting patterns. This is fun but it doesn't really advance the cause. A key observation might be that there is a connection between CAs and differential equations.
The whole of classical physics and much else is based on differential equations, which basically say how one or more quantities vary as a function of other quantities. For example the orbit of a planet around the Sun can be found by solving a differential equation that gives its velocity, i.e. the rate of change of its position, as a function of its position relative to the Sun.
You can say that differential equations have been the rules that classical and modern theories have used and to make the connection between them and CAs is obviously a big step in putting CAs into a more important position. Differential equations, when solved numerically, are obviously CAs.
For example, Laplace’s equation is one of the most commonly occurring differential equations and it can be solved by dividing the area up into a grid, assigning random values to start things off and then applying the following rule:
Replace the value in each cell by the average of its four neighbors.
This is called a “relaxation” method because if you keep applying the rule you eventually get a solution to Laplace’s equation.
This isn’t new but it is obviously just a generalised CA – the new value of the cell is just a function of its neighbors.
It is obvious that differential equations are CAs when you actually get down to working things out numerically. However it isn’t clear that thinking of them as CAs is actually helpful to either the theory of CAs or differential equations. It is a restatement of the fact that in physics the laws of nature can be cast as either differential equations or their equivalent integral equations.
Differential equations seem to be local as they specify what happens at one point and its neighborhood. Integral equations seem to be global as they make statements about what happens when you sum everything up, i.e. integrate. In fact differential equations have a global aspect in that they have to satisfy boundary conditions which are usually a long way from the points being considered.
The idea that CAs might provide a grand theory of everything focuses attention on the local interaction of things and suggests that the universe might actually be differential in some sense and that integral equations are some how an artifact.
Random Rules
Next we move on to randomness. The whole idea of randomness is a big problem for science in general and rules in particular. Put simply the problem is how can a deterministic set of rules create something that is random? Rules that create seemingly random behavior are interesting because randomness is the most complex behavior possible and the most difficult to reduce to something regular.
Of course all of this is linked to ideas like chaos, information and complexity theory. Randomness comes out in two distinct ways – from random initial conditions and from the nature of some types of rule. This is all very interesting and fun but nothing new if you look around.
Randomness from a simple rule?
The final part of Wolfram's book shows how the CA idea can work in other areas of science. It explains how a CA can account for the patterns on a seashell, how it can create other biological forms and model fluid flows. In the physics section we have some speculation on the discrete aspects of space and time but nothing that you could use to actually compute results or predictions.
An animal skin generated by a CA
CAs aren’t restricted to one or two dimensions- a shell generated by a CA.
Science yes but..
is this new approach a revolution?
Is it a new type of science as Wolfram's book claims?
It is important to make clear what is and what is not true.
The first things to say is that this is science – it’s an investigation of some very complex systems. The methods used to investigate the systems are entirely classical. We have experimentation, classification and description.
The missing element is prediction and, who knows, in time we might move on to understand the science of the CA so well that prediction is possible. Strictly speaking its not even a "new kind" of science because people have been working on this sort of idea for many years in complexity theory, CA theory, AI and more.
At the moment CA in physics and as a theory of the universe is interesting but not particularly rewarding. The universe might well be a computer but we still don't have much of a grip on its hardware or its software - and how to program it?
There's a good question.
Further reading and online resources
While A New Kind of Science is the best known of the books proposing that CAs might be a theory of everything, it’s a shame not to ignore some of the really good alternatives, links to all of which are in the right-hand panel above.
My favourite is currently out of print but you can still find it second hand: “Enter the Complexity Lab: Where Chaos Meets Complexity”, by William Roetzheim. Any of the many popular science books with words like “Complexity”, “Chaos”, or “Artificial Life” in the title are also worth looking at.
If you want to read a good book on the ideas but at a more academic level try: “Nonlinear Physics for Beginners: Fractals, Chaos, Pattern Formation, Solitons, Cellular Automata and Complex Systems” by Lui Lam.
For CAs and biology try: “Modeling Nature: Cellular Automata Simulations with Mathematica” by R.J. Gaylord & K. Nishidate.
If you just want some software to play with then download Cellab, and lots of other interesting software, from:
We have been searching for the theory of the Universe, the Grand Unified Theory, or GUTs if you must, for a long time. Physicists have persuaded governments to spend billions on particle accelerators to help provide data but could it be that the answer lies in your PC. Could the secret be that the Universe is just a computer…
Stephen Wolfram, the man who among other things gave use the maths program Mathematica, certainly thinks that computing is the key to everything. Early in 2001 he published a huge book, “A New Kind of Science”that outlined his ideas. I say “he” published because unlike most books claiming to make a contribution to science it wasn’t peer reviewed before publication. In fact the first that the scientific community knew of his ideas was when the book was published. Given this fact, and the strange style of the book, more of which later, it isn’t surprising that it caused something of a stir. The newspapers contained headlines to the effect that Wolfram was the new Newton or the new Einstein – but what do newspapers know! Some readers have claimed to have had their eyes opened to a new way of seeing. Others have claimed that it is just regurgitated stuff with some mysticism thrown in. To find out which it is we have to look a little closer at some of its central ideas.
***BOOK.JPG
**details
A New Kind of Science £40
Stephen Wolfram
Wolfram Media Incorporated; ISBN: 1579550088
Rules, programs and theories
The first question we have to answer is what computers have to do with theories? A scientific theory of something is a lot like a program. It explains the underlying mechanisms that make the usually complex phenomena look simple. Consider for a moment the theory of gravity. At first we have a lot of very different phenomena to explain, apples falling, moon orbiting the earth etc.. but then we have a single theory – i.e. that all matter attracts all other matter – which explains the lot. Consider what it would mean if a theory was a complex as the phenomena it accounted for. There would be no point in having the theory because the phenomena themselves would be just as compact a description.
So a theory is an explanation which is considerably simpler than the phenomenon it explains. Of course this begs the question of what exactly we mean by “explanation” or by “simpler” but you can see what the general idea is. You can also probably see that a theory is like a set of rules or instructions for generating the phenomenon. If you wanted to you could take the theory and use it to create a simulation of the real phenomenon – an accurate model of the moon rotating around the earth say. The point is that a theory is a prescription or recipe for producing the phenomenon which is considerably simpler than the phenomenon it produces.
Now you might begin to see the similarity between a theory and a computer program. A program is a set of rules that makes a computer produce some behavior and that behavior can be a lot more complicated than the program might lead you to believe. This is more or less the total content of Stephen Wolfram’s new book but he presents it in more than 1000 pages. Of course this is something of an over-simplification in that there is a lot more discussion and, dare I say it, fun stuff in the book than in my one-line version.
This view of what a theory is also answers the question “is the Universe just a big computer?” Of course it is. If theories are programs the Universe must just be a big computer that runs the program that corresponds to what we see around us. This conclusion should now seem fairly obvious but it is worth noting that not everyone agrees with it. There are two main counter-arguments to the idea. The first is that there might not be a theory of everything and hence no program. After all why should the Universe be built in such a way that a description of it is actually simpler than it is?
There are a number of arguments that suggest that the Universe probably does have a theory but the odd thing is that the same arguments can be used to show why it doesn’t! For example, if the Universe has no program how does it decide what is going to happen when two particles collide? If you believe in the program it is obvious that the Universe computes what happens next by just letting it happen. If you don’t believe then you can simply say that what happens, happens and it doesn’t necessarily prove that there is logic, let alone a simpler description to be discovered! At the moment at least it seems to be a matter of taste how you look at the existence of a theory of everything but since we have been lucky enough to find ever better theories so far why not continue to believe that this might just happen.
Notice that none of this discussion is invalidated by the non-determinism contained in quantum mechanics. It is fine for the program that the universe follows to be based on probabilities. Quantum mechanics is just as much a theory and just as much a program as Newtonian mechanics. The real problem is that we have difficulty really believing in a Universe where precisely what happens next isn’t determined by the precise conditions just before it happened. To rearrange Einstein’s quote it really is OK for God to play dice with the Universe – it is still a program.
Cellular Automata
If we want to build a theory based on programs we need to examine the way programs really work – and I’m not talking about Windows! We need to look at the simplest sorts of programs that might account for the behavior of the more fundamental things of the Universe. There are a number of possible ways we could go about this – Turing machines, Grammars, recursive logic and so on but the one that is used in “A New Kind of Science” and central to its explanation is the Cellular Automata, CAs.
Not only are CAs interesting models of program behavior they are also a lot of fun. What you might not realise by their being brought into the public eye by Wolfram’s book, they were invented in the 1940s by Ulam and Von Neumann. They were interested in finding computer-like models of self-reproducing machines that had the characteristics of living organisms.
A CA is basically a rule that a set of agents can apply locally. A full mathematical definition is possible and while such a modelwould be more complete it would also be more difficult to follow. The agents, or whatever you want to call them, are usually arranged in some sort of pattern – often a grid – and they can usually only see the agent that they are close to and each agent can usually be in one of a number of states – often either zero or one. Each agent is equipped with a rule, usually the same rule, and this tells them how to change their state according to their current state and the state of nearby agents. Usually the changes occur altogether on the tick of a clock that all of the agents can hear.
You might just recognise the description of a well-known computer game called Life, devised by John Conway, in this slightly abstract formulation of a CA and indeed Conway’s Life is an example of a much-studied CA. If you would like to see how CAs might be useful consider a grid of agents which are initially set to either black or white as shown:
**FIG1.TIF
The rule that each of the agents are going to obey at the next clock tick is the following:
If you are black and have a white neighbor then stay black otherwise turn white.
Where in this case a neighbor is defined to be any agent horizontally or vertically adjacent.
What do you think the result of this simple rule is going to be when all of the agents obey it? What might surprise you is that this rule only leaves the outline of the original shape black.
***FIG2.TIF
In other words the rule succeeded in picking out the outline of the shape. Notice that nothing but local information was used by any of the agents and yet it succeeded in extracting something that we might think of as global, i.e. the outline. It’s the same sort of phenomenon as the displays of pictures and patterns that happen at sporting events when members of the crowd are given cards to hold up at specified times. A global pattern can result from the application of a local rule. Putting this another way, it should be clear that a simple rule can lead to complex behavior. The rules for Life for example are very simple but we are still studying the behaviors that it can exhibit.
Make it simpler
The problem with 2D Cas, like the one described above and like Life, is that they are just too complicated to analyse in detail. The first important contribution that Wolfram made to the theory was to reduce the situation to the point where it could be analysed. He decided that a one-dimensional CA would be worth investigating. The idea of a 1D CA is no different from a 2D one but we start off with a line of agents and at the next tick the line is replaced by a new line determined by the rule that is being followed. As this is only a 1D arrangement we don’t actually have to replace the existing line, just display the new line underneath so building up a complete pattern of the development of the CA. It’s also possible to specify the rule in terms of the color of the agent, its two neighbors and the color of the new cell just below. For example the pattern:
***FIG3.TIF
specifies a rule that if an agent is white and has two black neighbors then the cell below should be black.As there are only eight possible arrangements of neighbors a complete rule that specifies exactly what should happen in any situation only has to list if the result of each of the eight is black or white. By thinking of black as 1 and white as 0 you can give each neighbor patter a number between 0 and 7 and then read off the resulting black or white cell on the next row as a set of eight zeros or ones i.e. a binary number. This can be used as an index to specify the rule.
***FIG4.TIF
This means you can refer to any of the 256 rules that are possible in a 1D CA by number. This in itself is something of a conceptual breakthrough because now you can begin to think about classifying the behavior of each of the possible rules. This is exactly what a biologist would do when confronted by a new biosphere. Once you have classified what you are looking at you can start to see patterns and make theories up about what you are looking at. Without classification you are simply looking at an undifferentiated mess, no matter how interesting it might appear.
Wolfram examined all 256 of the rules by simulating them and discovered that there were four classes of behavior. Class 1 behaviors were boring, just resulting in all on or all off states. Those in Class 2 were also fairly boring and resulted in stable states, only slightly more interesting than Class 1. Class 3 produced disordered behavior – random triangles and “video noise”. Finally Class 4 displayed complex behaviors that included “Life-like” patterns. Class 4 patterns demonstrate that even 1D CAs have enough complexity to produce interesting behavior.
**RULE90.TIF
Rule 90 looks to produce a nice regular pattern so its in Class 4.
Many of these 1D CAs produce interesting patterns and they are fun to play with. Not quite as impressive as fractals from a graphics point of view but given the amount you put in you seem to get a lot out – and of course this is the point! If you go back to the discussion about rules and theories you will see that this is exactly what should interest us. When a simple rule produces complex behavior then it could well be a theory of something if not everything!
Where next?
So we have the classification of the CAs but this isn’t new. Where can Wolfram’s new theory take us from here? The first thing to say is that in the first three chapters of the book we have an account of many different types of CA that go beyond the much studied 1D example. Put simple we are presented with lots and lots of further examples, which are often pretty and good fun but don’t really take us any further. At one point we have the connection drawn between CAs and differential equations. The whole of classical physics and much else is based on differential equations, which basically say how one or more quantities vary as a function of other quantities. For example the orbit of a planet around the Sun can be found by solving a differential equation that gives its velocity, i.e. the rate of change of its position, as a function of its position relative to the Sun. You can say that differential equations have been the rules that classical and modern theories have used and to make the connection between them and CAs is obvious a big step in putting CAs into a more important position. The only problem is that differential equations, when solved numerically are obviously CAs.
For example, Laplace’s equation is one of the most commonly occurring differential equations and it can be solved by dividing the area up into a grid, assigning random values to start things off and then applying the following rule:
Replace the value in each cell by the average of its four neighbors.
This is called a “relaxation” method because if you keep applying the rule you eventually get a solution to Laplace’s equation. This isn’t new but it is also obviously just a generalised CA – the new value of the cell is just a function of its neighbors.
It is obvious that differential equations are CAs when you actually get down to working things out numerically. However it isn’t clear that thinking of them as CAs is actually helpful. If it adds anything I for one can’t see what it is.
Next we move on to randomness – yes randomness. The whole idea of randomness is a big problem for science in general and rules in particular. Put simply the problem is how can a deterministic set of rules create something that is random? Rules that create seemingly random behavior are interesting because randomness is the most complex behavior possible and the most difficult to reduce to something regular. Of course all of this is linked to ideas like chaos, information and complexity theory and Wolfram rediscovers all of this. He notes that randomness comes out in two distinct ways – from random initial conditions and from the nature of some types of rule. This is all very interesting and fun but nothing new if you look around.
***RULE30.TIF
Randomness from a simple rule?
Finally the book deals with possible applications of CA idea in other areas of science. It is explained how a CA can account for the patterns on a seashell, how it can create other biological forms and model fluid flows. In the physics section we have some speculation on the discrete aspects of space and time but nothing that you could use to actually compute results or predictions. While Wolfram might argue that this isn’t really a criticism because numerical predictions are part of “old science” it is difficult to see what value any theory that doesn’t provide precise predictions could have?
And that’s about as far as it goes.
***PIGMENT.TIF An animal skin generated by a CA
***SHELL.TIF
CAs aren’t restricted to one or two dimensions- a shell generated by a CA.
Science yes but..
Given that the book is called “A New Kind of Science” and it is being claimed that this is a revolution, it is important to make clear what is and what is not true. The first things to say is that this is science – it’s an investigation of some very complex systems. The methods used to investigate the systems are entirely classical. We have experimentation, classification and description. The missing element is prediction and, who knows, in time we might move on to understand the science of the CA so well that prediction is possible.
What is more, not only is this not a new “kind” of science, much of it isn’t new at all. Because the book is written without the usual academic niceties of references to other peoples work it can be very difficult to find out what is new and what is not. Many of the practical examples given were actually first suggested by other people and there is no shortage of people working in the same area covered by the book. When you look into the wider areas of chaos theory, artificial life, computational information theory and so on you also find most of the more philosophical ideas discussed in detail. There’s even a great deal of existing work on the idea of a “digital” physics that goes well beyond what is being offered in this book.
So is it science? Yes.
Is it new? No.
Is it fun? Yes.
Is it important? Probably.
Is the Universe just a big computer? Your guess is as good as mine.
***BOX
Alternatives
While “A New Kind of Science” is getting all the publicity, it’s a shame not to mention some of the really good alternatives to it that have been available for a while. My favourite is currently out of print but you can still find it second hand: “Enter the Complexity Lab: Where Chaos Meets Complexity”, by William Roetzheim, Sams; ISBN: 0672303957. Any of the many popular science books with words like “Complexity”, “Chaos”, or “Artificial Life” in the title are also worth looking at.
If you want to read a good book on the ideas but at a more academic level try:“Nonlinear Physics for Beginners: Fractals, Chaos, Pattern Formation, Solitons, Cellular Automata and Complex Systems” £?? by Lui Lam World Scientific Publishing; ISBN: 9810201419.
For CAs and biology try: “Modeling Nature: Cellular Automata Simulations with Mathematica” £?? byR.J. Gaylord, K. Nishidate Springer-Verlag New York Inc.; ISBN: 0387946209.
If you just want some software to play with then download Cellab, and lots of other interesting software, from:
Click on a chapter and repeat any experiments you want to.
As well as the book there is also the software of the book. All of the experiments that Wolfram carried out were performed using Mathematica – of course! Now you too can have the code used to perform all the experiments nicely packaged and presented in the form of “A New Kind of Science Explorer”. This is available for Windows and the Mac and makes use of the Mathematica computational engine to show you graphics corresponding to most of the figures in the book.
It is very easy to use, perhaps just a little too easy. Every experiment comes ready setup with interesting values of the parameters and precomputed. If you have a fast computer then clicking on the “Generate” button just makes the image flash. You only really get into something new if you start changing the parameters and investigating what happens. Although the programs are all written in Mathematica, you don’t get the source code even if you happen to be a Mathematica user. So there is a limit to what you can do unless you are prepared to re-write everything from scratch – which in most cases isn’t difficult.
The interface gives you access to the experiments in the order in which they occur in chapter order. Clicking on any Chapter link takes you to a page of experiments as they occur in the book. What this means is that this is very much an accompaniment to the book and it makes you wonder why it just wasn’t bound into the back jacket. If you want to play with CAs as described in the book then its probably worth it, although at £60 its not exactly cheap.
**BOX Who is Stephen Wolfram?
If you want to know about Stephen Wolfram then there is an official website where you can get minute details of his life and work - www.stephenwolfram.com. Born in London in 1959, educated at Eton and then Oxford and Caltech he published his first scientific paper at 15. He studied a wide range of subjects but most of his early work was on particle physics and cosmology but he was also interested in a wide range of maths and computing in general. In 1979 he began the construction of SMP, a computer algebra system which was released commercially in 1981, the year he won the MacArthur Prize. Soon after he began to study Cellular Automata (CA) and published a number of papers which revolutionised the area.
In 1986 he started Wolfram Research and launched the first version of Mathematica – a program for doing mathematics. At this point Wolfram appears to have abandoned his academic career. Despite his claims to still be working on the study of complexity, nothing was published. His papers on physics stop in 1983 and his papers on cellular automata stop in 1988. He himself claims that all his efforts from 1987 went into the magnum opus that is the book “A New Kind of Science”. More specifically he claims to have spent the 10 years from 1991 working on the book and being CEO of Wolfram Research.
What is surprising about this progress is that if you look back at Wolfram’s early research papers they reveal the fact that he was a promising theoretical physicist. His papers are very mathematical and very mainstream. Even his papers on Cellular Automata are mathematical and academic. However the book “A New Kind of Science” is quite different. It is not really very technical and it is clearly aimed at a very different audience to an academic paper. Wolfram claims that reaching a wider audience was indeed his intention but this makes it all the less reasonable to see the book as a continuation of his academic research. The academic papers stop in 1987 and it isn’t reasonable to say that the “A New Kind of Science” represents the same sort of work in the following 10 plus years. In fact, given Wolfram’s abilities it is difficult to see why the book took anywhere near that length of time – 2 years seems more reasonable. (The first article on Wolfram’s work that mentions a new approach to science is dated 1997.)
So what happened? This is of course a question that is impossible to answer but it seem likely the Wolfram became disillusioned with academic science and more interested in the commercial success of Mathematica – a storyline that has curious parallels with Bill Gates and Microsoft. After a while, though, it also seems clear that Wolfram would get bored with grubby commerce and want to do something really important. What better then than to pick up with something simple but potentially of huge significance? Being out of touch with the academic world and peer reviewed publication and being CEO of a big company for 10 years also explains why he choose to self-publish a book rather than get back into the academic rat race. Mind you he is still making money out of the enterprise which is again very non-academic.
When you look at his early work and compare it to A New Kind of Science it is difficult to believe that it’s the same person writing it.
