Synopsis of Stephen Wolfram's book

"A New Kind of Science"

Swinton Roof

July-Aug 2002

Wolfram's new book is a marvelous tour de force of insight and ingenuity. Weighing in at over 1000 pages, it is a surprisingly easy read. Wolfram has one simple theme and he hammers it in continuously with very detailed and easily understood illustrations. His central thesis is based on the concept of the Universal Principle of Computational Equivalence. With this principle as his guiding light, he successively upends almost all of our cherished ideas about natural systems, theoretical science, mathematics, ideas of randomness, probability theory, free will and thought. Wolfram's book represents a lifetime of meticulous work but he has finally achieved what none before have - a foundational breakthrough in Systems Theory. The principle above may sound intimidating to those not mathematically inclined but I assure you, Wolfram's entire thesis is simplicity itself i.e. simple rules lead to complex behaviour. That's all you really need to know. The rest is just a slide show about the enormous implications of this.

I have written this essay as an attempt to disseminate some of Wolfram's ideas to my fellow thinkers, so that we might begin fruitfull dialogues. It is my belief that he has provided the very foundations for our developing concept of metalevel recursion & compressive valving inherent in Universe. This provides us with the unique opportunity to extend his work in our own directions. While reading his book, I wrote my own computer program to duplicate some of his results. This nifty little program also provided me with the illustrations to use in this essay. At the end I will add some observations of my own that we can start discussions with.

To begin, I'll need just a wee bit of explanation about systems and cellular automata, what they are, and what they can do. Wolfram uses simple cellular automata as his basic model for exploration.

1. CELLULAR AUTOMATA

Nature abounds in enormously complex systems we can only crudely describe. Systems like the weather, living organisms etc. are beyond our mathematical equations. If we look at systems in a particular way, though, we can gain some insight into a new way of thinking about them. Let's talk about computation first. Most all of us are familiar with using computers. We know they are just machines which take input and generate output. Underneath the hood are millions of things happening - bits flipping on and off etc. to generate that final output. Now if one thinks along temporal lines, he can see that really the computer, considered as a system, is just a bunch of states that change over time. In fact, the input and output can likewise be considered as states i.e. sequences of bits that are on or off. One can even remove the user and let the machine react to automatically generated inputs. Seen in this light, a computation, however complex, is just a series of states in the whole system. Complex systems in nature can likewise be thought of as just a series of states that change over time. Natural systems can thus be directly described as computations. The inputs are just the initial conditions and the outputs are just the final conditions.

There is an abstract little critter called a cellular automata that can do computations like we have described above. Formally it is just a box or cell that can have one or more states. A collection of such cells form a system if they are somehow connected or if their changes affect each other. Cellular automata are usually layed out on a spatial grid so that cells are usually affected only by their closest neighbors.

Wolfram starts with the simplest of all possible systems - one cell 'on' in a one-dimensional line of empty cells. Almost no one before him spent much time on such systems. Most mathematical attempts to understand cellular automata have been focused on 2dimensional arrays and complicated rules but little progress had been made. Wolfram started at the simplest level and soon found out why. He discovered an enormous wealth of complexity even at the very simplest possible level. Below is how it works.

Consider the simplest possible system. Each cell can be on or off (black or white). The next state of a cell depends only on the on/off state of it's nearest neighbors i.e. the cell to the left and the cell to the right. Below is one cell on with both neighbors off.

What kind of rules can we have? One possibility is: if the left is off and the right is off then the center cell will turn off. To consider the possible rules, however, we need to first understand what all the possible states are to begin with. For three cells here are only 8 possible cases:

If we consider each cell as a binary bit we may write the above possibilites as a series of 3-bit numbers. Below is that representation with the decimal number in parenthesis and the binary number following

(7) 111...(6) 110...(5) 101...(4) 100...(3) 011...(2) 010...(1) 001...(0) 000

The possible states is just the sequence of binary numbers from 0 to 7. Two to the power of three gives 8 possible states. This very simple list of initial patterns or states is the domain of inputs that any rules we come up with will operate on. Each rule we use must be evaluated according to which initial pattern is the case at the time. The outcome must be either on or off i.e. 1 or 0 so we can depict a rule simply by listing the possible patterns and show an on or off result underneath it to indicate which way the rule fires. Below is an example of such a rule with the outcomes shown for the center cell in each of the 8 possible starting patterns.

We can see that the center cell goes on in its next state only if the initial condition corresponds to patterns at positions 1 or 3 or 4. We can represent the above rule simply as an 8-bit number i.e. 00011010. This number evalutes to 2^4 + 2^3 + 2^1 = 26. We can thus call this rule by its number 26. The designation for the rule is quite simply the structure of the rule itself!

Now we wish to display the results of applying this rule 26 to a starting condition of one cell on. Each succeeding line of cells below shows the application of this rule to each particular cell in the line above it. Here is the application of rule 26 for 7 steps:

We can see that the pattern spreads out and appears to have some repitition. In fact, if we do this in high resolution for 200 steps, here is what we get:

