Wolfram concludes that ’the phenomenon of complexity is quite universal – and quite independent of the details of particular systems’. This complex behaviour does not depend on system features such as the way cellulare automata are typically arranged in a rigid array or that they are processed in parallel. Very simple rules of cellular automata generally lead to repetitive behaviour, slightly more complex rules may lead to nested behaviour and even more complex rules may lead to complex behaviour of the system. Complexity with regards to the underlying rules means how they can be intricate or their assembly or make-up is complicated. Complexity with regards to the behaviour of the overall system means that little or no regularity is observed.
The surprise is that the threshold for the level of complexity of the underlying rules to generate overall system complexity is relatively low. Conversely, above the threshold, there is no requirement for the rules to become more complex for the overall behaviour of the system to become more complex.
And vice versa: even the most complex of rules are capable of producing simple behaviour. Moreover: the kinds of behaviour at a system level are similar for various kinds of underlying rules. They can be categorized as repetitive, nested, random and ‘including localized structures’. This implies that general principles exist that produce the behaviour of a wide range of systems, regardless of the details of the underlying rules. And so, without knowing every detail of the observed system, we can make fundamental statements about its overall behaviour. Another consequence is that in order to study complex behaviour, there is no need to design vastly complicated computer programs in order to generate interesting behaviour: the simple programs will do [Wolfram, 2002, pp. 105 – 113].
Systems used in textbooks for complete analysis may have a limited capacity to generate complex behaviour because they, given the difficulties to make a complete analysis, are specifically chosen for their amenability to complete analysis, hence of a simple kind. If we ignore the need for analysis and look only at results of computer experiments, even simple ‘number programs’ can lead to complex results.
One difference is that in traditional mathematics, numbers are usually seen as elementary objects, the most important attribute of which is their size. Not so for computers: numbers must be represented explicity (in their entirety) for any computer to be able to work with it. This means that a computer uses numbers as we do: by reading them or writing them down fully as a sequence of digits. Whereas we humans do this on base 10 (0 to 9), computers typically use base 2 (0 to 1). Operations on these sequences have the effect that the sequences of digits are updated and change shape. In tradional mathematics, this effect is disregarded: the effect of an operation on a sequence as a consequence of an operation is considered trivial. Yet this effect amongst others is by itself capable of introducing complexity. However, even when the size only is represented as a base 2 digit sequence when executing a simple operator such as multiplication with fractions or even whole numbers, complex behaviour is possible.
‘Indeed, in the end, despite some confusing suggestions from traditional mathematics, we will discover that the general behavior of systems based on numbers is very similar to the general behavior of simple programs that we have already discussed‘ [Wolfram, 2002, p 117].
The underlying rules for systems like cellular automata are usually different from those for systems based on numbers. The main reason forr that is that rules for cellular automata are always local: the new color of any particular cell depends only on the previous colour of that cell and its immediate neighbours. But in systems based on numbers there is usually no such locality. But despite the absence of locality in the underlying rules of systes based on numbers it is possible to find localized structures also seen in cellular automata.
When using recursive functions of a form such as f(n) = f(n – f(n- 1) then only subtraction and addition are sufficient for the development of small programs based on numbers that generate behaviour of great complexity.
‘And almost by definition, numbers that can be obtained by simple mathematical operations will correspond to simple such (symbolic DPB) expressions. But the problem is that there is no telling how difficult it may be to compute the actual value of a number from the symbolic expression that is used to represent it‘ [Wolfram, 2002, p143].
Adding more dimensions to a cellular automaton or a turing machine does not necessarily mean that the complexity increases.
‘But the crucial point that I will discuss more in Chapter 7 is that the presence of sensitive dependence on initial conditions in systems like (a) and (b) in no way implies that it is what is responsible for the randomness and complexity we see in these systems. And indeed, what looking at the shift map in terms of digit sequences shows us is that this phenomenon on its own can make no contribution at all to what we can reasonably consider the ultimate production of randomness‘ [Wolfram, 2002, p. 155].
The design of this class of systems is so that the systems can have multiple states at any one step. The states at some time generate states at the nex step according to the underlying rules. All states thus generated remain in place after they have been generated. Most Multiway systems grow very fast or not at all and slow growth is as rare as is randomness. The usual behaviour is that repetition occurs, even if it is after a large number of seemingly random states. The threshold seems to be in the rate of growth: if the system is allowed to grow faster then the chances that it will show complex behaviour increases. In the process, however, it generates so many states that it becomes difficult to handle [Wolfram 2002, pp. 204 – 209].
Chapter 6: Starting from Randomness
If systems are started with random initial conditions (up to this point they started with very simple initial conditions such as one black or one white cell), they manage to exhibit repetitive, nested as well as complex behaviour. They are capable of generating a pattern that is partially random and partially locally structured. The point is that the intial conditions may be in part but not alone responsible for the existence of complex behaviour of the system [Wolfram 2002, pp. 223 – 230].
Class 1 – the behaviour is very simple and almost all initial conditions lead to exactly the same uniform final state
Class 2 – there are many different possible final states, but all of them consist just of a certain set of simple structures that either remain the same forever or repeat every few steps
Class 3 – the behaviour is more complicated, and seems in many respects random, although triangles and other small-scale structures are essentially always on some level seen
Class 4 – this class of systems involves a mixture of order and randomness: localized structures are produced which on their own are fairly simple, but these structures move around and interact with each other in very complicated ways.
‘There is no way of telling into which class a cellular automaton falls by studying its rules. What is needed is to run them and visually ascertain which class it belongs to’ [Wolfram 2002, Chapter 6, pp.235].
One-dimensional cellular automata of Class 4 are often on the boundary between Class 2 and Class 3, but settling in neither one of them. There seems to be some kind of transition. They do have characteristics of their own, notably localized structures, that do neither belong to Class 2 or Class 3 behaviour. This behaviour including localized structures can occur in ordinary discrete cellular automata as well as in continuous cellular automata as well as in two-dimensional cellular automata.
Sensitivity to Initial Conditions and Handling of Information
Class 1 – changes always die out. Information about a change is always quickly forgotten
Class 2 – changes may persist, but they remain localized, contained in a part of the system. Some information about the change is retained in the final configuration, but remains local and therefore not communicated thoughout the system
Class 3 – changes spread at a uniform rate thoughout the entire system. Change is communicated long-range given that local structures travelling around the system are affected by the change
Class 4 – changes spread sporadically, affecting other cells locally. These systems are capable of communicating long-range, but this happens only when localized structures are affected [Wolfram 2002, p. 252].
In Class 2 systems, the logical connection between their eventually repetitive behaviour and the fact that no long-range communication takes place is that the absence of long-range communication forces the system to behave as if its size were limited. This behaviour follows a general result that any system of limited size, discrete steps and definite rules will repeat itself eventually.
In Class 3 systems the possible sources of randomness are the randomness present in initial conditions (in the case of a cellular automaton the initial cells are chosen at random versus one single black or white cell for simple initial conditions) and the sensitive dependence on initial conditions of the process. Random behaviour in a Class 3 system can occur if there is no randomness in its initial conditions. There is not an a priori difference in the behaviour of most systems generated on the basis of random initial conditions and one based on simple intial conditions1. The dependence on the initial conditions of the patterns arising in the pattern in the overall behaviour of the system is limited in the sense that although the produced randomness is evident in many cases, the exact shape can differ from the initial conditions. This is a form of stability, for, whatever the initial conditions the system has to deal with, it always produces similar recognizable random behaviour as a result.
In Class 4 there must be some structures that can persist forever. If a system is capable of showing a sufficiently complicated structure then eventually at some initial condition, a moving structure is found also. Moving structures are inevitable in Class 4 systems. It is a general feature of Class 4 cellular automata that with appropriate initial conditions they can mimick the behaviour of all sorts of other systems. The behaviour of Class 4 cellular automata can be diverse and complex even though their underlying rules are very simple (compared to other cellular automata). The way that diffferent structures existing in Class 4 systems interact is difficult to predict. The behaviour resulting from the interaction is vastly more complex than the behaviour of the individual structures and the effects of the interactions may take a long time (many steps) after the collision to become clear.
It is common to be able to design special initial conditions so that some cellular automaton behaves like another. The trick is that the special initial conditions must then be designed so that the behaviour of the cellular automaton emulated is contained within the overall behaviour of the other cellular automaton.
The behaviour of a cellular automaton depends on the specified initial conditions. The behaviour of the system, the sequences shown, gets progressively more restricted as the system develops. The resulting end-state or final configuration can be thought of as an attractor for that cellular automaton. Usually many different but related initial conditionss lead to the same end-state: the basin of attraction leads it to an attractor, visible to the observer as the final configuration of the system.
Chapter 7 Mechanisms in Programs and Nature
Processes happening in nature are complicated. Simple programs are capable of producing this complicated behaviour. To what extent is the behaviour of the simple programs of for instance cellular automata relevant to phenomena observed in nature? ‘It (the visual similarity of the behaviour of cellular automata and natural processes being, DPB) is not, I believe, any kind of coincidence, or trick of perception. And instead what I suspect is that it reflects a deep correspondence between simple programs and systems in nature‘ [Wolfram 2002, p 298].
Striking similarities exist between the behaviours of many different processes in nature. This suggests a kind of universality in the types of behaviour of these processes, regardless the underlying rules. Wolfram suggests that this universality of behaviour encompasses both natural systems’ behaviour and that of cellular automata. If that is the case, studying the behaviour of cellular automata can give insight into the behaviour of processes occurring in nature. ‘For it (the observed similarity in systems behaviour, DPB) suggests that the basic mechanisms responsible for phenomena that we see in nature are somehow the same as those responsible for phenomena that we see in simple programs‘ [Wolfram 2002, p 298].
A feature of the behaviour of many processes in nature is randomness. Three sources of randomness in simple programs such as cellular automata exist:
the environment – randomness is injected into the system from outside from the interactions of the system with the environment.
initial conditions – the initial conditions are a source of randomness from outside. The randomness in the system’s behaviour is a transcription of the randomness in the initial conditions. Once the system evolves, no new randomness is introduced from interactions with the environment. The system’s behaviour can be no more random than the randomness of the initial conditions. In practical terms many times isolating a system from any outside interaction is not realistic and so the importance of this category is often limited.
intrinsic generation – simple programs often show random behaviour even though no randomness is injected from interactions with outside entities. Assuming that systems in nature behave like the simple programs, it is reasonable to assume that the intrinsic generating of randomness occurs in nature also. How random is this internally generated randomness really? Based on tests using existing measures for randomness they are at least as random as any process seen in nature. It is not random by a much used definition classifying behaviour as random if it can never be generated by a simple procedure such as the simple programs at hand, but this is a conceptual and not a practical definition. A limit to the randomness of numbers generated with a simple program, is that it is bound to repeat itself if it exists in a limited space. Another limit is the set of initial conditions: because it is deteministic, running a rule twice on the same initial conditions will generate the same sequence and the same random number as a consequence. Lastly truncating the generated number will limit its randomness. The clearest sign of intrinsic randomness is its repeatability: in the generated graphs areas will evolve with similar patterns. This is not possible starting from different initial conditions or with external randomness injected while interacting. The existence of intrinsic randomness allows a discrete system to behave in seemingly continuous ways, because the randomness at a local level averages out the differences in behaviour of individual simple programs or system elements. Continuous systems are capable of showing discrete behaviour and vice versa.
‘But despite this (capability of constraints to force complex behaviour DPB) my strong suspicion is that of all of the examples we see in nature almost none can in the end best be explained in terms of constraints‘ [Wolfram 2002, p 342]. Constraints are a way of making a system behave as the observer wants it to behave. To find out which constraints are required to deliver the desired behaviour of a system in nature is in practical terms far too difficult. The reason for that difficulty is that the number of configurations in any space soon becomes very large and it seems impossible for systems in nature to work out which constraint is required to satisfy the constraints at hand, especially if this procedure needs to be performed routinely. Even if possible the procedure to find the rule that actually satisfies the constraint is so cumbersome and computationally intensive, that it seems unlikely that nature uses it to evolve its processes. As a consequence nature seems to not work with constraints but with explicit rules to evolve its processes.
Implications for everyday systems
Intuitively from the perspective of traditional science the more complex is the system, the more complex is its behaviour. It has turned out that this is not the case: simple programs are much capable of generating compicated behaviour. In general the explicit (mechanistic) models show behaviour that confirms the behaviour of the corresponding systems in nature, but often diverges in the details.
The traditional way to use a model to make predictions about the behaviour of an observed system is to input a few numbers from the observed system in your model and then to try and predict the system’s behaviour from the outputs of your model. When the observed behaviour is complex (for example if it exhibits random behaviour) this approach is not feasible.
If the model is represented by a number of abstract equations, then it is unlikely (nor was it intended) that the equations describe the mechanics of the system, but only to describe its behaviour in whatever way works to make a prediction about its future behaviour. This usually implies disregarding all the details and only taking into account only the important factors driving the behaviour of the system.
Using simple programs, there is also no direct relation between the behaviour of the elements of the studied system and the mechanics of the program. ‘.. all any model is supposed to do – whether it is a cellular automaton, a differential equation or anything else – is to provide an abstract representation of effects that are important in detemining the behaviour of a system. And below the level of these effects there is no reason that the model should actually operate like the system itself‘ [Wolfram 2002, p 366].
The approach in the case of the cellular automata is to then visually compare (compare the pictures of) the outcomes of the model with the behaviour of the system and try and draw conclusions about similarities in the behaviour of the observed system and the created system.
Genetic material can be seen as the programming of a life form. Its lines contain rules that determine the morphology of a creature via the process of morphogenesis. Traditional darwinism suggests that the morphology of a creature determines its fitness. Its fitness in turn detemines its chances of survival and thus the survival of its genes: the more individuals of the species survive, the bigger its representation in the genepool. In this evolutionary process, the occurrence of mutations will add some randommness, so that the species continuously searches the genetic space of solutions for the combination of genes with the highest fitness.
‘The problem of maximizing fitness is essentially the same as the problem of satisfying constraints..‘ [Wolfram 2002, p386]. Sufficiently simple constraints can be satisfied by iterative random searches and converge to some solution, but if the constraints are complicated then this is no longer the case.
Biological systems have some tricks to speed up this process, like sexual reproduction to mix up the genetic offspring large scale and genetic differentiation to allow for localized updating of genetic information for separate organs.
Wolfram however consides it ‘implausible that the trillions or so of generations of organisms since the beginning of life on earth would be sufficient to allow optimal solutions to be found to constraints of any significant complexity‘ [Wolfram 2002 p 386]. To add insult to injury, the design of many existing organisms is far from optimal and is better described as a make-do, easy and cheap solution that will hopefully not immediately be fatal to its inhabitant.
In that sense not every feature of every creature points at some advantage towards the fitness of the creature: many features are hold-overs from elements evolved at some earlier stage. Many features are so because they are fairly straightforward to make based on simple programs and then they are just good enough for the species to survive, not more and not less. Not the details filled in afterwards, but the relatively coarse features support the survival of the species.
In a short program there is little room for frills: almost any mutation in the program will tend to have an immediate effect on at least some details of the phenotype. If, as a mental exercise, biological evolution is modeled as a sequence of cellular automata, using each others output sequentially as input, then it is easy to see that the final behaviour of the morphogenesis is quite complex.
It is, however, not required that the program be very long or complicated to generate complexity. A short program with some essential mutations suffices. The reason that there isn’t vastly more complexity in biological systems while it is so easy to come by and while the forms and patterns usually seen in biological systems are fairly simple is that: ‘My guess is that in essence it (the propensity to exhibit mainly simple patterns DPB) reflects limitations associated with the process of natural selection .. I suspect that in the end natural selection can only operate in a meaningful way on systems or parts of systems whose behaviour is in some sense quite simple‘ [Wolfram 2002, pp. 391 – 92]. The reasons are:
when behaviour is complex, the number of actual configurations quickly becomes too large to explore when the layout of different individuals in a species becomes very differnent then the details may have a different weight in their survival skills. If the variety of detail becomes large then acting consitently and definitively becomes increasingly difficult when the overall behaviour of a system is more complex then any of its subsystems, then any change will entail a large number of changes to all the subsystems, each with a different effect on the behaviour of the individual systems and natural selection has no way to pick the relevant changes
if chances occur in many directions, it becomes very difficult for changes to cancel out or find one direction and thus for natural selection to understand what to act on iterative random searches tend to be slow and make very little progress towards a global optimum.
If a feature is to be succesfully optimized for different environments then it must be simple. While it has been claimed that natural selection increases complexity of organisms, Wolfram suggests that it reduces complexity: ..’it tends to make biological systems avoid complexity, and be more like systems in engineering‘ [Wolfram 2002, p 393]. The difference is that in engineering systems are designed and developed in a goal oriented way, whereas in evolution it is done by an iterative random search process.
There is evidence from the fossil record that evolution brings smooth change and relative simplicity of features in biological systems. If all this evoltionary process points at simple features and smooth changes, then where comes the diversity from? It turns out that a change in the rate of growth changes the shape of the organism dramatically as well as its mechanical operation.
‘My approach in investigating issues like the Second Law is in effect to use simple programs as metaphors for physical systems. But can such programs in fact be more than that? And for example is it conceivable that at some level physical systems actually operate directly according to the rules of a simple program? ‘ [Wolfram 2002, p. 434].
Out of 256 rules for cellular automata based on two colours and nearest neighbour interaction, only six exhibit reversible behaviour. This means that overall behaviour can be reversed if the rules of each automaton are played backwards. Their behaviour, however, is not very interesting. Out of 7,500 billion rules based on three colours and next-neighbour interaction, around 1,800 exhibit reversible behaviour of which a handful shows interesting behaviour.
The rules can be designed to show reversible behaviour if their pictured behaviour can be mirrored vertically (the graphs generated are usually from top to bottom, DPB): the future then looks the same as the past. It turns out that the pivotal design feature of reversible rules is that existing rules can be adapted to add dependence on the states of neighbouring cells two steps back. Note that this reversibily of rules can also be constructed by using the preceding step only, if, instead of two states, four are allowed. The overall behaviour showed by these rules is reversible, whether the intial conditons be random or simple. It is shown that a small fraction of the reversible rules exhibit complex behaviour for initial conditions that are simple or random alike.
Whether this reversibility actually happens in real life depends on the theoretical definition of the initial conditions and in our ability to set them up so as to exhibit the reversible overall behaviour. If the initial conditons are exactly right then increasingly complex behaviour towards the future can become simpler when reversed. In practical terms this hardly ever happens, because we tend to design and implement the intial conditions so that they are easy to describe and construct to the experimenter. It seems reasonable that in any meaningful experiment, the activities to set up the experiment should be simpler than the process that the experiment is intended to observe. If we consider these processes as computations, then the computations required to set up the experiment should be simpler than the computations involved in the evolution of the system under review. So starting with simple initial conditions and trace back to the more complex ones, then, starting the evolution of the system there anew, we will surely find that the system shows increasingly simple behaviour. Finding these complicated seemingly random initial conditions in any other way than tracing a reversible process to and fro the simple initial conditions seems impossible. This is also the basic argument for the existence of the Second Law of Thermodynamics.
Entropy is defined as the amount of information about a system that is still unknown after measurements on the system. The Second Law means that if more measurements are performed over time then the entropy will tend to decrease. In other words: should the observer be able to know with absolute certainty properties such as the positions and velocities of each particle in the system, then the entropy would be zero. According to the definition entropy is the information with which it would be possible to pick out the configuration the system is actually in from every possible configuration of the distribution of particles in the system satisfying the outcomes of the measurements on the system. To increase the number and quality of the measurements involved amounts to the same computational effort as is required for the actual evolution of the system. Once randomness is produced, the actual behaviour of the system becomes independent of the details of the initial conditions of the system. In a reversible system different initial conditions must lead to a diffent evolution of the system, for else there would be no way of reversing the system behaviour in a unique way. But even though the outcomes from different initial conditions can be much different, the overall patterns produced by the system can still look much the same. But to identify the initial conditions from the state of a system at any time implies a computational effort that is far beyond the effort for a practical and meaningful measurement procedure. If a system generates sufficient randomness, then it evolves towards a unique equilibrium whose properties are for practical reasons independent of its initial conditions. In this why it is possible to identify many systems based on a few typical parameters.
‘With cellular automata it is possible, using reversible rules and starting from a random set of initial conditions, to generate behaviour that increases order instead of tending towards more random behaviour, e.g. rule 37R [Wolfram 2002, pp. 452 – 57]. Its behaviour neither completely settles down to order nor does it generate randomness only. Although it is reversible, it does not obey the Second Law. To be able to reverse this process, however, the experimenter would have to set up initial conditions exactly so as to be able to reach the ‘earlier’ stages, else the information generated by the system is lost. But how can there be enough information to reconstruct the past? All the intermediate local structures that passed on the way to the ’turning point’ would have to be absorbed by the system on its way back to in the end to reach its original state. No local structure emitted on the way to the turning point can escape.
The evolution in systems is therefore intrinsically? not reversible. All forms of self organisation in cellular automata without reversible rules can potentially occur?
For these reasons it is possible to parts of the universe get more organised than other parts, even with all laws of nature being reversible. What the cellular automata such as 37R show is that this is even possible for closed systems to not follow the Second Law. If the systems gets partitioned then within the partitions order might evolve while simultaneously elsewhere in the system randomness is generated. Any closed system will repeat itself at some point in time. Until then it must visit every possible configuration. Most of these will be or seem to be random. Rule 37R does not produce this ergodicity: it visits only a small fraction of all possible states before repeating.
Conserved Quantities and Continuum Phenomena
Examples are quantities of energy and electric charge. Can the amount of information in exchanged messages be a proxy for a quantity to be conserved?
With nearest neighbour rules, cellular automata do exhibit this principle (shown as the number of cells of equal colour conserved in each step), but without showing sufficient complex behaviour. Using next-neighbour rules, they are capable of showing conservation while exhibiting interesting behaviour also. Even more interesting and random behaviour occurs when block cells are used, especially using three colours instead of two. In this setup the total number of black cells must remain equal for the entire system. On a local level, however, the number of black cells does not necessarily remain the same.
In a multiway system all possible replacements are always executed at every step, thereby generating many new strings (i.e. combinations of added up replacements) at each step. ‘In this way they allow for multiple histories for a system. At every step multiple replacements are possible and so, tracing back the different paths from string to string, different histories of the system are possible. This may appear strange, for our understanding of the universe is that it has only one history, not many. But if the state of the universe is a single string in the multiway system, then we are part of that string and we cannot look into it from the outside. Being on the inside of the string it is our perception that we follow just one unique history and not many. Had we been able to look at it from without, then the path that the system followed would seem arbitrary‘ [Wolfram 2002, p 505]. If the universe is indeed a multiway system then another source of randomness is the actual path that its evolution has followed. This randomness component is similar to the outside randomness discussed earlier, but different in the sense that in would occur even if this universe would be perfectly isolated from the rest of the universe.
There are sufficient other sources of randomness to explain interesting behaviour in the universe and that by itself is no sufficient reason to assume the multiway system as a basis for the evolution of the universe. What other reasons can there be to underpin the assumption that the underlying mechanism of the uiverse is a multiway system? For one, multiway systems are much capable of generating a vast many different possible strings and therefore many possible connections between them, meaning different histories.
However, looking at the sequences of those strings it becomes obvious that these can not be arbitrary. Each path is defined by a sequence of ways in which replacements by multiway systems’ rules are applied. And each such path in turn defines a causal network. Certain underlying rules have the property that the form of this causal network ends up being the same regardless of the order in which the replacements are applied. And thus regardless of the path that is followed in the multiway system. If the multiway system ends up with the same causal network, then it must be possible to apply a replacement to a string already generated, to end up at the same final state. Whenever paths always eventually converge then there will be similarities on a sufficiently large scale in the obtained causal networks. And so the structure of the causal networks may vary a lot at the level of individual events. But at a sufficiently large level, the individual details will be washed out and the structure of the causal network will be essentially the same: on a sufficiently high level the universe will appear to have a unique history, while the histories on local levels are different.
Processes of perception and analysis
The processes that lead to some forms of behaviour in systems are comparable to some processes that are involved in their perception and analysis. Perception relates to the immediate reception of data via sensory input, analysis involves conscious and computational effort. Perception and analysis are an effort to reduce events in our everyday lives to manageable proportions so that we can use them. Reduction of data happens by ignoring whatever is not necessary for our everyday survival and by finding patterns in the remaining data so that individual elements in the data do not need to be specified. If the data contains regularities then there is some redundance in the data. The reduction is important for reasons of storage and communication.
This process of perception and analysis is the inverse of the evolving of systems behaviour from simple programs: to identify whatever it is that produces some kind of behaviour. For observed complex behaviour this is not an easy task, for the complex behaviour generated bears no obvious relation to the simple programs or rules that generate them. An important difference is that there are many more ways to generate complex behaviour than there are to recognize the origins of this kind of behaviour. The task of finding the origins of this behaviour is similar to solving problems satisfying a set of constraints.
Randomness is roughly defined as the apparent inability to find a regularity in what we perceive. Absence of randomness implies that redundancies are present in what we see, hence a shorter description can be given of what we see that allows us to reproduce it. In the case of randomness, we would have no choice but to repeat the entire picture, pixel by pixel, to reproduce it. The fact that our usual perceptional abilities do not allow such description doesn’t mean that no such description exists. It is very much possible that randomness is generated by the repetition of a simple rule a few times over. Does it, then, imply that the picture is not random? From a perceptory point of view it is, because we are incapable to find the corresponding rule, from a conceptual point of view this definition is not satisfactory. In the latter case the definition would be that randomness exists if no such rule exists and not only if we cannot immediately discern it. However, finding the short description, i.e. the short program that generates this random behaviour is not possible in a computationally finite way. Resticting the computational effort to find out whether something is random seems unsatisfactory, because it is arbitrary, it still requires a vast amount of computational work and many systems will not be labelled as random for the wrong reasons. So in the definition of randomness some reference needs to be made to how the short descriptions are to be found. ‘..something could be considered to be random whenever there is essentially no simple program that can succeed in detecting regularities in it‘ [Wolfram 2002, p 556]. In practical terms this means that after comparing the behaviour of a few simple programs with the behaviour of the observed would-be random generator and if no regularities are found in it, then the behaviour of the observed system is random.
If we say that something is complex, we say that we have failed to find a simple description for it hence that our powers of perception and analysis have failed on it. How the behaviour is described depends on what purpose the description serves, or how we perceive the observed behaviour. The assessment of the involved complexity may differ depending on the purpose of the observation. Given this purpose, then the shorter the description the less complex the behaviour. The remaining question is whether it is possible to define complexity independent of the details of the methods of perception and analysis. The common opinion traditionally was that any complex behaviour stems from a complex system, but this is no longer the case. It takes a simple program to develop a picture for which our perception can find no simple overall description.
‘So what this means is that, just like every other method of analysis that we have considered, we have little choice but to conclude that traditional mathematics and mathematical formulas cannot in the end realistically be expected to tell us very much about patterns generated by systems like rule 30‘ [Wolfram 2002, p 620].
Human thinking stands out from other methods of perception in its extensive use of memory, the usage of the huge amount of data that we have encountered and interacted with previously. The way human memory does this is by retrieval based on general notions of similarity rather than exact specifications of whatever memory item is that we are looking for. Hashing could not work, because similar experiences summarized by different words might end up being stored in completely different locations and the relevant piece of information might not be retrieved on the occasion that the key search word involved hits a different hash code. What is needed is information that really sets one piece of information apart from other pieces, to store that and to discard all others. The effect is that the retrieved information is similar enough to have the same representation and thus to be retrieved of some remotely or seemingly remote association occurs with some situation at hand.
This can be achieved with a number of templates that the information is compared with. Only if the remaining signal per layer of nerve cells generates a certain hash code then the information is deemed relevant and retrieved. It is very rare that a variation in the input results in a variation in the output; in other words: quick retrieval (based on the hash code) of similar (not necessarily exactly the same) information is possible. The stored information is pattern based only and not stored as meaningful or a priori relevant information.
‘But it is my strong suspicion that in fact logic is very far from fundamental, particularly in human thinking‘ [Wolfram 2002, 627]. We retrieve connections from memory without too much effort, but perform logical reasoning cumbersomely, going one step after the next, and it possible that we are in that process mainly using elements of logic that we have learned from previous experience only.
Chapter 11 The Notion of Computation
All sorts of behaviour can be produced by simple rules such as cellular automata. There is a need for a framework for thinking about this behaviour. Traditional science provides this framework only if the observed behaviour is fairly simple. What can we do if the observed behaviour is more complex? The key-idea is the notion of computation. If the various kinds of behaviour are generated by simple rules, or simple programs then the way to think about them is in terms of the computations they can perform: the input is provided by the initial conditions and the output by the state of the system after a number of steps. What happens in between is the computation, in abstract terms and regardless the details of how it actually works. Abstraction is useful when discussing systems’ behaviour in a unified way, regardless the different kinds of underlying rules. For even though the internal workings of systems may be different, the computations they perform may be similar. At this pivot it may become possible to formulate principles applying to a variety of different systems and independent of the detailed structures of their rules.
‘At some level, any cellular automaton – or for that matter, any system whatsoever – can be viewed as performing a computation that determines what its future behaviour will be‘ [Wolfram, 2002, p 641]. And for some of the cellular automata described it so happens that the computations they perform can be described to a limited extent in traditional mathematical notions. Answers to the question of the framework come from practical computing.
The Phenomenon of Universality
Based on our experience with mechanical and other devices it can be assumed that we need different underlying constructions for different kinds of tasks. The existence of computers has shown that different underlying constructions make universal systems that can be made to execute different tasks by being programmed in different ways. The hardware is the same, different software may be used, programming the computer for different tasks.
This idea of universality is also the basis for programming languages, where instructions from a fixed set are strung together in different ways to create programs for different tasks. Conversely any computer programmed with a program designed in any language can perform the same set of tasks: any computer system or language can be set up to emulate one another. An analog is human language: virtually any topic can be discussed in any language and given two languages, it is largely possible to always translate between them.
Are natural systems universal as well? ‘The basic point is that if a system is universal, then it must effectively be capable of emulating any other system, and as a result it must be able to produce behavior that is as complex as the behavior of any other system. So knowing that a particular system is universal thus immediately implies that the system can produce behavior that is in a sense arbitrarily complex‘ [Wolfram 2002, p 643].
So as the intuition that complex behaviour must be generated by complex rules is wrong, so the idea that simple rules cannot be universal is wrong. It is often assumed that universality is a unique and special quality but now it becomes clear that it is widespread and occurs in a wide range of systems including the systems we see in nature.
It is possible to construct a universal cellular automaton and to input initial conditions so that it emulates any other cellular automata and thus to produce any behaviour that the other cellular automaton can produce. The conclusion is (again) that nothing new is gained by using rules that are more complex than the rules of the universal cellular automaton, because given it, more complicated rules can always be emulated by the simple rules of the universal cellular automaton and by setting up appropriate initial conditions. Universality can occur in simple cellular automata with two colours and next-neighbour rules, but their operation is more difficult to follow than cellular automata with a more complex set-up.
Emulating other Systems with Cellular Automata
Mobile cellular automata, cellular automata that emulate Turing machines, substitution systems2, sequential substitution systems, tag systems, register machine, number systems and simple operators. A cellular automaton can emulate a practical computer as it can emulate registers, numbers, logic expressions and data retrieval. Cellular automata can perform the computations that a practical computer can perform.
And so a universal cellular automaton is universal beyond being capable of emulating all other cellular automata: it is capable of emulating a vast array of other systems, including practical computers. Reciprocally all other automata can be made to emulate cellular automata, including a universal cellular automaton, and they must therefore itself be universal, because a universal cellular automaton can emulate a wide array of systems including all possible mobile automata and symbolic systems. ‘By emulating a universal cellular automaton with a Turing machine, it is possible to construct a universal Turing machine‘ [Wolfram 2002, p 665].
‘And indeed the fact that it is possible to set up a univeral system using essentially just the operations of ordinary arthmetic is closely related to the proof af Godel’s Theorem‘ [Wolfram 2002, p 673].
Implications of Universality
All of the discussed systems can be made to emulate each other. All of them have certain features in common. And now, thinking in terms of computation, we can begin to see why this might be the case. They have common features just because they can be made to emulate each other. The most important consequence is that from a computational perspective a very wide array of systems with very different underlying structures are at some level fundamentally equivalent. Although the initial thought might have been that the different kinds of systems would have been suitable for different kinds of computations, this is in fact not the case. They are capable of performing exactly the same kinds of computations.
Computation therefore can be discussed in abstract terms, independent of the kind of system that performs the computation: it does not matter what kind of system we use, any kind of system can be programmed to perform any kind of computation. The results of the study of computation at an abstract level are applicable to a wide variety of actual systems.
To be fair: not all cellular automata are capable of all kinds of computations, but some have large computational capabilties: once past a certain threshold, the set of possible computations will be always the same. Beyond that threshold of universality, no additional complexity of the underlying rules might increase the computational capabilties of the system. Once the threshold is passed, it does not matter what kind of system it is that we are observing.
The rule 110 Cellular Automaton
The threshold for the complexity of the underlying rules required to produce complex behaviour is remarkably low.
Class 4 Behaviour and Universality
Rule 110 with random initial conditions exhibits many localized structures that move around and interact with each other. This is not unique to that rule, this kind of behaviour is produced by all cellular automata of Class 4. The suspicion is that any Class 4 system will turn out to have universal computational capabilities. For the 256 nearest-neighbour rules and two colours, only four more or less comply (rule 124, 137 and 193, all require some trivial amendments). But for rules involving more colours, more dimensions and / or next-neigbour rules, Class 4 localized structures often emerge. The crux for the existence of class 4 behaviour is the control of the transmission of information through the system.
Universality in Turing Machines and other Systems
The simplest Universal Turing Machine currently known has two states and five possible colours. It might not be the simplest Universal Turing Machine in existence and so the simplest lies between this and two states and two colours, none of which are Universal Turing Machines; there is some evidence that a Turing Machine with two states and three colours is universal, but no proof exists as yet. There is a close connection between the appearance of complexity and universality.
Combinators can emulate rule 110 and are known to be universal from the 1930s. Other symbolic sytems show complex behaviour and may turn out to be universal too.
Chapter 12 The Principle of Computational Equivalence
The Principle of Computational Equivalence applies to any process of any kind, natural or artificial: ‘all processes, whether they are produced by human effort or occur spontaneously in nature, can be viewed as computations‘ [Wolfram 2002, p 715]. This means that any process that follows definite rules can be thought of as a computation. For example the process of evolution of a system like a cellular automaton can be viewed as a computation, even though all it does is generate the behaviour of the system. Processes in nature can be thought of as computations, although the rules they follow are defined by the basic laws of nature and all they do is generate their own behaviour.
Outline of the principle
The principle asserts that there is a fundamental equivalence between many kinds of processes in computational terms.
Computation is defined as that which a universal system as meant here can do. It is possible to imagine another system capable of computations beyond universal cellular automata or other such systems but they can never be constructed in our universe.
Almost all processes that are not obviously simple can be viewed as computations of equivalent sophistication. In other words: there is just one level of computational sophistication and it is achieved by almost all processes that do not seem obviously simple. Universality allows the construction of universal systems that can perform any computation and thus they must be capable of exhibiting the highest level of computational sophistication. From a computational view this means that systems with quite different underlying structures will show equivalence in that rules can be found for them that achieve universality and that can thus exhibit the same level of computational sophistication.
The rules need not be more complicated themselves to achieve universality hence a higher level of computational sophistication. On the contrary: many simple though not overly simple rules are capable of achieving universality hence computational sophistication. This property should furthermore be very common and occur in a wide variety of systems, both abstract and natural. ‘And what this suggests is that a fundamental unity exists across a vast range of processes in nature and elsewhere: despite all their detailed differences every process can be viewed as corresponding to a computation that is ultimately equivalent in its sophistication‘ [Wolfram 2002, p 719].
We could identify all of the existing processes, engineered or natural, and observe their behaviour. It will surely become clear that in many instances it will be simple repetitive or nested behaviour. Whenever a system shows vastly more complex behaviour, the Principle of Computational Equivalence then asserts that the rules underlying it are universal. Conversely: given some rule it is usually very complicated to find out if it is universal or not.
If a system is universal then it is possible, by choosing the appropriate initial conditions, to perform computations of any sophistication. No guarantee exists, however, that some large portion of all initial conditions result in behaviour of the system that is more interesting and not merely obviously simple. But even rules that are by themselves not complicated, given simple initial conditions, may produce complex behaviour and may well produce processes of computational sophistication.
Introduction of a new law to the effect that no system can carry out explicit computations that are more sopisticated than that can be carried out by systems such as cellular automata or Turing Machines. Almost all processes except those that are obviously simple achieve the limit of Computational Equivalence implying that almost all possible systems with behaviour that is not obviously simple an overwhelming fraction are universal. Every process in this way can be thought of as a ‘lump of computation’.
The Validity of the Principle
The principle is counter-intuitive from the perspective of traditional science and there is no proof for it. Cellular automata are fundamentally discrete. It appears that systems in nature are more sophisticated than these computer systems because they should from a traditional perspective be continuous. But the presumed continuousness of these systems itself is an idealization required by traditional methods. As an example: fluids are traditionally described by continuous models. However, they consist of discrete particles and their computational behaviour must be of a system of discrete particles.
‘It is my strong suspicion that at a fundamental level absolutely every aspect of our universe will in the end turn out to be discrete. And if this is so, then it immediately implies that there cannot ever ultimately be any form of continuity in our universe that violates the Principle of Computational Equivalence’ [Wolfram 2002, p 730]. In a continuous system, the computation is not local and every digit has in principle infinite length. And in the same vein: ‘.. it is my strong belief that the basic mechanisms of human thinking will in the end turn out to correspond to rather simple computational processes’ [Wolfram 2002, p 733].
Once a system reaches a relatively low threshold of complexity then any real system must exhibit the same level of computational sophistication. This means that observers will tend to be computationally equivalent to the observed systems. As a consequence they will consider the behaviour of such systems complex.
Scientific triumphs have in common that almost all of them are based on finding ways to reduce the amount of computational work in order to predict how it will behave. Most of the time, the idea is to derive a mathematical formula that allows to detemine what the outcome of the evolution of the system will without having to trace its every step explicitly. There is great shortage of formulas describing all sorts of known and common systems’ behaviour.
Traditional science takes as a starting point that much of the evolutionary steps perfomed by a system are an unnecessarily large effort. It is attempted to shortcut this process and find an outcome with less effort. However, describing the behaviour of systems exhibiting complex behaviour is a difficult task. In general not only the rules for the system are required to do that, but its initial conditions as well. The difficulty is that, knowing the rules and the initial condtions, it might still take an irreducible amount if time to predict its behaviour. When computational irreducibility exists there is no other way to find out how it will behave but to go though its every evolutionary step up to the required state. The predicting system can only outrun the actual system of which we are trying to predict its future with less effort if its computations are more sophisticated. This idea violates the Principle of Computational Equivalence: every system that shows no obviously simple behaviour is computationally exactly equivalent. So predicting models cannot be more sophisticated than the systems they intend to describe. And so for many systems no systematic predictions can be done, their process of evolution cannot be shortcut and they are computationally irreducible. If the behaviour of a system is simple, for example repetitive or nested, then the system is computationally reducible. This reduces the potential of traditional science to advance in studying systems of which the behaviour is not quite simple.
To make use of mathematical formulas for instance only makes sense if the computation is reducible hence the system’s behaviour is relatively simple. Science must constrain itself to the study of relatively easy systems because only these are computationally reducible. This is not the case for the new kind of science, because it uses limited formulas but pictures of the evolution of systems instead. The observed systems may very well be computationally irreducible. They are not a preamble to the actual ‘real’ predictions based on formulas, but they are the real thing themselves. A universal system can emulate any other system, including the predictive model. Using shortcuts means trying to outrun the observed system with another that takes less effort. Because the latter can be emulated by the former (as it is universal), this means that the predictive model must be able to outrun itself. This is relevant because universality is abound in systems.
As a consequence of computational irreducibility there can be no easy theory for everything, there will be no formula that predicts any and every observable process or behaviour that seems complex to us. To deduce the consequences of these simple rules that generate complex behaviour will require irreducible amounts of computational effort. Any system can be observed but there can not be a guarantee that a model of that system exists that accurately describes or predicts how the observed system will behave.
The Phenomenon of Free Will
Though a system may be governed by definite underlying laws, its behaviour may not be describable by reasonable laws. This involves computational irreducibility, because the only way to find out how the system will behave is to actually evolve the system. There is no other way to work out this behaviour more directly.
Analog to this is the human brain: although definite laws underpin its workings, because of irreducible computation no way exists to derive an outcome via reasonable laws. It then seems that, knowing that definite rules underpin it, the system seems to behave in some way that it does not seem to follow any reasonable law at all doing this or that. And yet the underpinning rules are definite without any freedom yet allowing the system’s behaviour some form of apparent freedom. ‘For if a system is computationally irreducible this means that there is in effect a tangible separation between the underlying rules for the system and its overall behaviour associated with the irreducible amount of computational work needed to go from one to the other. And it is this separation, I believe, that the basic origin of the apparent freedom we see in all sorts of systems lies – whether those systems are abstract cellular automata or actual living brains‘ [Wolfram 2002, p 751].
The main issue is that it is not possible to make predictions about the behaviour of a system, for if we could then the behaviour would be determined in a definite way and cannot be free. But now we know that definite simple rules can lead to unpredictability: the ensuing behaviour is so complex that it seems free of obvious rules. This occurs as a result of the evolution of the system itself and no external input is required to derive that behaviour.
‘But this is not to say that everything that goes on in our brains has an intrinsic origin. Indeed, as a practical matter what usually seems to happen is that we receive external input that leads to some train of thought which continues for a while, but then dies out until we get more input. And often this the actual form of this train of thought is influenced by the memory we have developed from inputs in the past – making it not necessarily repeatable evn with exactly the same input‘ [Wolfram 2002, p752 – 53].
Undecidability and Untractability
Undecidability as per Godels Entscheidungsproblem is not a rare case, it can be achieved with very simple rules and it is very common. For every system that seems to exhibit complex behaviour, its evolution is likely to be undecidable. Finite questions about a system can ultimately answered by finite computation, but the computations may have an amount of difficulty that makes intractable. To assess the difficulty of a computation, one assesses the amount of time it takes, how big the program is that runs it and how much memory it takes. However, it is often not knowable if the progam that is used for the computation is the most efficient for the job. Working with very small programs it becomes possible to assess their efficiency.
Implications for Mathematics and its Foundations
Applications in mathematics. In nature and in mathematics simple laws govern complex behaviour. Mathematics has distantiated itself increasingly from correspondence with nature. Universality in an axiom system means that any question about the behaviour of any other universal system can be encoded as a statement in the axiom system and that if the answer can be established in the other system then it can also be given by giving a proof in the axiom system. Every axiom system currently in use in mathematics is universal: it can in a sense emulate every other system.
Intelligence in the Universe
Human beings have no specific or particular position in nature: their computational skills do not vary vastly from the skills of other natural processes.
‘But the question then remains why when human intelligence is involved it tends to create artifacts that look much simpler than objects that just appear in nature. And I believe the basic answer to this has to do with the fact that when we as humans set up artifacts we usually need to be able to foresee what they will do – for otherwise we have no way to tell whether they will achieve the purposes we want. Yet nature presumably operates under no such constraint. And is fact I have argued that among systems that appear in nature a great many exhibit computational irreducibility – so that in a sense it becomes irreducibly difficult to foresee what they will do‘ [Wolfram 2002, p 828].
A firm as such is not a complicated thing: it takes one question to know what it is (answer: a firm) and another to find out what it does (answer: ‘we manufacture coffee cups’). More complicated is the answer to the question: ‘how do you make coffeecups’, for this requires some considerable explanation. And yet more complicated is the answer to: ‘what makes your firm stand out from other coffeecup manufacturing firms?’. The answer to that will have to involve statements about ‘how we do things around here’, the intricate details of which might have taken you years to learn and practice and now to explain.
A system might be suspected to be built for a purpose if it is the minimal configuration for that purpose.
‘It would be most satisfying if science were to prove that we as humans are in some fundamental way special, and above everything else in the universe. But if one looks at the history of science many of its greatest advances have come precisely from identifying ways in which we are not special – for this is what allows science to make ever more general statements about the universe and the things in it‘ [Wolfram 2002, p 844].
‘So this means that there is in the end no difference between the level of computational sophistication that is achieved by humans and by all sorts of other systems in nature and elsewhere’ [Wolfram 2002, p 844].