Abstract

Part 1
Mathematics, Logic & Computers

1.1  Mechanical computers
1.2  Abstract mathematics
1.3  Boolean logic
1.4  Reducing mathematical relationships to abstract Boolean logic
1.5  Physical implementation of Boolean logic
1.6  Universal computation

Part 2
Cellular Automata Computers

2.1  Basic structure and operation of a CA
2.2  Useful things to do with a CA

Part 3
Banks' Proof of Universality in 2-dimensional, 5-neighborhood CA

3.1  Rules of change
3.2  The wire and signal
3.3  The dead end
3.4  The fan out junction
3.5  The clock
3.6  The logic element
3.7  The NOT gate
3.8  The NOR gate

Part 4
Epilog

4.1  Manipulation of information by whatever means
4.2  The machine within the machine
4.3  The dependent automaton
4.4  Progress in understanding computers and cellular automata

Back to abstract

Go to BottomLayer home

 

 

 

Commentary on Edwin Roger Banks, "Information Processing and Transmission in Cellular Automata," Banks' Ph.D. thesis, 1971 (MIT, Dep't of Mechanical Engineering).  By Ross Rhodes.


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."

Acknowledgments

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


Endnotes

5.  Of course, it is not strictly necessary to do anything useful with Banks' machine, and he was not setting out to do anything useful, or even to design a machine that would do anything better than the klunky computer he had to work with (which must have seemed like a miracle of wizardry back in 1971). It was sufficient for Banks to prove that such a thing could be done, and that it would work.

5.1.  It is certainly possible to build an uncoordinated CA and, in fact, there may be some uses for such an "asynchronous" design.  However, for the general purpose computing presented here, the progress of Banks' signals along his wires depends on coordination and synchronization, and this is the case for most "interesting" CAs.

6.  Wolfram is not fully satisfied that any of the cellular automata proofs of universality is fully complete. Nevertheless, he strongly suspects that each of the cell spaces described by Von Neumann, Codd, Minsky, Banks and Cook are, in fact, capable of universal computation.

7.  Fredkin's recollections of the collaboration are set out in his draft manuscript Digital Mechanics (2000 paper), at 77 et seq., and in other papers at his site, www.digitalphilosophy.org


Previous

© Copyright 2004 by Ross Rhodes.

Hit Counter