This remarkable pattern is identical to the classic fractal the Serpenski Triangle. Wolfram simply calls the resulting pattern 'nested'. The only essential difference is that it is built from the ground up instead of the top down. Instead of higher math functions involving trigonometric relations and recursive subdivision, it is built from one simple rule involving eight bits of information. It doesn't get any simpler than this folks. To be blunt, the entire system above, as a computation, can be expressed by only 11 bits i.e. the 3bit starting pattern and the 8bit rule.

The really nice thing about this simple scheme is that there are only 2^8 or 256 possible rules to be explored. This can easily be done. Once done, we have a complete descriptive account of the behavior of ALL what I call D1B2R1 systems. D1 stands for one dimensional, B2 means base 2 or binary valued, and R1 means the neighborhood radius is one unit cell.

My program also computes other systems such as D1B3R2 which has rules that evalute the two closest neighbors each side in one dimension and where each cell can have 3 values white,gray, or black. Enough of that for later though.

The important thing is that Wolfram discovered that the behaviours of all possible rules fall into 4 classes:

1) Simple uniformity or convergence to a fixed pattern

2) Repetitive or nested patterns

3) Apparently random patterns

and last but most important of all ...

4) Complex patterns that have recognizable local features that may repeat, and/or move around, mixed in with random patches, but with no enduring pattern anywhere that repeats in a predictable way.

Examples of all four classes are given below with the rule number which produced it.

CLASS 1 : rule 1- uniform

CLASS 2: rule 26 - nested

CLASS 2: rule 54 - Repetitive

CLASS 3: rule 30 - random

CLASS 4: rule 110 - Complex

The last rule was shown in greater detail because the complex structures don't appear until it has evolved a bit. One can see patterns that move in downward angles. When they intersect other patterns they sometimes pass on through sometimes not. Sometimes patterns intersect and produce a whole other pattern. There are also random areas that repeat. The randomness is sort of nested in the repititions.

Rule 30 (CLASS 3 above) is listed as random but it does seem to have repetitive features. In general, though, as it evolves, the central cells under the peak are completely random and unpredictable. The high res version below shows extended evolution. We will discuss this later.

CLASS 3 random - rule 30 - after 500 iters

In addition to the simple cellular automata model above, Wolfram investigated over the course of twenty years every discrete rule based system he could find. Included in some of the systems he studied are mobile automata, Turing machines, substitution systems, tag systems, cyclic tag systems, register machines, symbolic systems, networks, number systems, recursive systems, prime sequences and iterated maps. He also studied some continuous systems like differential equations. Some systems, especially the continuous ones, require tinkering with the rules a bit to get more than simple behaviour, but in general all discrete systems produce behaviour which falls into the above four classes. It is a testiment to his endurance that he could have undertaken this enormous task of investigating each type of system so thoroughly. Some rule sets produce so many possible rules that it is even theoretically impossible to explore all of them in this universe. Wolfram had to develop Montecarlo techniques to study statistical representations of the possibilites.

Below is an example of how adding a complication like using 3-valued cells can add a little but no real increase of complexity beyond class 4 is seen. The picture is interesting nonetheless. I colored it to add a little pizazz.

In general Wolfram found that no matter what you did, the simple model had all the basic variations in behaviour. Sometimes one had to make the rules a bit more complicated or use multivalued cells to get complex behaviour, but after that, any additional complication of the rules or possible cell values did little to complexify the system. Beyond a certain point, increasing the neighborhood size to include influences from more distant cells also did little to complexify the behaviour. The general rule appears to be that discrete systems only need to have a few simple rules to produce complex behaviour, and those rules need only be local rules. The corollary to this is that complex patterns never need complex reasons for existing. They can always be produced by simple rules. Complex rules just aren't needed. The icing to this cake is that continuous systems dont produce complex behaviour unless they are complicated or tinkered with. This has enormous implications that we will discuss.

2. INITIAL CONDITIONS

The above examples were all based on the initial condition of only one cell on. Can the behaviour be influenced by initial conditions? The answer is yes indeed, but the general four classes of behaviour remain. Below are samples started from random initial conditions (the top row of cells is random).

CLASS 1: rule 216 - convergence

CLASS 2: rule 3 - periodic

CLASS 3: rule 18 - random

CLASS 4: rule 110 - complex

Some of the behaviour with random initial conditions may mask or alter the nature of the rule. Rule 18 above generates the typical nested triangles, but a random start seems to maintain the randomness. Others like rule 216 above quickly converge to their true nature - uniformity. On the other hand, rules which generate complex behaviour tend to remain complex as rule 110 does.

One may also use repetitive patterns to start with. The results are similar to those above except now the random behaviour rules tend to give nice repetitive patterns. What's going on?

One clue is to notice that significant features in the pictures tend to either move straight down unchanged or move left or right at some fixed angle. Notice this behavior in the CLASS 4 - rule 110 picture above. As different patterns move and eventually intersect, they in effect, interact with each other. Now remember that all these patterns are quite simply strings of on/off cells i.e. bits of information. Patterns are only metaphysical interpretations of binary information if you like. Seen in this light, we can understand a bit better how the four classes of behaviour originate.

