1. Cellular automaton models
It always bothers me that, according to the laws as we understand them today, it takes a computing machine an infinite number of logical operations to figure out what goes on in no matter how tiny a region of space and no matter how tiny a region of time. How can all that be going on in that tiny space? Why should it take an infinite amount of logic to figure out what one tiny piece of space-time is going to do?
— Richard Feynman
A cellular automaton (CA) is a kind of digital computer. It is discrete and deterministic. It is made up of cells like the points in a lattice or like the squares of a checkerboard. It is called "automaton" because it follows a simple digital (discrete) rule. A well known CA is the Game of Life [2] invented by John Conway. The rule is as follows: given a rectangular 2D lattice (like a checker-board), with two states per cell (up or down, or -, 1 or 0; we will use 1 or 0), the rule states that at each tick of a clock, the value at each cell becomes a one if exactly 3 of its nearest 8 neighbors are ones, it will remain a one if 2 or 3 neighbors are ones, and it will become a zero in all other cases.
Our thesis is that some CA model may be, in effect, programmed to act like physics. We call such models digital mechanics (DM). In short, DM is a discrete and deterministic modelling system which we propose to use (instead of differential equations, for example) for modelling phenomena in physics. We are driven in this direction by many heuristics; primarily by the concept, borrowed (and extended) from automata theory, of the universal machine [3] Any ordinary commercial computer would be a universal machine, except for the fact that it does not have an infinite memory. In this paper, we shall extend the meaning of the term "universal machine" to include the universal cellular automaton (UCA) or other kinds of general purpose computers that have large but finite memories; this would include any commercial computer. A universal machine can exactly mimic the behavior of any other finite computer, provided its memory is just a very little bit larger than the target machine.
For example, let us imagine a Cray YMP, with a total of 256 MB (256 MegaBytes) of RAM (random access memory and other memory, such as registers, but no disks or other auxiliary storage) solving a large, complex problem. An Apple Macintosh with 1 MB of RAM and a 256 MB hard disk can solve the same problem by exactly mimicking the behavior of the Cray. The 1 MB of RAM would be used to contain the simulation program and the 256 MB of disk would represent the state of the memory of the Cray. Simulating a Cray with 16 GB (GigaBytes) of RAM would mean that the Mac's disk would also have to have 16 GB, but the 1 MB of RAM would still be enough (technically, a few hundred more bytes might be needed). Of course the Macintosh would be seen by us to be very much slower than the Cray, but as seen from within (the evolution of the information in the memory) the two processes would be absolutely identical.
A sufficiently large universal #1 cellular automaton (UCA) can, by definition, exhibit any (and every) kind of mechanistic, locally finite behavior. What this means is that if you can imagine a process that could take place in a particular CA of any degree of complexity, then the same process can also be done by any CA that happens to be universal even though the universal CA is governed by a drastically simpler rule than the complex CA. By "complexity" we mean some combination of: a large number of states per cell, a complex CA rule, neighborhood (spatial connectivity and dimensionality), boundary condition or initial condition. If any particular CA is a good model of microscopic processes in physics, then every UCA could be programmed to exhibit the isomorphic behavior (after a space-time mapping). While it is true that there is no need to match neighborhoods, a UCA with a lower dimensionality than the CA it is modelling will spend almost all of its resources compensating for that deficiency.
A reversible universal cellular automaton (RUCA), belongs to a subclass of UCA. RUCA have properties that are both counter intuitive and very suggestive of being useful as a more direct substrate for an informational process that might be an exact model of microscopic processes in physics. Because RUCA are microscopically reversible, information and other quantities of the process are conserved in a very natural way. This means that it is possible to map properties of a RUCA information process onto properties of physics, such as energy or angular momentum, and have those properties conserved as a consequence of the reversible rule. RUCA also exhibit unusual and counterintuitive behavior that is a consequence of perfect reversibility combined with extreme quantization. RUCA reversibility is very different than the intuitive notion of microscopic reversibility that relies on continuity to ensure that no effect gets lost no matter how infinitesimal it becomes.
DM is a model of the basic phenomena of nature that uses the cellular automaton paradigm. What we will do in this paper is to suggest how various physical phenomena might be recast in the DM genre by mapping certain properties of physics onto the collection of kinds of behaviors that we have either seen in RUCA or which our experience leads us to believe can be found in RUCA. In this paper, we will always be assuming that our world is a large but finite system; finite in the amount of information in a finite volume of space-time, and finite in the total volume of space-time. We call that assumption "finite nature". The main implication of finite nature is that a finite volume of space-time can be exactly represented by a finite number of bits. DM like systems may be useful for creating approximate models of continuous phenomena, but if finite nature is true, then DM can be an exact model.
#1 In this context, by universal we mean capable of supporting the operation of a finite universal computer, such as an Apple Macintosh. Obviously physics allows this, and every sufficiently large RUCA or UCA also allows this.
#2 By "determined" we mean that we have made experimental arrangements to guarantee that a given event will happen.
#3 The conservative logic gate is commonly known as the Fredkin gate. See ref. [14].
References
[1] T. Toffoli and N. Margolus, Cellular Automata Machines - A New Environment for modelling (MIT Press, Cambridge, MA, 1987).
[2] M. Gardner, The fantastic combinations of John Conway's new solitaire game of 'Life', Sci. Am. 223 (April 1970) 120-123.
[3] M. Minsky, Computation, Finite and Infinite Machines (Prentice Hall, Englewood Cliffs, NJ, 1967)
[14] E. Predkin and T. Toffoli, Conservative logic, Int. J. Theor. Phys. 21 (1982) 219-253.
