More about "Non-replicative...''

In this paper we introduce a new kind of Cellular Automata, which we call "cellular automata on homogeneous directed graphs". It is important to emphasize, that these structures are something different from Random Boolean Networks or Neural Networks in general, since in our case the structures must be topologically homogeneous.

We show that using "CAs on homogeneous digraphs", it is possible to obtain highly unexpected configuration dynamics. Namely, it is possible to obtain asymmetrical configurations from a single non-blank cell in the initial configuration, using perfectly symmetrical rules and homogeneous space!

The big surprise, however, is that with "CAs on digraphs" it is possible to obtain asymmetrical configurations, even using some simple functions like XOR, i.e. using 2 (two!) neighbours only!

This is connected to the old question how this "slight" asymmetry, which we observe in our physical world, could arise from symmetrical laws and in a homogeneous Universe? For instance, the human face itself is a very good exaple of such asymmetry.

According to some hypothesis, the roots of all that go back to Quantum Mechanics and so called "CP-violation", which we observe in the weak interactions.

This work should be also regarded as a readable introduction to a more general theory, to be presented in our next work -- "Digital Physics", currently in preparation.

In "Digital Physics" we are trying to implement a new, fresh approach to Edward Fredkin's theories about "Universe as a CA". Instead of trying to model any physical laws, like microscopic reversibility, mass conservation, etc., we are looking for mathematical constraints, which will eventually "filter out" a small set of CAs -- candidates for a real universe!

Here we will present a tight condition, which we call "minimality for CAs". This condition is directly connected to the so called "Occam's razor" principle, widely used in physics and metaphysics. And we will conjecture that it is likely that this condition will be so good in "filtering out" the proper set of cellular automata, that at the end of the process we will have only one CA!

Yet another interesting point is that under this condition, reversibility of CAs is no longer explained as only a "desirable" property, inspired by microscopic reversibility and the Second Law of Thermodynamics. Under this condition, it becomes obvious that if the Universe is undeed CA, then it must be a reversible CA.

So to speak, "Digital Physics" is going to be a strange physics without... any physics at all.

At the time when "Non-Replicative..." was in preparation, little was known about properties of the "CAs on digraphs". For example, in this work we made a conjecture that asymmetry could be born only in some very special graphs, which we call "CP-homogeneous graphs". These should be described as a graphs which contain topologically indistinguishable vertices, but topologically distinguishable edges at the same time (as opposed to "absolutely" homogeneous graphs, which have both vertices and edges indistinguishable...).

But Joel Dobrzelewski, a CA enthusiast which the author met on the Net, was able to make an amazing discovery.

Dobrzelewski, who was familiar whith the contents of the present work before its official publication, has been able to find a very complicated three dimensional, reversible CA with two neighbours only, which should be eventually able to pass the condition. Moreover: his 3D RCA is an example of absolutely homogeneous CA, but nevertheless what you obtain here are asymmetrical configurations!

The "Big bang" and the "arrow of the time" are two of the topics which are easily (and in our case -- elegantly) explained by our general theory.

The problem is that what we call "reversible CAs" are, in fact, "properly injective CAs on finite configurations only". This should be defined as CAs for which every finite configuration has not more than one (finite) predecessor, and it is important to add that there exist some configurations, which under these rules have no predecessor at all ("Garden-of-Eden" configurations).

To make things clear, what we call "invertibility", is equivalent to "bijectivity over the set of all finite configurations only" -- please, note that this terminology is different from most of the works in Cellular Automata Theory.

Thus, the "Big Bang" should be explained as a simple "Garden-of-Eden" configuration, from which the evolution began, and the "arrow of the time" is a simple consecuence from the fact that the CA is properly injective (reversible), but not bijective (invertible).

The Einstein-Podolsky-Rosen paradox has always been considered to be a major obstacle in the way of Fredkin's theory about "Universe as a CA".

Ironically, "Non-Replicative..." was first presented in a forum where almost everyone was talking about "EPR-paradox" and "Quantum computation" -- The Forth Workshop on Physics and Computation (PhysComp96), held in Boston, Massachusetts.

However, when the world becomes a cellular automaton, there is nothing true about Bell's theorem. It is simply irrelevant to cellular automata -- there are many reasons about that.

First of all, Bell's theorem is a simple corollary of Set Theory. But the assumtions of the Set Theory (the "speed of the light" limit and "undestructible" particles or objects as an embodiment of the information) are far from true for all cellular automata.

The first assumtion ("speed of the light" limitation) is not true because of the simple argument: please, note that in the "digital realm" all the history is already recorded! There is no "light cone" here, there is rather an "informational cone". If indeed the Universe is a CA, then not only EPR correlations exist, but probably much weirder correlations do exists in our physical world.

The second assumption ("object description" of the information) is irrelevant because of the "non-objective" dynamics of CAs. In general, it is hard to predict what kind of object will be built when two or more "gliders" ("particles") collide in the game of Life: they may dissolve, may form another glider or even an absolutely new object with unknown properties!

Thus, the existence of the strong correlations between spacially distinct particles may turn out to be the most crutial argument... in favour of "Digital Physics".

The reversible cellular automata which we currently analize have the fantastic property to have strongly correlated cell dynamics "almost everywhere". To demonstrate real EPR-effects here, however, seems to be a hard task; but not because of Bell's theorem, rather because of something which we can call "moving" computation.

The problem is that it might be impossible to demonstrate EPR on static cells (fixed "points" of in space). It is likely that we must "allow" these "points" to move within the CA space (one can think about some "moving" configuration, which will represent the "tube" in which Bennett and Smolin are making their experimets...).

We are currently working toward a demonstration of a real EPR-effects on a reversible CA.

Text by Plamen Petrov
Artwork by Joel Dobrzelewski