Recall that we said above that complex behaviour only requires simple rules and those rules need only be local. Local rules means cells only affected by their immediate surroundings. This is a very important clue as to what's going on. A cell can only be influenced by far away neighbors if they spawn a pattern that moves and eventually intersects that cell. Think in terms of pattern information flowing down through the system and left or right. How far this information travels has a lot to do with the final overall behaviour of the system as a whole.

CLASS 1 rules do not communicate information. Each cell is effectively or very soon closed off from the others. The system quickly converges to uniformity, even with random initial conditions.

CLASS 2 rules transmit information a little farther but only in certain fixed orientations that preserve the repetitive nature. Random inputs can present an apparent random overall pattern, but what in effect is happening is that the random initial pattern is simply being repeated.

CLASS 3 rules transmit information unbridled in all directions. The net result is that cells far away from each other ultimately have their influence felt in unpredictable ways. Patterns transmitted from one cell interact virtually with the whole system given enough time. This has the effect of a information blender set on puree'. Repetitive inputs conversely maintain their repetitiveness because the marching patterns are in step across the whole playfield of the system.

CLASS 4 rules handle information in a more balanced way. Local features mix and blend sometimes re-emerging, sometimes not. Class 4 stands on some kind of critical edge between order and chaos. Just enough information passes through the system to allow interaction, but not so much that chaos ensues.

The above discussion about the flow of information is at the very heart of why systems behave the way they do. When we finally get to the Universal Principle of Computational Equivalence we shall see the enormous consequence of Wolfram's new theory. For now, though, remember - simple local rules produce interesting global behaviour because pattern information gets transmitted at different rates.

One other fact should be pointed out now. All of the above systems are finite i.e. the program that generated them used a fixed grid or spatial framework of cells. Cells on the edges are evaluated by wrapping around to the other side to get the nearest neighbor. This means that the flow of pattern information is confined and this will ultimately produce reptition.

Strict confinement produces uniform behaviour as evidenced by class 1 systems because the rules themselves confine the behaviour. Looser restraints produce reptition. No restraints produce randomness. Balanced restraint produces complex behaviour. Rule 30 gives extremely random behaviour. Even when the whole system itself is boxed into a small number of cells, the period before repititon occurs is extremely long.

Wolfram studied systems that have global restraints that have to be satisfied and tried to get them to produce complex behaviour. It was very difficult to do so. Global restraints are very dificult to satisfy and almost always result in periodicity or uniformity.

@@@

Our discussion will now move into the philosohical implications of Wolfram's work. We will start off with the simple stuff and work our way up to complexity.

NOTE: I will be interjecting some of my own observations from time to time, so I hope no one tries to pin Wolfram down on something I specifically say. This paper is only my own impression of what his work is about.

3. SIMPLE BEHAVIOUR

History shows that human systems have developed over time from very simple beginnings. Math and science owe their success to the ability to extract regular features from natural systems. Our very own perceptual ability fundamentally uses pattern recognition at its core. We tend to notice and remember repeating patterns or features that are regular. Complex patterns elude our powers of description.

Our number systems reflect this propensity to seek patterns of regularity. All number systems for counting are based on repeating digits. This enables compact and efficient representation of values. Limits and convergences are essential aspects of mathemtics. We use such tricks to simplify equations and get values we can recognize and understand. Calculus is based on the idea of infinite limits. That little trick is a nifty way to avoid dealing with infinity itself.

