A New Kind of Science 530
| A New Kind Of Science | |
| author | Stephen Wolfram |
| pages | 1197 (plus 62 page index) |
| publisher | Wolfram Media, Inc. |
| rating | 10 |
| reviewer | cybrpnk2 |
| ISBN | 1-57955-008-8 |
| summary | A long awaited treatise that cellular automations, not mathematics, holds the key to understanding reality |
First things first - have I read this book? Hell, no, and if anybody else says THEY have in the next year, they're lying thru their teeth. This book is so dense that if Wolfram had added a single additional page, the whole thing would have imploded into a black hole. That's got to be the only reason he quit writing and finally went to press.
I've been waiting for years for ANKOS to come out. I ordered my copy Tuesday when it was released, got it on Thursday and I've been skimming it like mad since. To give you some idea of how engrossing this book is, I was reading it Friday morning at 4 AM in the bathroom of a Motel 6, curled up in a bedspread on the tile floor to keep from disturbing my wife and stepdaughter during a trip to my stepson's graduation. I've got four college degrees, one in math and two from MIT, and bottom line - this sucker's gonna take a while to digest. However, it's theoretically straightforward enough that anybody with a high enough level of obsession and a few years to stay glued to it can follow it in its entirety. In ANKOS, Wolfram certainly comes across as arrogantly cocky but in the final analysis is he a crank or a revolutionary genius? Who knows, but it's going to be a new nerd pastime for the next decade to argue that point.
ANKOS is 1250+ pages divided into 850 pages of breezy exposition followed by 350 pages of fine-print notes. The exposition is composed of 12 chapters and the notes have about a paragraph per page of topic- and name-dropping technobabble to let you know where to go next for more details on whichever of Wolfram's tangents strike your fancy. Topping the whole thing off is a 60+ page index with thousands of entries in even smaller typeface than the notes.
Despite its length, ANKOS is not a rigorous mathematical proof of anything as much as it is a superficial survey of a vast new intellectual landscape. And what a landscape Wolfram has laid before us. It's all about cellular automations, which have traditionally been relegated to the realm of mathematical recreations. Start with a black square in the center grid square (cell) on the top line of a sheet of graph paper. Think up a few rules about whether a square gets colored black or white on the next line down depending on the colors of its neighbors. Apply these rules to the squares on the next line of the sheet of graph paper. Repeat. Watch what happens. Sounds simple. It isn't.
The first short chapter outlines Wolfram's central thesis: That three hundred years of mathematics based on the equals sign have failed to provide true insight into various complex systems in nature, and that algorithms based on the DO loop can succeed in this endeavor where mathematics has failed. The reason, claims Wolfram, is that deceptively simple algorithms can produce heretofore undreamed of levels of complexity. He claims that while frontier intellectual efforts such as chaos theory, fractals, AI, cybernetics and so forth have hinted at this concept for years, his decade of isolation studying cellular automata has taken the idea of simple algorithms or rules embodying universal complexity to the level of a new paradigm.
The second chapter outlines what Wolfram calls his crucial experiment: the systematic analysis of the 256 simplest rule sets for the most basic cellular automatons. He discovers this "universe" of rules is sufficient to produce his four so-called "classes" of complex systems: order, self-similar nested patterns, structures and most importantly, true randomness. The first two lead to somewhat familiar checkerboard-type patterns and leaf-type fractals; the last two, unforeseen unique shapes and unpredictable sequences. Wolfram stresses that the ability of simple iterative algorithms to produce complex and unique non-fractal shapes as well as truly random sequences of output is in fact a revolutionary new discovery with subtle and profound implications.
The third chapter expands his initial 256-rule-set universe of simple algorithms with many others Wolfram has researched for years in the dead of night while others slept. Rule sets involving multiple colors beyond black-and-white, rule sets that update only one grid square instead of a whole row, rule sets that embody full-blown Turing machines, rule sets that substitute entire sets of patterned blocks into single grid cells, that tag end point grid squares with new patterns, that implement "registers" and "symbols" - Wolfram has examined them all in excruciating detail. And no matter how complex the rule set is he explores, it ends up generating still more and more unexpected complex behavior with many notable features as the rule sets are implemented. This ever-escalating spiral of complexity leads Wolfram to believe that cellular automatons are a viable alternative to mathematics in modeling - in fact, embodying - the inherent complexity of the natural world.
In chapter four, he begins this process, by linking cellular automatons to the natural world concept of numbers. Automatons that multiply and divide, that calculate prime numbers and generate universal constants like pi, that calculate square roots and even more complex numerical functions like partial differential equations - Wolfram details them all. Who needs conscious human minds like those of Pythagoras or Newton to laboriously work out over thousands of years the details of things like trigonometry or calculus? Set up dominos in just the right way, flip the first one and stand back - nature can do such calculations automatically, efficiently and mindlessly.
Chapter five broadens the natural scope of cellular automations from one-dimensional numbers to multi-dimensional entities. Simple X-Y Cartesian coordinates are left behind as Wolfram defines "networks" and "constraints" as the canvas on which updated cellular automatons flourish - always generating the ever-higher levels of complexity. More Turing machines and fractals such as snowflakes and biological cells forming organs spontaneously spring forth. So far we've seen some really neat sleight-of-hand that Martin Gardner or Michael Barnsley might have written. But we're only on page 200 of 850 with seven chapters to go, and Wolfram is just now getting warmed up.
Chapter six is where Wolfram begins to lay the foundation for what he believes is so special about his insights and discoveries. Instead of using rigid and fixed initial conditions as the starting points for the cellular automations he has described, he now explores what happens using random and unknown initial conditions in each of his previously defined four "classes" of systems. He finds that while previously explored checkerboard (Class 1) and fractal (Class 2) systems yield few surprises, his newly-discovered unique (Class 3) and random (Class 4) cellular automaton systems generate still higher levels of complexity and begin to exhibit behavior that can simulate any of the four classes - a telltale hint of universality. Furthermore, their behavior starts to be influenced by "attractors" that guide them to "structure" and self-organization.
With the scent of universality and self-organization in the air, Wolfram begins in chapter seven to compare and contrast his cellular automations to various real-world topics of interest. Billiards, taffy-making, Brownian motion, casino games, the three-body problem, pachinko machines - randomness is obviously a factor in all of these. Yet, Wolfram notes, while randomness is embedded in the initiation and influences the outcomes of each of these processes, none of them actually generate true randomness in the course of running the process itself. The cellular automations he has catalogued, particularly his beloved Rule 30, do. The realization that cellular automations can uniquely serve as an initiator or generator of true randomness is a crucial insight, leading to the difference between continuity and discreteness and ultimately to the origins of simple behaviors. How, you ask? Hey, Wolfram takes most of the chapter to lay it out in a manner that I'm still trying to follow: no way can I summarize it in a sentence or two.
By chapter eight, Wolfram believes he has laid out sufficient rationale for why you, me and everybody else should think cellular automations are indeed the mirror we should be looking in to find true reflections of the world around us. Forget the Navier-Stokes equations - if you want to understand fluid flow, you have to think of it as a cellular automation process. Ditto for crystal growth. Ditto for fracture mechanics. Ditto for Wall Street. Most definitely ditto for biological systems like leaf growth, seashell growth and pigmentation patterns. This is very convincing stuff - tables of Mathematica-generated cellular automation shapes side by side with the photos of corresponding leaves or seashells or pigment patterns found in nature. Yes, you've seen this before in all of the fractals textbooks. The difference between fractals and cellular automations: fractals are a way to mathematically catalog the points that make up the object while cellular automations are a way to actually physically create the object via a growth process. It's a somewhat subtle difference - and a key Wolfram point.
Having established some credibility for his ideas, Wolfram stretches that credibility to the limit in chapter nine, where he applies his cellular automation ideas to fundamental physics. It was practically inevitable he would do this - his first published paper as a teenager was on particle physics, and that's the field he got his PhD in from Cal Tech at age 20 before going on to write the Mathematica software program and make his millions as a young businessman. Despite his solid background in physics, this seems at first blush to be pretty speculative stuff. He shifts his focus on the cellular automations from randomness to reversibility, and describes several rule-sets that both lead to complexity and are reversible. This behavior is an apparent violation of the Second Law of Thermodynamics. From Wolfram's way of thinking, if the universe is indeed some kind of ongoing cellular automation, then it may well be reversible and the Second Law must not be the whole story, so there must be something more we have yet to learn about the nature of the universe itself. He continues extensive speculations on what this may be, and how space, time, gravity, relativity and quantum mechanics must all be manifestations of this underlying Universal Cellular Automation. The rule set for this ultimate automation, which Wolfram believes might ultimately be expressed as only a few lines of code in Mathematica, takes the place of a mathematically-defined unified field theory in Wolfram's world. This is mind-blowing stuff, but ultimately boils down to Wolfram's opinion. I have great difficulty in comprehending space and time and matter and energy as "mere" manifestations of some cellular automation - if so, what is left to be the "system" on which the automation itself is running? I'm reduced to one of Clarke's Laws: The universe is not only stranger than we imagine, it is stranger than we CAN imagine ...
Wolfram shifts from Kubrick-style religion back to mere philosophy in chapter ten, where he explores how cellular automations are perceived by the human mind. Visual image perception, the human perception of complexity and randomness, cryptography, data compression, statistical analysis, and the nature of mathematics as a mental artifact are all explored. The chapter ends on a discussion of language and the mechanics of thinking itself. Wolfram reaches no real concrete conclusions on any of these, except that once again cellular automation is a revolutionary new tool to use in achieving new insights on all of these topics.
Chapter eleven jumps from the human mind to the machine mind by exploring not the nature of consciousness but the nature of computation instead. He goes here into somewhat deeper detail on ideas he has introduced earlier, about how cellular automations can perform mathematical calculations, emulate other computational systems, and act as universal Turing machines. He focuses on the implications of randomness in Class 4 systems and the universality embodied in systems like that of his Rule 110. His arguments lead up to a closing realization, what he does not call but may one day be named Wolfram's Law.
The final chapter, chapter twelve, discusses what all of Wolfram's years of isolation and work have led him to conclude. He calls it the Principle of Computational Equivalence. What follows is an unavoidably oversimplified distillation of Wolfram's thoughts on the PCE. If indeed cellular automations are somehow at the heart of the universe around us, then the human effort to reduce the universe to understandable models and formulas and simulations is ultimately doomed to failure. Because of the nature of cellular automation computation, there is no way to come up with a shortcut method that will deduce the final outcome of a system in advance of it actually running to completion. We can currently compute a rocket trajectory or a lens shape or a skyscraper framework in advance using mathematics merely because these are ridiculously simple human efforts. New technologies based not on mathematics but instead on cellular-automations like wind-tunnel simulators and nanobot devices will be exciting technological advances but will not lead to a fundamentally new understanding of nature. Issues that humans define as undecidability and intractability will always limit the level of understanding we will ultimately achieve, and will always have impacts on philosophical questions such as predestination and free will. To conclude with Wolfram's own final paragraph in the book:
"And indeed in the end the PCE encapsulates both the ultimate power and the ultimate weakness of science. For it implies that all the wonders of the universe can in effect be captured by simple rules, yet it shows that there can be no way to know all the consequences of these rules, except in effect just to watch and see how they unfold."
As noted above, 350+ pages of notes follow this exposition, and trust me, there's no way they can be summarized. To mention one nugget I found amusing as I envisioned Wolfram working towards endless dawns on ANKOS, he thinks sleep has no purpose except to allow removal of built-up brain wastes that cannot be removed while conscious. So much for dreaming.
So what is the bottom line on ANKOS? It is a towering piece of work and an enduring monument to what a focused and disciplined intellect can achieve. It is very thought provoking. It will definitely lead to new work and progress on cellular automation theory and some interesting technological applications we should all look forward to with anticipation. But is it the next Principia, the herald of a new scientific revolution?
Read and decide for yourself. Only time, and a lot of it, will tell.
To read it yourself, you can purchase A New Kind of Science at bn.com. You can read your own book reviews in this space by submitting your reviews after reading the book review guidelines.
Fallacies everywhere... (Score:5, Interesting)
I am disappointed that a Physics PhD could miss out on some fundamental issues here. First of all: anybody who has worked their way through an undergraduate curriculum in Physics understands in a visceral fashion that there is an extreme difference between MODELLING the world with a construct, mathematical, computational or otherwise, and saying that the world IS such a construct. We are in possession of many equations that model certain interactions between different kinds of substances via different forces in the world. Traditional mathematics has yielded many useful tools for modelling these processes. Stating that computational theory or cellular automata may yield useful models as well is an obvious inference. Saying that all physical processes are fundamentally composed of elements that ARE cellular automata seems to me to be a non sequitor. Hell, we don't KNOW what anything in quantum physics or beyond IS really, we just know that certain relationships hold mathetmatically that we can translate in physical conceptions and understanding.
Now, the concept of emergent complexity and complexity theory in general - as I understand it, this is stuff that folks at the Santa Fe Institute and elsewhere have been working on for years, and that the understanding has been around for years that you can model many real-world processes well by systems such as cellular automata or other rule-based systems with complex emergent behaviors.
So... I am left wondering what to make of this book. Ultimately, it will speak for itself when I read it. But it sounds like it's a mix of already known fact with ego and some intuitionist insights into certain physical processes in a monolithic volume. If he PROVES anything interesting and fundamental about certain areas of physics or fluid dynamics, or presents models more useful and meaningful (i.e. that provide information NOT obtainable through current models) than he has produced a valuable scientific work. Otherwise, it's just an interesting treatise that may inspire more meaningful work by others who are more willing to work within the establishment and processes of the mainstream scientific world (not to say that those outside it CAN'T do excellent work, just that I'm not sure if Wolfram can).
I wonder if he is still sane. (Score:3, Interesting)
I worry about that. Science isn't practiced very well in a vaccuum. One feature of the scientific act of discovery that makes it so effective is that the scientists involved are constantly examining each others musings, to keep any one of them from going off the deep end. Genius and madness go hand in hand, after all, and nothing can drive you nuts quite like being alone with your own thoughts. Especially if those thoughts are exceptional.
I just hope this book doen't show that dear Dr. Wolfram has lost it.
"Bit String Physics" (Score:4, Interesting)
From the introduction to Bit String Physics [amazon.com]:
Re:Fallacies everywhere... (Score:2, Interesting)
Personally, I'm going to read the book BEFORE i decide.
Crank, crank, crank (Score:5, Interesting)
This means he's almost certainly a crank. If actual scientists were arguing heavily about it, there might be a bit more uncertainty. But if the debate is happening amongst people whose knowledge of physics comes mainly from Star Trek, then that pretty much settles the matter in advance.
Wolfram will probably end up having a place on the intellectual fringes, worshipped by people who are often smart but who haven't bothered/aren't trained well enough to see why specialists don't really pay attention to them. In nerd idea-space Ayn Rand is the other main example of this type.
The best comment I've read about Wolfram's book comes from Cosma Shalizi, a physicist working at the Santa Fe institute, who specializes in cellular automata. He comments [santafe.edu] [scroll down on link]:
Dis-recommended: Stephen Wolfram, A New Kind of Science [This is almost, but not quite, a case for the immortal ``What is true is not new, and what is new is not true''. The one new, true thing is a proof that the elementary CA rule 110 can support universal, Turing-complete computation. (One of Wolfram's earlier books states that such a thing is obviously impossible.) This however was shown not by Wolfram but by Matthew Cook (this is the ``technical content and proofs'' for which Wolfram acknowledges Cook, in six point type, in his frontmatter). In any case it cannot bear the weight Wolfram places on it. Watch This Space for a detailed critique of this book, a rare blend of monster raving egomania and utter batshit insanity.]
I await solid arguments to the contrary --- ie, arguments that don't start from any of the following premises:
1. But he was a boy genius at CalTech and Feynman said so!
2. But he wrote Mathematica, which is obviously really hard!
3. But if he's right this will change the world!
4. But other Scientists are ignoring/laughing at/refuting him only because they are jealous of his enormous brain!
5. But he only ignored peer review because he's so brilliant!
6. But every work of genius always seems crazy when it first appears!
I leave it was an exercise to the reader to show why Wolfram's supporters shouldn't rely on these points (although Wolfram himself apparently does).
Are these the tools for decompiling DNA? (Score:4, Interesting)
What this most made me think of is DNA. DNA is just oodles of four-state variables that represent some kind of program. It is exactly like the cellular automata he's been working with. Looking at the code (the DNA itself) and the output (the organism produced) perhaps we can understand the underlying algorithm that uses the code to produce the output. Unravelling, understanding, decompiling, reverse engineering, or whatever you want to call it, the secrets of how the DNA code is executed could be the biggest scientific advance ever, and Wolfram may have provided the tools to do it.
Suprisingly there was no reference to this in the review, which probably indicates no discussion of it in the book. Cybrpnk2, is it true that he did not discuss DNA?
Re:Fallacies everywhere... (Score:4, Interesting)
There's a good chance that Wolfram is attempting to do much more than provide support for the work of others (although that is certain to occur). The sheer number of axioms, the amount of supporting "data", and the numerous instructions to build supporting "instruments" (via his software) leads me to that conclusion.
Thomas Kuhn proposed that mainstream science is based on an ongoing process of shattering and creating scientific worldviews. I would say that that the most meaningful work is performed by people who are able to support a new theory with new data and cause a paradigm shift [uoregon.edu].
Copernicus, using the latest instruments and the latest data acquired from those instruments, argued that it is the Sun at the center of the solar system (and not the Earth as most scientists in his era argued). I think that Wolfram is trying to be a Copernicus as opposed to a Hawking. So the real question here is: what is Wolfram getting at with this book? Well, he probably is not done yet.
On a lighter note, we can't blame such talented (and often obsessed) individuals for perceiving everything within the context of their paradigm - especially when it could lead to more software sales ;)
Re:Are these the tools for decompiling DNA? (Score:3, Interesting)
worried about his opinion on sleep (Score:1, Interesting)
To mention one nugget I found amusing as I envisioned Wolfram working towards endless dawns on ANKOS, he thinks sleep has no purpose except to allow removal of built-up brain wastes that cannot be removed while conscious. So much for dreaming.
>>
There's really a tremendous amount of scientific literature on the role of sleep focusing on the role of sleep in consolidating the events of the day into long term memories by storing important events and dumping unimportant ones. The hypothesis that the reviewer and Wolfram are apparently referring to (sleep allows neurons to clear waste and rebuild neurotransmitter supplies) may have some validity, but no one in sleep research would consider it the whole story. I'm a bit worried about Wolfram's grander conclusions if he's missing basic literature in fields outside his own.
Disclaimer: I haven't read the book either, so I don't know the full context of Wolfram's claims on sleep
Re:One in math? (Score:3, Interesting)
Emergent systems (Score:4, Interesting)
Robert Laughlin (Stanford University) is researching this. What we observe in the universe is model-independent, and we cannot actually see the model itself.
"The laws that govern large-scale phenomena will not be deduced from the laws that govern tiny particles, he says. "It's in the same way that flocking behaviour can be characterised without understanding everything about birds, or superconductivity without understanding atomic theory."
This idea is called emergence. It's a familiar phenomenon in the theory of condensed matter, which is Laughlin's background. Solids and liquids sometimes play host to strange entities that bear little resemblance to the atoms making up the substance."
...
"If what you see is model-independent then you can't learn anything about the underlying equations by observing it," says Laughlin. "You could call this the dark side of emergence."
...
"What we emerge from is unknowable," says Laughlin. "The underlying equations of the Universe cannot be determined from what we know."
The article goes into greater detail than I can here, but it definitely an interesting read.
If all this is true, we can never really know the true mechanics of the universe. It may actually be a simple "4-line" automaton. It could be a billion other things - we'll probably never know.
Wolfram is no Isaac Newton (Score:3, Interesting)
Re:Don't read this post (Score:4, Interesting)
But then again, this is Slashdot...
Try Homeschooling... (Score:1, Interesting)
Every year we talk about sending them to a "normal" school, and every year we don't.
So far the kids seem to be ok -- people say they are pretty bright -- they just seem like our kids to me.
The big downside is I never see my wife (she teaches the kids in the AM and works in the PM), and the kids handwrighting is pretty bad.
Any other homeschooling parents/kids out there?
-- ac at work
Re:Ahem... (Score:1, Interesting)
Referencing Chomsky has become sort of a litmus test for me, as has Stephen Jay Gould.
They're all bright people who communicate primarily with people outside of their fields of interest, who don't know enough to evaluate the originality or validity of their arguments.
I've noticed a pattern: they write something of validity, that's interesting, to establish some sort of credibility. Then, however, they write a treatise aimed at a lay audience or audience outside of their field that makes grand claims about some topic. The lay audience says "Look, this person has X credentials, what they're saying must have some validity". Then they proceed to quote them uncritically. Often the audience doesn't know enough about the topic to critically evaluate it for originality, etc. But they accept it, and because the work has been aimed at a larger audience, masses of people attribute various accomplishments to them erroneously, or make ill-formed arguments based on the work.
In the case of Chomsky, this involved his entry into political science, sociology, and law.
In the case of Gould, it involved his entry into psychology and behavioral ecology.
Wolfram may very well represent another one of these figures, that everyone who isn't involved in the field begins to cite. I've already seen it here on Slashdot--people speculating about possible advancements suggested by "Wolfram's work" without assessing the validity of his claims or his authorship. They don't know enough about the field to assess his work, and don't bother.
Wolfram has made a lot about needing to bypass traditional academic circles to publish his book. He claims it's because they don't understand. My impression based on initial comments by those in the field is that the real reason he bypassed people in the field is because he doesn't have much new to say, but wants to say it anyway, and thus has to say it to an audience who doesn't know the difference.
The physics is speculation (Score:4, Interesting)
Fredkin went down this road a few years ago, but didn't succeed either. He and Wolfram used to work together, but they seem to have split up.
If anybody ever finds a simple CA that results in a system that behaves like physics, there will be a short, world-famous paper that will put them down in history with Newton and Einstein. But this isn't it. To Wolfram's credit, he isn't claiming that it is.
Re:INTERVIEW WOLFRAM! (Score:3, Interesting)
okay, so i'm bitter (Score:2, Interesting)
Peer-review has its uses, especially in filtering out crack-pots with perpetual motion machines. That said, its not the only way or the best way to publish, especially if you have something that is as new and revolutionary as Wolfram claims. He's got enough information for people to reproduce his results, so he's not a crank... he just might be wrong.
Re:Talking at work (Score:4, Interesting)
This is quickly becoming a religious discussion.
If you are interested in emperical evidence that has been collected which validates QM, may I humbly suggest a google search on the topic as a starting point. We have electrical devices which rely on quantum tunnelling to function is one example that comes to mind
Your "religious" stance is that mathematics can be used to define and model the physical world at any level (and by implicaton, any physical system), and wherever it cannot, it must be because our view of the physical world, not our mathematics or the application thereof, is wrong.
My "religious" stance (since I'm not going to bother to dig up the references here
Any argument which starts by dismissing emperical evidence as "imperfect and therefor to be dismissed in favor of our elegant models which we hold so dear" (as an aside, the heisenberg uncertaintly principle refers to a particle's position and vector, not the overall, possible constraints thereof. It does not preclude emperical evidence of its existence, measurement of its value, or consiquences, as you mistakenly assume. Indeed, quite the opposite) in favor of appeals to authority ("we've used this approach for thousands of years and it works, so anything we see that conflicts must be wrong!") becomes a religious, or perhaps philisophical, but certainly not scientific, discussion.
The Greeks didn't like the fact that the number two had an irrational square root
Re:INTERVIEW WOLFRAM! (Score:3, Interesting)
I think we should wait a year, perhaps two.
And I think the questioners should be required to have read the book in question, and pass a test on the subject as an (admittedly imperfect) assurance that they have done so.
Otherwise the questions are likely to be an emberrassment, and the answers rather scathing.
Then again, that might be worth it, just for entertainment value. [grin]
Re:One in math? (Score:3, Interesting)
I have a Sociology degree, and a Robotics/AI degree. Robotics was far easier, and dealt with simpler logical models. Sociology was harder because it dealt with people and social networks -- easily the most complex systems ever discovered in the universe (and I have a background in theoretical physics).
Yes, Sociology attracts flakes, but it also attracts people who like to get to grips with the really difficult, interesting questions that can't be abstracted away into pseudo-code, automata, and heuristics.
uh, Church's thesis, Goedel, Turing, etc. (Score:1, Interesting)
Church's thesis: all computational mechanisms of sufficient power are equivalent (e.g. by bisimulation). That sounds a lot like Wolfram's PCE.
Turing machines are an example of a universal machine.
So once you get simulation of a Turing machine, then everybody acknowledges that complexity arises, and universal complexity in particular.
Turing's original result was showing the non-computability of the halting problem for Turing machines, which pretty well sums up what the reviewer says is the final insight: there's no analytical shortcut for complex processes.
This is not new.
(Also compare with Goedel's incompleteness theorem about the existence of true but unprovable statements.)
And if you want a readable account of cellular automata and its relationship to complexity in general an universal machines, read William Poundstone's "The Recursive Universe". He told the story of the loads of people playing with cellular automata. It's *readable* and *digestible*. (I digested it when I was about 19...)