Abstract: According to the classical definition, a cellular automaton (CA) is an abstract mathematical model for computation that updates its cells "all at once" (in a full parallelism) during a single "instant" of time. This raises the engineering question how one should implement such a definition in practice, especially if we keep in mind that using any kind of synchronization device ("clock") will inevitably lead to slower updates as the size of the CA configuration increases due to the speed-of-light limitation.
In the present work we demonstrate a simple scheme that turns any such "abstract CA" into a physically realizable parallel computer ("concrete CA") that runs with constant speed regardless of the size of the automaton. Although this "concrete CA" works asynchronously rather than synchronously, it updates its cells in such a way that it preserves the global behavior of the "abstract CA". As a result, for any hypothetical "observer" that resides within such a CA it will be impossible to distinguish whether he/she lives in a "abstract/synchronous CA" or in a "concrete/asynchronous CA"; it is also interesting to note that this solution is purely mechanical and does not use quantum mechanical effects of any kind.
Last revised: Monday, August 19, 2002 6:14 PM
This work is still in preparation. Meanwhile, please check out the contents of the e-mail sent to Joel Dobrzelewski on May 20th, 2001 that gives one possible solution to the problem [Pet01].
(Actually, the solution is quite simple, so it is one way or another surprising that, to our knowledge, it has not been published so far&)
Quite recently, however, the same solution finally got published!
The solution proposed in the e-mail cited above has been independently found and published by Mathieu Capcarrere as a part of his Ph.D. thesis [Cap02].
(I have learned about this publication from the and already congratulated Capcarrere for his finding, acknowledging his work preceded the publication of the present article)
Actually, the whole problem has a long history full of curiosities; it is quite possible that someone else already succeeded to publish a similar thing, so please let me know if you have some information about any other predecessors.
For example, readers interested in the history of the problem should check out [Mar90] and [Wol02]. Both Margolus and Wolfram describe similar solutions for one-dimensional CAs, but to our great surprise fail to notice how their solutions could be generalized for CAs of any dimension.
For example, Margolus [Mar90] mixes the whole problem with quantum computation and concludes that:
"In fact, at least in one dimension, it does seem possible to construct plausible models to simulate any interacting deterministic system at a constant rate and in a local manner. The problem of finding satisfactory models of fully parallel quantum computation in more than one dimension remain open."
Similarly, Wolfram [Wol02] describes only the one-dimensional case and speculates:
"I argued in the last section that the progress of time should be viewed at a fundamental level much like the evolution of a system like a cellular automaton. But one of the features of a cellular automaton is that it is set up to update all of its cells together, as if at each tick of some global clock. Yet as it seems unreasonable to imagine that the universe consists of a rigid grid of cells in space, so also it seems unreasonable to imagine that there is a global clock which defines the updating of every element in the universe synchronized in time.
But what is the alternative? At first it may seem bizarre, but one possibility that I believe is ultimately not too far from correct is that the universe might not work like a cellular automaton in which all cells get updated at once, but instead like a mobile automaton or Turing machine, in which just a single cell gets updated at each step."
It is our opinion that this otherwise highly suggestive viewpoint is erroneous. However, to reveal what is wrong with this line of thoughts requires lengthy explanation; this topic will be studied later in [Pet02g].
* This article is a part of [Pet02].
[Cap02] Capcarrere, Mathieu, "Cellular Automata and other Cellular Systems: Design & Evolution", Ph.D. Thesis No.2541, Swiss Federal Institute of Technology, Lausanne, Switzerland (March 1st, 2002), 172 pp. See section 6.3.1: "A simple and efficient time-stamping method" (p.104).
Available online at: http://lslwww.epfl.ch/~msc/THESIS/thesis.html
[Mar90] Margolus, Norman, "Parallel Quantum Computation", in: "Complexity, Entropy and the Physics of Information", Wojciech Zurek, ed., Addison-Wesley (1990) . See: "Local Synchronization", pp. in the book or pp.9-12 in the online version.
Available online (PostScript): http://www.aeiveos.com/~bradbury/Authors/Computing/Margolus-N/PQC94.ps
Available online (PDF):
[Pet01] Petrov, Plamen, Private e-mail message sent to Joel Dobrzelewski (May 20th, 2001).
The full text of this e-mail is available here. (The same topic has been also discussed on the in December 2001).
[Pet02] Petrov, Plamen, "Series of Brief Articles about Digital Physics (DP)", in preparation. For the latest update, check out: https://digitalphysics.org/Publications/Petrov/DPSeries/
[Pet02g] Petrov, Plamen, "What is Emulation?", in preparation.
[Wol02] Wolfram, Stephen, "A New Kind of Science", Wolfram Media, Inc., Champaign IL (2002), 1192 pp.. Check out the Index for "Synchronization, in practical computing" (p.1035) and "Synchronization, in the Universe" (p.486).
Web site: http://www.wolframscience.com