Part 4
Epilog
In considering Banks' accomplishment, it may at first seem that all he has created is a picture of a working computer - an animated illustration of what goes on inside the wires-and-diodes-and-transistors machine on your desktop.
And, in a sense, he has done that. However, the principles he describes can be used to create a working computer.
4.1 Manipulation of information by whatever means
Each of the cells in Banks' space represent a bit of
information, just as each particle of magnetic iron on a tape, or each pit on a CD, represents information in our familiar wired desktop machines. Accordingly, each cycle of transformation in Banks' cellular automata represents a transformation of that information - which is to say it accomplishes information processing. Because the processing/transformation rules are well defined and controllable, an engineer working with Banks' principles can process the information in any way he or she wants, just like
with any other general purpose computer.
Assuming that we wish to maintain the distinction between "us" and "the machine" so that the machine can do something useful for us,
[note 5] we will need a machine that can "set" the values of every cell to form an initial configuration that contains all of the wires, dead ends, junctions and logic elements we want for our computation. We will also want another machine that can sample any cell and tell us whether its value is 0 or 1. (Your computer monitor is doing that for you, when it displays a black or a white square.) Accordingly, we will need some kind of overarching machine that can access any individual cell to either set it's value, or just to read and display or otherwise make use of its value. In computer terms, this is called a read/write head, and it would have to be some kind of interface between all of the autonomous cells of Banks' machine design and the one of us that wants to do something useful with it. In our world of general purpose computing, all computers have some method of accessing
memory locations to either set them (programming, or marking changes of state) or to read them (output, or carrying over one calculation into the next).
4.2 The machine within the machine
Each of the cells in Banks' space also
represents a little computer that acts on the information it
obtains from its neighbors. As discussed in part 1 of this
essay, it makes no difference whatsoever how we construct the
computer(s) that will do the work of a cell, and that will actually be
the cell. We can construct these computerettes out of sheep and
goats and shepherds; or out of wires and diodes and transistors and
batteries; or by any other method of constructing logic gates.
We could even build them out of little Banks CAs -- except that this
would lead us into a long recursive turtles-all-the-way-down exercise
with no obvious stopping place for
machines-within-machines-within-machines.
4.3 The dependent automaton
We began with the condition that each
cell operates independently from its neighbors. Except that its
actions are not completely independent. For the thing to
work, there must be coordination among the cells to the extent that
all transitions must take place at the same time. It simply
would not do for a cell's neighbors to be changing state randomly,
because that would throw off the whole structure. [note
5.1] Accordingly,
the entire construction and each of the little computerettes we call
cells must operate in lock step.
This overall unification of operation might be achieved by
obtaining a sufficient quantity of computerettes that were absolutely
and perfectly identical, such that their very nature makes them
operate in sync. Fat chance. Well, anyway, nothing we can
buy off-the-shelf can meet such exacting specifications.
Another way to achieve the necessary coordination is to employ a
master clock with access to each and every computerette/cell in the
array, so that the master clock can trigger each cell to do its
calculating on schedule. This necessarily introduces the
requirement of another layer above the cellular array -- a
super-computer upon which each cell is dependent, but which itself is
independent of the cells that it controls.
In fact, the most common way to achieve unified operation is to
take advantage of the computer-within-a-computer concept. Each
"cell" can be created as a simple subroutine of some master
computer, properly referenced according to the master program.
The master computer then can operate in linear fashion according to
its own master clock to make all necessary calculations for one cycle,
and then proceed with this result to make the calculations for the
next cycle.
There is an alternative method of coordination which prevents
random transitions without the use of any master clock -- by having each cell broadcast its progress.
By this method, the cell would flip a switch each time it completed
its calculations and changed, so that its neighbors would know not to start
again for their next transition calculations until they
detected that all switches in their neighborhood had been
flipped. Instead of calculating according to an external
schedule, each cell simply waits for its neighbors to "catch
up" before going ahead itself. This method comes closest to the ideal of automatic,
independent and distributed computing at all parts of the CA.
From what we have seen, universal computation by a CA appears to be
unnatural in the sense that it requires a great deal of
preparation. It is, therefore, a great wonder that nature itself exhibits so
many features that seem to derive from something very much like
cellular automata computation.
4.4 Progress in understanding computers and cellular automata
At the time Banks was working on this problem another member of the
club at MIT, William Gosper, was looking at Conway's Game of Life to
see if that cellular automata configuration could also be made to do
these things. Not long after Banks had his initial proof (and before
Banks' thesis was finally accepted), Gosper found that, indeed, Game
of Life was similarly universal. Now that you have the general idea, you can see an excellent realization of a Game of Life implementation of these ideas (real computer programming, not just animation) at the following web site with designs by Paul Rendell:
http://rendell.server.org.uk/gol/tm.htm
Banks had shown that the requirements of eight neighbors for each two-state cell
(which is the Game of Life design) was extravagant and unnecessary, because the same functionality could be achieved with only four neighbors. Although Banks constructed his cell space in two dimensions, he points out that it can be accomplished in only one dimension (a single row of cells extending beyond the horizon) (Banks71 at 43) or in three dimensions (Banks71 at 25) by carefully defining the neighborhood.
Further progress in the march toward simplicity was reportedly made by Matthew Cook, an employee of Stephen Wolfram, who
in the 1990s was asked to develop a one-dimensional universal machine where each cell interacted only with its two immediate neighbors according to Wolfram's favorite rules of transition.
(Wolfram, A New Kind of Science at 1115.) [note
6]
The real point of Banks' exercise was to probe the intuition of his thesis advisor Edward Fredkin who, in company with a number of computer scientists and physicists, strongly suspected that cellular automata can model all of the processes of physics.
[note 7] Proving that cellular automata can act as universal general purpose computers, and that they can do so using the simplest of designs, enables this school to appropriate all of the antecedent proofs of Turing and Boole and others which incorporate not only inanimate structures, but the very "laws of thought."
A very special thanks to Roger Banks for his gracious comments and
suggestions. Thanks also to Edward Fredkin for bringing this
work to my attention, and for continuing
inspiration and exhortation to further study and wonder. And
forever thanks to my editorial assistant and master inspirer, Dr.
Janet Rhodes.
Canton, Ohio
April 11, 2004
|