Most mathematical formulas produce simple behaviour that is easy to cognize. Wolfram has shown that almost all mathematical formulae have simplicity at their heart and it is very difficult to get them to produce behaviour that is much more than periodic or nested. The very idea behind math to begin with is that it seems possible that we can always reduce complicated situations into simple symbolics given enough thought and ingenuity. This symbolic shorthand is what Wolfram calls computational reducibility. The idea is that a system viewed as a computation can somehow be simplified if a quicker way of performing the computation can be found. This is how scientists compute the orbit of a satellite (using Newton's simple law of gravity - a mathematical formula) so that the space shuttle knows where to go before the satellite gets there. The crux of the matter is that the symbolic computation must somehow run faster than the real life system. Man has always assumed that such computational reduction is always in principle possible. Wolfram shows in his work that this is not always the case. This sounds discouraging but it also reinforces the belief that the universe has simple principles at its core. It's just that the results may not always be simple.

Computational reducibility hinges on the ability to exploit regularities in behaviour. Fourier wave analysis, for example, breaks complicated patterns down into sums of periodic functions. Quantum physics is based on a quantum wave equation. Constraints yield periodic behaviour as we said above, so it is apparent why theoretical physics always tends to study constraints and limit conditions. Experimental physics tries to isolate and confine systems to simplify their behaviour. Quantum wells enable physicists to study simple electron states such as spin-up or spin- down.

Potential wells confine systems and tend to produce uniform behaviour. Systems, thus confined, tend toward equilibrium or oscillate. Again it is the regularites that we tend to observe, describe, analyze and exploit. Natural systems of gas particles are discrete but it is the overall behaviour of such systems in equilibrium that we tend to study i.e. steady state global properties like volume, temperatue, and pressure. It is only the gross global values that we seem able to grapple with even though we know that the system at the molecular level is quite simple itself.

One of the most difficult areas of theoretical science deals with fluid behaviour. Again we try to describe discrete behaviour with continuous functions. This approach is really tough going and ultimately doomed to failure, according to Wolfram. This is not to say that broad simplifications and formulae can't be used. It's just that there is a fundamental real limit as to what they can accomplish.

Hidden amidst almost the entire body of human thought is the belief that space and time are continuous. This simple naive belief persists in spite of the overwhelming evidence that nature has been found to be discrete down to the smallest levels. The majority of mathematics uses continuous functions because they are the ones that can be more easily analyzed, differentiated, and integrated. A little thought, though, must surely convince one that nature does not actually apply mathematical formula like Newton's Law on a case by case basis instantaneously. Something else must be going on.

Hidden in the use of continuous equations or formulae is the idea of infinity. Every value one gets from a computation is implicitly understood to have infinite accuracy. To actually write out any such number, however, requires an infinite string of digits. Even an infinitestimally small change in value propagates out to infinity as a totally different string of digits. The patterns thus produced by the digits themselves bear little relation to the actual value. The value is arrived at only after they are all added up. Computation by value is actually a perverse simplification of how patterns really behave. Computation by value is inherently oriented toward periodicity or nesting. Irrationals or transcendental numbers can at best be only approximated. Rational numbers have repeating digits. Wolfram's theory helps explain why 'computation by value' has its limits - no pun intended.

It thus becomes apparent that 'continuity' means non-local rules are in effect i.e. change in digit sequences must propagate out to infinity instantaneously. Discreteness, in contrast, means local rules are in effect and change propagates at finite speeds across a system. This idea ties in with our own group's ideas of locality and continuity as applied to hardware and software. Hardware is identified as actual real discrete features with local rules. Software is identified as symbolic continuous non-local shorthand. I leave it up to the reader to decide which is the more fundamental reality.

Wolfram has shown that it is very difficult to get continuous functions to display anything more than simple behaviour. Discrete systems in contrast easily produce very complex behaviour. One caveat should be mentioned here. Only a handful of the rules out of the possible ones actually produce complex behaviour. This fact has implications for the investigation of life and evolution. The important point for now is that complexity arises naturally once the appropriate rule is in effect. This complexity is to a large extent computationally irreducible. Wolfram thus dashes our belief in continuity but gives us something in return. He has not taken away our simplicity. Those methods still work where applicable. What he has done is to help us have a simple way of understanding complexity. This really hasn't been done before.

Ever since Bertalansky (spelling?), systems theory has been seen as very important, but little real progress has been made in unifying or establishing concrete principles of behaviour for all systems. Wolfram has established a foundation for such a science of systems. Much work has been done by other people on chaos theory, fractals, complexity etc. but the thrust has always been to use mathematics to analyze such systems and derive formulas or come up with proofs. It has been tough going obviously because of the fact that such systems are not often computationally reducible. They simply dont have the inherent regularities needed for symbolic exploitation.

Our very cognition and perceptual apparatus appears to be designed or evolved to filter out regularities. Patterns are perceived to be complex when we cant visually or otherwise lock in on some easily recognizable features. Even the neural structures of the sense organs and brain seem patterned on simple repitition. Complexity thus eludes us. That is in fact why we call such behaviour complex to begin with. While our own internal systems thus are built from the ground up on simple structures and rules, we as human beings nonetheless think and act in startlingly complex ways. Wolfram reassures us that this is completely natural and inevitable. The catch is that our own cognition is computationally irreducible. We simply cannot apply mathematical shorthand to analyze our own system states in totality. We must remain free willed and indeterminate relatively speaking in relation to our own internal states. Later Wolfram produces a stronger version of this argument and says that such a system is irreducible even from the outside by any system of equivalent or greater complexity.

Metalevel representation is at the heart of the ability to perform symbolic computation. This is how we are able to perform mathematical treatments to begin with. It will take further development of Wolfram's ideas to see what is meant by this point however, so we will leave this question till later in this paper. The next step along the path to complexity is the idea of randomness.

4. RANDOM BEHAVIOUR

At the core of Probability Theory are the twin ideas of random sampling and equal likelihood of events. These ideas have persisited in spite of the lack of any definitive reason to believe in them. Mathematics has failed to come up with any positive definition of randomness. The origins of these ideas go back to games of chance in which odds of an event influenced betting and vice versa. It was believed that the likelihood of a group of events happening was simply the numerical fraction of the total possible events because each event in itself was assumed to have an equal likelihood i.e. events happen at random. Special machines were constructed to ensure that this randomness was in effect. It was assumed that randomness were a fundamental fact of nature, but nature always seemed to need a little help. Equal likelihood is a gross supposition. It is sort of like believing that events have springs propelling them into existence. Equal likelihoods would have to have all their little springs set to the same push. To take a fraction of an event space as an odd or probability demands that you perform this sort of supposition otherwise the fractionation would be meaningless.

Smart gamblers know that physical devices always have regularities that can be exploited to improve one's odds. A roulette wheel, for example, is never perfect, and will always bias some bets. In fact, if a wheel were somehow perfect, it would never stop spinning.

So what is randomness, and where does it come from? Wolfram says randonmess has three sources. It either comes from outside, comes from random intial conditions, or is intrinsic. We have always assumed that many systems are random because so many perturbations come from the outside enviroment that the net result is random. This begs the question, however, for if randomness comes from the outside, where did that outside randomness come from?

Randomness from initial conditions is that presented by Chaos Theory. Many examples are given where sensitivity to random initial conditions results in a random system after some period of evolution. Wolfram shows that these models invariably involve kneading, mixing, shuffling, resampling etc. such that ultimately all they really produce is repeated or nested sequences of very long length. Psuedo or apparent randomness is all we really get. Such theories invariably use mathematical models or functions to anaylze the systems and are thus subject to the same reducibility constraints we mentioned above.

The third source says that randomness is somehow intrinsic to certain systems. Mathematics and science both ultimately must base their beliefs on this source, but neither has revealed any mechanism for such sources. In fact, it is my belief that randomness is the archetypal 'ghost in the machine'

I will explain what I mean. First, the only positive proceedures mathematics has come up with to detect randomness depend on finding some sort of regularities in a sequence being tested. There are any number of such tests designed to ferret out regularities, but if a sequence passes all the tests, there is no assurance it will pass the next test. The best definition of randomness math has come up with is that a sequence is random if no proceedure exists which can be encoded in a sequence shorter that the original itself. In terms of compression, this definition is stating that no regularities can be found so the sequence is incompressible, but compression always relies on picking out a particular model for what kind of regularities or redundancies to exploit. There's the catch again.

Now suppose we do have a random sequence. We must surely know that it cannot be expressed by some proceedure shorter than itself. Therefore let us say that we have a proceedure that works and is longer. Well, we could simply shorten it by merely using the sequence itself as our proceedure. but this is no proceedure at all. If it cant be shorter, and longer is superfluous, then what we are in effect saying is - no proceedure at all can exist. If no proceedure can ever hope to produce randomness, how on earth can intrinsic randomness occur. Aha 'the ghost in the machine'.

Part of the problem is that the mathematical definition is a negative statement so there are innumerable cases that must be tested before certainty arises. In effect we have a definiton for randomness that says no definition can exist! Now that's a real show stopper and explains why little progress has been made in that direction!

Einstein said that God does not play dice. Quantum physics says it does. In fact, many scientists use random sequences for their models and simulations that are derived from radioactive decay for example. Unfortunately quantum physics has no explanation for intrinsic randomness either. Indeed, it even says we can't know. Another ghost!

Math has produced many what are so-called psuedo-random generators. These are almost always based on functions which can be mathematically analyzed for periodicity. Many are in widespread use, but all seem to have some fatal flaw somewhere that presents a regularity even if the period is very very long. Wolfram claims that this is an inevitable result of using math functions because such functions have evolved over time with the precise intent of computational reducibility and are thus based on the exploitation of regularities.

So what is the answer? Wolfram says that the mundane idea of randomness is about all we really need. His claim is that anything we come up with is ultimately subject to or given impetus to by our natural abilities of cognition and perception anyway. Our perceptions are based on the ability to detect regularities from the get go. Having said that, he presents a nifty little toy - a genuine random generator with really simple rules. It is rule 30 in the simplest of all possible cellular automata systems. Wolfram has extensively analyzed the sequence of on/off cells directly below the peak in the rule 30 graph. It has survived every test for randomness yet devised. Using an array of only 100 cells he says it will eventually repeat because of the wrap around effect, but he claims the period before repitition is billions and billions of years of computer time.

Wolfram has been using rule 30 in his Mathematica program for years now. It is that good. Ok, so how the heck does an 8-bit rule manage to generate such a random sequence? Well, we said above (section 1 on cellular automata) it has to do with the unbridled flow and mixing of information through the celular field. The problem for some might be that in effect he is saying that an 8-bit number can represent a sequence of arbitrary length, so it obviously by definition cant be random. Think of the compression! Wolfram says this is an illusion, because to be of any such use, the rule has to be capable of being derived backwards from the sequence. This is essentially a problem of computational undecidability. Wolfram is pretty sure that rule 30 presents computational irreducibility and decoding it in reverse from its output is essentially impossible. It is also impossible in principle to predict subsequent output in any way other than actually carrying out the computation itself cell by cell.

The final conclusion Wolfram comes to is that intrinsic randomness is quite easy to achieve from simple rules. No one believed it possible to begin with so no one actually looked at such systems this way. He also says that such intrinsic randomness is thus very possible in natural systems. A vital point to be researched is that given the same initial conditions, the sequences will actually repeat exactly. He believes there is some experimental evidence that this does indeed happen sometimes in nature. Again it is a case that no one has ever bothered to look in that direction.

Finally I think we might say that our original beliefs about order rising out of chaos need to be revised. We must begin to think in terms of how chaos arises out of order. Order appears to stand in it's rightful place now - at the start with simple beginnings where it belongs. In the beginning was order.

I think we should also amend our statement that randomness is a function of parameters. Strictly speaking, the specific sequences are bound to initial conditions ( i.e. the parameters), but the process itself is intrinsic to specific simple rule sets.

This leads us to our next section - complexity. Here we will deal with the idea of computational irreducibility.

5. COMPLEX BEHAVIOUR

AND

THE UNIVERSAL PRINCIPAL OF COMPUTATIONAL EQUIVALENCE

We have seen in our original discussion of class 4 behaviour that complex systems defy our powers of description. We can perceive features and patches of randomness that change and move but no overall description seems possible because the ultimate fate of such systems is unknowable. From a computational viewpoint it is the halting problem Goedel dealt with in his famous theorem. Wolfram shows that such cellular systems can model logic functions and axiomatic systems and are subject to the same holes that Goedel's theorem dicloses.

Wolfram goes on to show how simple cellular systems can essentially model any function by using the appropriate rule and the right initial conditions. Next he shows how some cellular automata can be used to emulate other automata. The usual device was to let a group of cells in the original automata represent one cell in the automata being modeled. After some difficulty he finally found the right cell groupings and intial conditions to completely emulate the other.

Eventually Wolfram tried emulating other systems with success. Then he tried emulating a particular class of system known as a cyclic tag system that was already mathematically proven to be a Universal Turing Machine. Astoundingly he succeeded and thus proved that his model itself was thus a Universal Turing Machine.

The problem he faced next was that his particular model required some pretty complicated rules. His final coup was to model rule 110. He succeeded and definitively demonstrated that rule 110 is a class 4 Universal Turing Machine. He finally had the simplest Universal Turing Machine ever discovered - i.e. a 1 dim, 2 state machine with an 8-bit rule.

Wolfram then spent a few years investigating and emulating other systems and rules. What he found was that with enough effort, any system that produced class 4 behaviour could emulate any other class 4 system. He established that at a certain threshold, all systems that cross into class 4 behaviour become computationally equivalent as Universal Turing Machines.

The catch to all this is that such emulative equivalence occurs at a price, and some systems may involve thousands of steps to achieve what another does in a few. The incredible significance, however, is that adding system complexity does not improve computational ability past the point of universality. Efficiencies may be different but the final assay of what can be ultimately achieved becomes equivalent in all such systems.

What Wolfram has done is to show that many natural systems can very possibly be Universal Turing Machines and thus computationally equivalent. Once a very simple threshold of complexity is crossed, everything is possible, and rule 110 demonstrates that the threshold is very very low indeed. It is only because no one has thought to look in that direction that this fact has not yet been exploited in the fields of semiconductor design, nanotechnology, etc. It is only a matter of time before such ideas will come to fruition.

This idea has philosophical implications which we will now explore.

6. Intelligence, Evolution, and Free Will

Wolfram discusses many of the various qualifications for or descriptions of what we call intelligence. In each case he shows that there is no specific ability that we can actually describe that can't be emulated by some computation. UTMs (Universal Turing Machines) embody every aspect of intelligence that is capable of being precisely knowable. This is very similar to the case with randomness. One may argue the conundrum till one is blue in the face, but one can never come up with a counter example that doesn't involve 'the ghost in the machine' somewhere i.e. the invocation of metaphysical unknowables that are unknowable in principle. The pragmatic view is to just accept the low brow evidence and call it intelligence. Once one makes this very simple change in paradigm, a whole world of intelligent process is seen to abound in nature. The Universal Principle of Computational Equivalence demands that this be so.

Once one has gone that far, he begins to see that his normal view of what is intelligent is very anthropomorphic and must now embrace possibly even the memory traces worn in ancient cliffs of sandstone as parts of a bigger intelligence working on a (cellular?) scale immensely different from his own, yet still computationally equivalent. I needn't say what the ramifications for various religions might be.

...

Wolfram doesn't cover Evolution in great depth, but it is his position that natural selection cannot explain the incredible diversity of evolutionary forms. Fitness functions are more suited for adapting and triming forms or behaviours that are more or less stabilized already. This can be seen in the various bill lengths of Darwin's finches on the Galopagos Islands. The problem with genetic algorithms and fitness functions (the standard model for natural selection) is that they are hill climbing algorithms and easily get stuck on local maxima. In addition, when confronted with a large diversity of differences, such algorithms have difficulty in making selections so to speak. The enviromental factors, in essence, create a situation in which any survival advantage gained during one period of time is quickly superceded or nullified by subsequent conditions or genetic solutions. In my opinion, fitness functions are something of a red herring anyway. In my research programming genetic algorithms, I found that the system is very sensitive to how the fitness evaluator function is setup. The actual system itself does trivial pruning after that. The problem then becomes identified as how can so many enviromental fitness functions coexist and compete. In essence the fitness evaluation becomes the thing actually evolving not the DNA. Seen in this light, DNA would just be a coded solution to a particular computation, not the computation itself. This would immediately place evolution on a less secure basis ontologically as it would imply metaphysical movements directing the evolution of fitness challenges. I find this an untenable viewpoint. There is a much simpler answer.

It is Wolfram's view ( and mine) that all the complexity needed for explosive diversification is already instrinsic to the simple rules embodied in genetic systems. These ideas are corroborated by evolutionary epocs wherein there were great spurts of diversity followed by gradual trimming of the enduring forms that survive. Survival of the fittest in this scheme is more a question of intrinsic viability at inception.

I would like to take Wolfram's theoretical framework and extend it to the study of origins now. Scientists believe that the primordial broth a few billion years ago was rich and hearty with complex molecules. We know that certain groups of molecules can form self-organizing feedback reactions. These systems can be studied as networks whose nodes are various reaction products and whose connectivity is given by various reaction pathways between nodes. The presence of catalylic feedback reactions between groups of nodes can be seen as connectivity rules which cause the network connectivity to change and evolve over time. such a network can be directly modeled as a rule-based network having close analogues to cellular automata. Wolfram has studied such systems extensively and has shown that many can display class 4 behaviour. This means that they are computationally equivalent to Universal Turing Machines. It is my view that this is a most likely scenario.

Given an environment of vacuoles or colloids, such systems could contain reaction products long enough for class four behaviour to emerge. Possibly even, reaction byproducts could self-organize to form a primitive cell wall. There is still a problem of how to get actual genetic material organized. I have some speculations as to how this might occur. Given that we have UTMS (Universal Turing Machines) we know they are capable of emulating any other computational system. Recent experiments have also used polymerase reactions with nucleic base pair solutions to do simple computations (designed on purpose by humans of course). Now remember that UTM emulation can occur simply by choosing the right initial conditions. Recall also that emulation involves a computational ratio heavy on the emulator side with the emulated side being more compact and efficient. It is my guess that it might be possible that given the right initial conditions (chemical enviroment) an emulation might be triggered. This emulation would involve the elements of DNA (and other possible reactants) but at a different concentration and network connectivity than a finished DNA strand. The computational efficiency ratio being different would more or less guarantee this. The lower computational efficiency of the emulator system, however, just might manage to keep base pair products in close enough arrangement for them to spontaneously assemble into the actual system being emulated! Wolfram doesn't discuss this possibility but to me such a possibility is the most exciting thing about his new theory.

Before covering this exciting possibility, let's bring up another piece of data about DNA. We know it has four base pairs - C,G,A, and T. It seems likely also that genes basically have two states - switched on and off. It is also arranged in a one dimensional sequence like a Turing Tape machine. There are even tape head reader analogues like mitochondria and data inputs like RNA. I believe we have a very explicit case of a two state, four color Turing machine. Wolfram has shown that this is close to being the minimal Turing machine that can be Universal. Since both the rule-based network (chemical innards of cells) and the Turing machine systems (DNA) could be computationally equivalent, emulation and thus communication would be possible. The complexity or length of DNA strands has little to do with the complexity of the final organism as witnessed by massive chromosomes in some flies. Wolfram's Universal Principle of Computative Equivalence tells us that little is gained by additional complexity of rules past a certain minimum needed to achieve UTM status.

Now back to my idea of the possible power of emulation. I call it transubstantiation by computative assemblage. It would be the ultimate way to do nanotechnology. The emulator would perform the initial less compact emulation long enough for the more compact system being emulated to self-organize! There are a few wrinkles to iron out, but I think the idea is solid. The susbstrate (emulator UTM) being less computationally efficient would have a representative block equivalence larger and hence less dense or compact than the final assemblage, leaving room for the computationally superfluous elements to disperse. Different initial conditions would make different computational assemblages. Full blown UTMs would not have to be assembled. One could assemble specific computations.

There is another bonus to these sorts of ideas. Such computational emulation has a direction that points from the less compact emulator to the more compact emulated. Wolfram's technique involves letting a block or group of emulator side cells equal one cell on the emulated side of the process. This is representation pure and simple, and to me it implies that it just might be the fundamental mechanism behind semiosis and the ability to use symbols. There is still a problem though. Symbols lie on the representative side of emulation yet they are vastly more compact than the side of the relation being emulated. There is something missing in that picture. Ah, but what if symbols were instead identified as initial conditions along with the particular rule set to use? Bingo! That would be the key to setup the UTM for a particular emulative computation. As such symbols would serve to catalyze a particular substrate system into specific modes of emulative computation. The Universal Principle of Computative Equivalence actually assures this possibility according to Wolfram, and we have ample evidence to support the conjecture that neural networks and DNA systems express class 4 behaviour. This prospect implies that basically all living systems are capable of some form of semiosis.

Finally given this possibility, we might conjecture about human behaviour and language. Could it be possible that imitation sets up initial conditions for performing emulation? The neural substrate for humans must surely be the same for all of us or at least very close. Since we are all UTMs, our computative efficiency levels must be similar even if the computational states themselves are different. Given semiotic ability, similar UTMs could literally train each other by exchanging appropriate initial condition triggers. Imitation would thus lead to emulation and semiotic resonance between systems not in direct computational contact. As imitative-emulative rapport proceeds, transubstantiation of emulations could lead to actual symbolic mastery. Might this not be how language is learned and commmunicated? Initial conditions setting up similar UTMs to perform similar emulations would thus be a way of bridging the chasm of subjectivity presented by most philosophies.

I have only a few last points before I wind up this essay with my Extended Rules of Order. When a UTM performs a semiotic computation (emulation triggered by symbolic initial conditions), there is a level of representation going on. The emulated computation actually exists embedded in the original substrate only at a different degree of compactness. The compactness is not strictly spatial because it really involves emulator block length repititions in time. It is in one sense less compact because of this being embedded. It's only as a separate computative entity that it is computationally more efficient and compact. What I am trying to get at is that one computational pattern is in a way superimposed on the other. The substrate emulator process is really doing the work but it is actually performing another meta-level computation at the same time. Now if transubstantiation of connectivity can occur, then bingo, we have the possibility of meta-level recursion. The emulated process could in effect influence the emulator process. I think I have discovered a fundamental mechanism to support our own theories. When we throw in symbols as the semiotic initial conditions for UTM emulation, we have the possiblity of the compressive valving that I discuss in some of my other papers. The final products or output of such a system would in effect just be more symbols (intial conditions) which lead to other meta-level recursions.

A fascinating speculation at this point is a question I have. Wolfram has shown that rule 110 is a UTM and that rule 30 is random. He talks a bit about Goedel's Theorem and the lack of total completeness or consistency in all UTMs. This tells me that not all computations can occur in real time (i.e. certain computative proofs might not exist if we maintain consistency) He has even shown that UTMs can be about 90% or more complete though. The question I have is, if we start with one inital cell in rule 30, are all possible patterns eventually produced? If so, doesn't this provide a way for UTMs, emulating rule 30, to at least discover or encounter possible truths beyond what it can computationally achieve itself? Are we talking human intuition here?

What about a GOD rule. In a sub-quantum Universal rule set began some space-time computations that emerged during the big bang. How big would the rule set have to be? Going back to our DNA 2-state, four color UTM, we can see that there are 4x4x4 = 64 input patterns for a central cell with two neighbors along a one domensional DNA tape. With a 2-state tape reader, we have base 2 arithmetic so the rule sets or numbers can easily be shown to consist of 64 bit numbers. This is a huge possible number of possible rules. Only one is likely in actual use however. The vast majority would not turn out to be UTMs. They would exhibit the full range of class 1 through 4 behaviours. Maybe several different rules are possiblly in use as genetic UTMs. We just dont know yet. Still it's interesting to realize that apparently a 64 bit binary number is large enough to specify the underlying mechanism of DNA computative transcription. How big would GOD need to be. Wolfram suggests that simple rules are all you need, so GOD could be quite small after all.

Oops, I forgot about free will. Using a little of my own, I'll make this short and sweet. Wolfram has shown that network UTMs can have properties like Einsteinian relativity. One has to do translations of computations into speed of light information steps etc. but the main point is that we as UTMS in our own right are embedded within a larger UTM so we experience reality relatavistically within our own event cones. Being computationally irreducible ourselves we can be as free as we like. No other UTMs can ever computationally reducibly prove that we aren't.

This stuff is my own:

Extended Rules of Order

1. Order rules. Chaos and complexity arise from simple rules of order.

2. Confinement tends to produce uniformity and no flow of information.

3. Constraints tend to produce repitition and nesting with a restricted flow of information.

4. Randomness is intrinsic to specific simple rules of order. Randomness results from the unbridled flow of information.

5. Complexity generates Universal Computative Equivalence. Complexity is the balance of information flow between regularity and novelty.

6. Imitation forms the intial conditions for emulation.

7. Emulation enables metalevel recursion.

8. Metalevel recursion defines intelligence.

9. Different intelligences can have different computational efficiencies yet still communicate by emulative resonance.

10. Math is a small subset of all the possible modes of computation.

11. Man has yet to explore all the possible modes of computation.

12. Metaphysics is best defined as abstract pattern that is metalevel recursive upon a physical substrate. The 'ghost in the machine' is just an emulation.

13. Supraphysics with non-local rules is still a possibility, but it is not necessary to explain most complex phenomena unless that is ... space-time turns out to be based on a discrete non-local rule set from which locality emerges.

14. Local rules is the rule for hardware.

15. Non-local rules is the rule for software.