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