While NKS came out with much hype, and with a lot of skepticism from scientists, the scientific ideas there are not completely trivial. I just think they are not foundational for the science of physics (at least not as we know it so far), rather they are foundational for the science of biology.
The main discovery made by Wolfram (although with an important confusion which I will explain below, and with an extremely significant precurser in Coway's game of life) is that a simple 1 dimensional cellular automata whose rules are chosen at random will have a finite not so small probability of being a full computer (in Wolfram's system, 2 of the 128 possibilities). The proof that the system he found, rule 110 in his terminology, is actually a full computer only came two decades later, thanks to the pioneering work of Cook (working under Wolfram). But it justifies his focus on the system as central to science, since before, it was often implicitly assumed that to get a certain amount of complexity, you had to put in complexity by hand. This result is also present in Conway's system, but Wolfram's work is somewhat complementary, because the information flows in 1d systems make it more difficult to imagine a full computer emerging. The fact that it does anyway (although, as Cook's construction shows, with horrible running times, because of the difficulty of shuttling imformation long distances) is surprising and notable.
This is not so important for physics, because any attempt to model physics with cellular automata will have to be grossly nonlocal in order to avoid Bell's theorem. This is not so implausible today, given gravitational holography, but Wolfram suggested that there would be a direct correspondence between local elementary particle paths and automata structures, and these ideas are flat out impossible, and were ruled out before he proposed them, by Bells theorem. This means that the chapter of his book dealing with physics is completely wrong, and may be ignored.
But this work is important in a completely different way, it is the foundation of biology!
(EDIT: Chaitin's new book makes some brief comments about NKS which echo the main biological points below. I am not cribbing Chaitin, his book postdates this.)
Biology and Religion
The most puzzling aspect of the world we find ourselves in is that we are surrounded by complex computing devices not of our own design! Namely ourselves, other people, animals, plants, and bacteria. How did these computational structures get built, when we have to work pretty hard to make a computer? It seems that there is a puzzle here.
The puzzle has, in the past, been resolved by assuming some sort of magic put life on Earth, a supernatural agency. This idea is clearly at odds with the laws of nature as we understand them today, but it is important to keep in mind the superstitious answer, because elements of it are salvageable.
The superstitious answer is that God came down into the primordial soup, and mixed up the molecules to make life. The notion of God is not clearly defined in religious texts, where rigor is not the top priority. But I will try to give a positivistic definition below. I find that using this positivistic definition, which does not mention anything supernatural, I can translate the thoughts of religious people and make complete sense of what they are saying, where otherwise it just sounds like the ranting of delusional people suffering from severe brain-damage.
In order to discuss biology sensibly, I believe one must understand this religious point of view thoroughly, in a logical positivistic way, because it is important in biology to the same extent that it is completely unimportant in physics.
In a complex system, such as human social structures, we tend to observe patters which cannot be attributed solely to the actions of individual people. For example, the protestant reformation seem to have happened all at once, within the span of a few decades in the early 16th century, where Church reformers were active and working for centuries before, with very little success. What made it happen? It wasn't just Luther and Calvin, it was also a network of businessmen and bankers, and disenchanted Catholics. The discovery of America was important in some way, as was the expulsion of Jews from England. To my mind, the most important was the 14th century edict forbidding usury by Catholics, which prevented the formation of banking. But it clearly wasn't one cause, nor was it the work of one person working alone.
When we see such complex phenomena, it is reasonable to attribute them to the working of a larger intelligence than the intelligence of any individual, and this is the intelligence of the collective. Just as a person is a collection of neurons, not any one of which is responsible for her intelligence, the society is a collection of individuals, no one of which is responsible for everything the society does or thinks collectively. The collective pattern is in many ways smarter than the individual--- it contains collective memories, in traditions and conventions, which inform individual action in complex ways.
The notion of of god (lower case g, like Zeus, or Mars) in ancient cultures is the name given to the entities formed from collective human actions. They are nebulous, but important, because the decision to go to war cannot be attributed to any one person, but to an entity, the god of war, formed from many individuals working together with the aim of forming a coherent collective which will lead the society to make that phase-transition of behavior which is going to war. Identifying a notion of a god, and explcitly setting people working for this god, makes them aware of the fact that they are working as parts of a machine, not solely as individual actors. Further, it can inspire them to act without direct orders from a King, or a priest, just through their own introspection, so as to best achieve the goal.
The notion of god was refined somewhere in India or Iran into the notion of God (upper case G), from which the Brahma cults and Abrahamic religion, and Zoroastianism emerged. This notion suggests that the conflict between gods is similar to the conflict between individuals, the gods also make collectives, and some win and some lose. In the end, there is a notion of a supreme God, the God which is the limit of the collective of whatever gods survive, defined as infinitely high up the god heirarchy, and demanding ethical actions.
This limiting conception of God was considered so important by the ancient thinkers, that they let all thier other ideas die away in the midieval collapse, choosing to preserve only this through the middle ages.
But in addition to the practical notions of guiding behavior in collectives, the ancients also attributed all sorts of supernatural feats to God, including creating the universe and hand-designing life. These ideas about God are out of place with the conception as a meta-property of a complex system, and are completely contradicted by modern scientific discoveries. They are superfluous to religion, and detrimental to it, because they make people expect miracles and divine intervention in ways that violate the laws of nature, and such things just never happen.
The notion of God, as far as I have been able to make sense of it, is essentially a limiting computational conception--- it is the limit as time goes to infinity of the behavior of a complex system where the computational entities combine and grow in power into ever larger units. The idea of the limit suggests that there will be a coherence between the units at all levels, so that in the infinite time limit, for example, all societies will agree on the ethical course of action in a given circumstance, and will agree on how to organize their economies, and structure their interpersonal relations. These predictions are surprising, considering the divergence in human behavior, and yet, history suggests that such a convergence is slowly happening.
This computational decidability in the evolving limit has a direct counterpart in the idea that as mathematical systems become more complex, by reflection, they decide all arithmetical theorems. This is not a theorem, but an observation. It is noted that as we go up the tower of set theoretic reflection principles, more and more arithmetic theorems are resolved, and there is no in-principle limitation that suggests that the theorems will not all be decided by strong enough reflection. This is Paul Cohen's "Article of faith" in mathematical practice, and I will accept it without reservation.
Further, the article of faith tells you that we already have a name for the mathematical idea of God, it can be identified with the concept of the Church Kleene ordinal, the limit of all countable computable ordinals. Any computable formal system is only able to approach this ordinal gradually, and this ordinal is infinitely rich. If you have a description of this ordinal, you have a reflection principle which should be powerful enough to decide all theorems of arithmetic, to decide what consequences of any axiomatic system will be.
Because this ordinal has all the theological attributes religious folks attribute to God, in relation to pure mathematics, I consider it a sort of heresy to assume that there are larger ordinals. In particular, any notion of the first uncountable ordinal, or inaccessible ordinals, are only meaningful once they are placed in a given axiomatic system, and then they should collapse in the appropriate countable model to be less than the Church Kleene ordinal. This is not technically precise, but it gets the main idea across (it is easy to collapse the ordinals to be countable, but it is not so easy to rearrange the scheme to make them less than Church Kleene, but this is because within any deductive system which is of a set-theoretic nature, you can give a name to the Church Kleene ordinal, and define this ordinal plus 1, etc. These technical considerations are not so significant for the philosophical ideas)
So the interpretation I will take for religious doctrine is that God is to be identified with the Church Kleene ordinal, no higher ordinal is to be interpreted as actually higher, and gods will be identified with human collectives acting together to form a unit greater than the individuals. The monotheistic law of complex systems will state that all gods converge to the ideal represented by God over time, as they battle it out in a Darwinian struggle.
Automata and Darwin's experiment
When you have a cellular automata capable of universal computation, there is a strange phenomenon--- sub-parts of it are always in competition with itself. To explain this, one needs to look at Darwin's experiment, detailed in the Origin of Species.
Most of the Origin is theoretical, but Darwin did do one important experiment. He took a square plot of land, and carefully removed all visible living things from the soil. He uprooted all the plants, sifted to remove insects, and left the plot alone to see how it would be recolonized.
What he observed is that the plant species that recolonized the plot were first of the fast-growing unstable variety, that a whole bunch of weeds and bugs spread over the new area. Then, over time, other more hardy species slowly took over from the weeds, until, many months later, the plot was indistinguishable from the remaining land in the lot.
The purpose of the experiment was to see whether there is an actual struggle for resources in nature. Darwin hypothesized that if nature is in constant struggle, different elements, which are more successful but slowly replicating, will only win out after a time over elements which are less hardy, but whose strategy is quick colonization of new territory. His observations were consistent with the idea that the living things in any area are continually struggling for primacy, and that the limitation is the finite resources in any given plot of land.
This idea can be tested in computing cellular automata. By zeroing out a square patch in a 2d cellular automata which looks stable, one can see whether the remaining data colonizes the space in a way that is uniform, or in a gradually transforming way. I did this experiment using an 8-bit cellular automata (256 values) with random rules, and I found that in many cases, those cases which are complex, the colonization is in stages, much as in Darwin's plot of land. The stages are short-lived, perhaps reflecting the limited computation possible in a small region with 8-bit values. It would be interesting to repeat the experiment using arbitrarily large integers on each cell, which can be thought of as representing a complex polymer, which catalyzes transformations on its neighbors
But the inhomogenous colonization suggests that once you have a computing cellular automata, there is a constant competition between parts of the automata, which make collective computations, for resources. In other words, that Darwin's struggle is begun.
To make this idea more precise, consider dividing a CA in two, by placing a wall between the left and right half, and not allowing the halves to interact. If the CA is truly computational and complex, the two halves will not come to a statistical equilibrium, but will have complex structures on either side which acquire new characteristics at random over time, as its subparts evolve.
If you now remove the wall, it is unlikely that the left half will have compatible characteristics with the right half. They will not be able to mix. So in this case, the two halves must battle for domination, and whichever half wins will impose its characteristics on the other half fillling the whole space with cells which are compatible with its characteristics. These characteristics include typical CA "animals" or structures which are qualitatively similar in their relations, particular configurations which are only stable in the environment of other structures around them. It is difficult to extract these characteristics from a running simulation, because you don't know a-priori what to look for, but I am confident that it can be done.
This type of thing implies that there is continuous competition in a CA which appears the moment it is first seeded, and continues as long as it is operating. In this environment, Darwinian selection and evolution are possible even without any explicit self-replicating structure. Any self-replication is of very high-level qualitative traits, not of low level bit structures.
Replication and evolution
This point of view is different from the most usual point of view regarding evolution (which is not the one originally proposed by Darwin). The usual point of view is the modern-synthesis evolution, which suggests that evolution proceeds by copying bit-strings in molecules, with errors, and that the result is that optimized bit strings are eventually selected.
This point of view is extremely poor in modelling actual biological evolution. First, nothing you are familiar with actually replicated itself. People have sex, bacteria share genes, and crossing over is complicated on non-genetic sequences, it is only a simple shuffling on genes.
Further, mutations seem to be produced by shadowy internal mechanism directed by complex RNA networks in egg cells and in testicles. They are not random copying errors. To assume that the biological world is produced by a process of copying with error, coupled with selection is as silly as the following parable suggests:
Many years ago, there was only one book. It was a cookbook, with detailed instructions on how to make macaroni and cheese. The book was copied by scribes, who made an error here, an omitted passage there, and these books then competed for attention. Some recipes were improved by the errors, others became unreadable. Eventually, the books grew in length, with new passages produced by accidental duplicated copying, until today, behold! The library of Congress!
This story is ridiculous. But it is this ridiculous story that is currently sold as dogma in the biological sciences.
It is my view that any realistic theory of evolution must be closer to Darwin than to the modern synthesis. It must take into account that the process of mutation is authorly, it proceeeds by complex RNA editing of DNA sequences. It must take into account the idea that sexual selection is primary, so that mate-selection is the dominant driving force of evolution in sexual species. It must also take into account the idea that the competition begins well before replication, and requires nothing more than a computing CA.
There is support for this position from computer experiments on self-replicating evolution. In order to test natural selection, little chunks of code were allowed to replicated and self-modify in the 1970s-1980s, to see what the end result would be. The end result was that the programs modified themselves until they found the shortest fastest self-replicator, which then filled up the computer memory.
At the time, this was considered a positive sign, the programs had evolved. But the obvious stasis in the final state leads me to see this as death of a complex system. There is no further progress possible from the end state, without an external agent to kick things around. The result is not a complex system, but a system trapped in a stable equilbrium of parasitic fast replication. Far from being a model of life, it is a model of a self-replicating cancer killing all evolution.
CA properties: Wolfram's Annoying Error
Wolfram classified Cellular automata into four types
- homogenous end state
- Simple periodic structures, perhaps separated, with different periods
- Self-similar ("Chaotic") structures
- Complex structures
Type 1 are automata that die. These just have a single stable endpoint that you always reach. Type 2 have infinitely many endpoints, but they are as simple to describe as a classical integrable motion--- you just have cycles of certain types, and to specify the endpoint, you give a list of all the cycles, and where you are in the cycle, and this specifies the result of running the CA from a given initial condition. These first two types of automata obviously will not reproduce a general purpose computer.
Type 3 are those automata that lead to self-similar fractal structures, like the Sierpinsky gasket. These are more complex, so that the end-state requires an actual computation to specify, and wolfram identifies these with classical chaotic motions. I think this identification is wrong, but this is what it is.
The Type 4 are the complex automata, where you have to actually run them in full to figure out what they do. I don't like the final category, so I will now give my personal classification.
- homogenous end state
- simple periodic end states, perhaps separated with different periods
- Self-similar or statistically self-similar fractal structures
- random automata, chaotic stable endpoint, stat mech.
- Complex automata, biology.
The class 3 is expanded slightly, and class 4 is divided in two. There are random automata, which act to produce a randomized collection of values which wander ergodically through the allowed value space, and class 5, those automata which produce true complex behavior, with a way to map a computer into them with a map of map of reasonable complexity, which can actually be described by a finite procedure.
Because Wolfram doesn't distin
Q&A (4870)
