Saturday, 9 March 2013

70. Universal Cellular Automata

Any process that follows definite rules can be regarded as a computation. Thus, cellular automata (CA) can carry out computation, as can Turing machines, and many other systems in Nature (Wolfram 2002). In fact, as I discussed in Part 23, the universe is a quantum computer. In computations carried out by humans on computers, the computer programs define the rules of computation. In Nature, the rules of computation are nothing but the laws of quantum mechanics.

The notion of a universal computer emerged from the work of Alan Turing in the 1950s, and this launched the computer revolution. It was demonstrated that it is possible to build universal computing machines with a fixed underlying construction, but which can be made to perform different computations by being programmed in different ways. With suitable programming, any computer system or computer language can be ultimately made to perform the same set of tasks.

Can at least some of the CA be universal computers? ‘Yes’, according to Wolfram (2002). He gave details about the construction of CA that can be universal cellular automata (UCA). He described a cellular automaton with 19 colours and 140 rules which was able to emulate all the 256 Wolfram CA.

The rule for one of the UCA is extremely simple. In fact it is Rule 90. What is not simple in the universal-automaton version of Rule 90 is that, unlike the description I gave in Part 68, each cell is represented by a block of 20 cells. Each block encodes the colour of the cell it represents, as also the rule for updating the colour at the next time step. Thus there are 19 possible colours for each cell. The new colour of each cell depends on the previous colours of a total of five cells. Thus there are, in principle, 2,476,099 cases to consider. Further, even the nearest-neighbour restriction in the formulation of the rule underlying the automaton is removed, and next-nearest-neighbour interactions are also recognized, so that there are 32 cases in each rule, compared to 8 before. Wolfram demonstrated that such an automaton can ultimately emulate any CA with any set of rules, irrespective of how many neighbours are involved or how many colours are involved. Thus nothing fundamental can be gained by using rules more complicated than those used for defining this universal automaton. Given this automaton, more complicated rules can always be emulated just by setting up appropriate initial conditions.

Nevertheless, this universal automaton is quite complicated. The breakthrough achieved by Wolfram (2002), after years of investigations, was that even a simple rule, namely his Rule 110, with just two colours and only nearest-neighbour interactions, is also one of the UCA. That is, Rule 110, with various choices of initial conditions, can emulate any computation. The crucial idea making this possible is to build up components from combinations of localized structures that the Rule 110 produces. This has been demonstrated to work, allowing us to get a large number of different kinds of components without having to increase the complexity of the underlying rules.

The typical behaviour of Rule 110, with random initial conditions, has been found to be that of a large number of localized structures that move around and interact with one another in complicated ways. In fact, this is a feature of all class 4 CA (cf. Part 69). Wolfram avers that probably most of them are UCA. Even class 3 CA, which are characterized by chaotic or fractal behaviour, may turn out to include many which are UCA.

The UCA can emulate Turing machines, mobile automata, substitution systems, register machines, RAMs, logic circuits, etc.

In UCAs the rules are simple but the initial conditions can be very complicated. There is also the question of efficiency.

Here is a universal cellular automaton with 16 colours that generates prime numbers:

The principle of computational equivalence

The immense number of CA examined by Wolfram led to the formulation of his Principle of Computational Equivalence (PCE). According to this principle, almost all processes that are not ‘obviously simple’ (e.g. those not described by class 1 and class 2 CA) correspond to computations that are of equivalent degree of complexity. In other words, irrespective of the simple or complicated nature of the rules or the initial conditions of a process, any such process will always correspond to a computation of equivalent difficulty or sophistication.

The genesis of the PCE, which is indeed a ‘bold hypothesis’ and needs more confirmation, lies in the idea of computational universality described above: It is possible to construct universal systems that can perform essentially any computation, and which must therefore all be capable of exhibiting the highest level of computational sophistication. This is reminiscent of the well known Church-Turing thesis, according to which, any process or computation governed by specific rules that can be performed at all can be performed by a Turing machine or equivalent universal computer.

The fact that even a simple rule like Rule 110 is a universal cellular automaton implies that computational sophistication does not necessarily imply sophisticated or complex rules. It does not matter how simple or complicated either the rules or the initial conditions for a process are; so long as the process itself does not look obviously simple (e.g. purely repetitive or purely nested), it will almost always correspond to a computation of equivalent sophistication.

The PCE, though still under debate, has far-reaching consequences for science, and for much else. Wolfram has applied it to a truly wide-ranging set of situations. He has demonstrated that simple programs can be used to explain space and time, perception, and also for rationalizing a variety of fundamental facts in physics, biology, and many other sciences.

In fact, Wolfram speaks of a 'New Kind of Science' (NKS) formulated by him. I shall say more on that in a later post.

No comments:

Post a Comment