DP FAQ

3.1 What is Fredkin's thesis?
3.2 What is minimality?
3.3 What is "minimal CA"?
3.4 What is minimality (Petrov's) hypothesis?
3.5 What are "-transformations"?
3.6 Why are Fredkin's rules considered to be good candidates for DP rules?
3.7 What is Triangle CA (TCA)?
3.8 How many CAs, which are good candidates for passing the minimality (Petrov's) hypothesis, are known so far?
3.9 What if Petrov's hypothesis is incorrect?
3.10 What if Fredkin's thesis is incorrect?
3.11 What is the role of physical experiment in DP? How does DP explain property X, known from contemporary physics?

We would like to recommend to our members to subscribe to Cellular Automata (CA) newsgroup: comp.theory.cell-automata. Check whether your ISP permits you to subscribe to this newsgroup directly.

To subscribe via e-mail, send a single line of text:

subscribe

to the Majordomo server <>. To post a message to the group, send it to <> or <>. System administrator of the CA newsgroup and mailing list is Bruce Boghosian <>.

The Cellular Automata FAQ can be found on the WWW: http://alife.santafe.edu/alife/topics/cas/ca-faq/ca-faq.html

There is also a "Physics of / and Computation" mailing list (see below), which is non-automatic. To subscribe to this list, write to Prof. Norman Margolus <>. Right now, the traffic of the POC/PAC list is very low (about 20 messages per year or so). It mainly includes announcements from the POC/PAC research groups at MIT and Boston University.

"Physics of / and Computation" is a relatively new scientific field, which is a mix between Theoretical Physics and Theoretical Computer Science.

The old name of this field was "Physics of Computation" (POC), which I belive is no longer in use and was recently replaced by "Physics and Computation" (PAC). So far four workshops on this area have been held (in 1981, 1984, 1992 and 1996).

See also: http://www.im.lcs.mit.edu/cgi-bin/poc.pl

Contributions by: Plamen Petrov <>
Last updated: Jan 15, 1998

Basically, there is no difference between notion of cellular automaton (CA), known from the cellular automata theory, and the same notion used in the context of DP. However, to avoid any possible collisions, in DP we never use the term 'CA' for finite cellular automata, i.e. we assume that 'CA' has infinite number of cells.

In DP we often picture CA as a homogeneous directed graph instead of tessellation. In this case, "neighborhood" of some cell c is represented as directed "links" from the neighbor cells to c.

Since, using this method, every tessellation can be represented as a homogeneous directed graph, it is always possible to do so. However, the opposite is not true, which leaves room for the definition of a new notion: "CA on a homogeneous digraph". See ref. [Pet96] for more information on this topic.

Also, for brevity, when talking about some CA configuration, in DP we assume that this configuration is finite, i.e. contains finite number of nonblank cells. If we need to deal with some infinite configuration, we mention that explicitly in the text.

See also: CA FAQ for the definition of "cellular automaton"

"Finite Nature" assumption

2.2 What do we call "reversible" and "invertible" CA in DP? How does this terminology differ from the terminology widely used in Cellular Automata theory?

Contributions by: Plamen Petrov <>
Last updated: Jan 16, 1998

After Toffoli and Margolus [TM90] terms "reversible" (RCA) and "invertible" (ICA) cellular automata seem to be used as synonyms. However, in DP we prefer to make a bold distinguishment between these two terms.

What we call "reversible" are these CAs which have not more than one predecessor for each configuration. Respectively, "invertible" are these CAs which have exactly one predecessor for each configuration.

For brevity, sometimes we use the term "reversible" to denote "properly reversible" CAs, i.e. automata, which contain configurations with no predecessors at all. The last configurations are known from CA theory as "Garden-of-Eden" (GOE) configurations.

See also: [Pet96]

Contributions by: Plamen Petrov <>
Last updated: Jan 16, 1998

Edward Fredkin is an author of the following assertion, which we call "Fredkin's thesis":

"The Universe is a cellular automaton".

Fredkin's thesis is the milestone of the whole DP theory; in DP we assume that assertion made by Fredkin is correct and we operate with it just like a computer scientists operate with so called "Church-Turing-Post thesis". The last one suggests that the class of all (intuitively) computable functions is equivalent to the class of all mathematical functions, computable on a Turing Machine (TM).

Contributions by: Plamen Petrov <>
Last updated: Jan 16, 1998

In its wide context, minimality as a notion should be considered to be equivalent of what is called "Occam's razor" (in physics and metaphysics) and (from some certain point of view) to what is known as "information content" or "Solomonoff-Kolmogorov-Chaitin complexity" (in theoretical Informatics, theoretical Computer Science).

In DP theory we hypothesize that what we call "minimal CA(s)" should be a good candidate for strict mathematical definition of minimality as a notion.

Contributions by: Plamen Petrov <>
Last updated: Jan 16, 1998

Let there be some CA and some initial configuration (IC) within it.

Let P be some regular packaging of the CA space. We shall denote packages of P as p_i, where p_i= < c_i1, c_i2, ..., c_in>, assuming that every package contains exactly n cells. Let us also denote as c[t] (or p[t]) the state of some cell c (package p) for a given time step t, starting from IC and applying the rule of the CA.

We say that some CA is "minimal", if there exists some finite IC of our CA such that for every fixed (in advance) ordered set of n states < s_j1, s_j2, ..., s_jn> there exist some time step t and consequently - package p_i, such that p_i[t] = < c_i1[t]=s_j1, c_i2[t]=s_j2, ..., c_in[t]=s_jn>.

Contributions by: Plamen Petrov <>
Last updated: Jan 16, 1998

The minimality (or Petrov) hypothesis states that if Fredkin thesis is a correct assumption, then there exists some relatively simple mathematical condition (predicate), which is 'true' for the CA which is supposed to be our Universe, and is 'false' for all other CAs.

Currently we suggest that this predicate has the following form:

"This CA is both computationally universal and minimal", or, even shorter:

"This CA is minimal".

Thus, we hypothesize that there exists only one minimal CA, which turns out to be a complete mathematical model of our Universe.

Contributions by: Plamen Petrov <>
Last updated: Jan 19, 1998

-transformations transform one CA into another by preserving some computational processes and discarding others. In their essence, -transformations are homomorphisms which "minimize" the global function of some CA; they behave like "filters", which "throw away" all "uninteresting" computational processes and preserve the "interesting" ones.

An example of -transformation is the following:

Let CA₁ be some cellular automaton and let P is some regular packaging of the space of CA₁. We shall denote packages of P as p_i, where p_i = < c_i1, c_i2, ..., c_in>, assuming that every package contains exactly n cells.

Then it is possible to form another cellular automaton (CA₂) by "joining" cells of CA₁ within every package p_i of P to form "supercells" c_i', such that every c_i' of CA₂ has exactly kⁿ states, where k is the number of the states per cell of CA₁. It is also possible to write the rule of CA₂ in such a way that every configuration of CA₁ will have a corresponding configuration in CA₂. Then CA₁ and CA₂ will be isomorphous to each other.

Let us assume now that we are interested in some specific computational process within CA₁, which starts from some certain initial configuration G(0) of CA₁ and, applying the global function, leads to a sequence of generations G(0), G(1), ..., G(t), ... . Let us also assume that our computational process never contains package p_i (for every i and every t), such that p_i[t] = < c_i1[t]=s_j1, c_i2[t]=s_j2, ..., c_in[t]=s_jn>, where s_jm, m=1, ..., n, are some cell states for CA₁.

Then it is possible to transform CA₁ into CA₂ as described above, but in such a way that CA₂ will have kⁿ-1 states per cell ("supercell").

Note now that CA₂ will contain an isomorphous computation process for every computational process of CA₁ that does not contain package p_i[t] = < c_i1[t]=s_j1, c_i2[t]=s_j2, ..., c_in[t]=s_jn> during the evolution of that process. And the opposite: CA₂ will not contain any computational process that will correspond to a computational process of CA₁, which contains such package(s). Thus, we have a -transformation from CA₁ to CA₂ with regard to the desirable initial configuration G(0) and the computational process G(0), G(1), ... , G(t), ... that follows from G(0).

Contributions by: Plamen Petrov <>
Last updated: Jan 16, 1998

According to Theorem 3 of [Pet96], all reversible CAs with Fredkin's rules contain only one non-trivial computational process, i.e. all computational processes in these CAs are isomorphous to each other.

Obviously, the global function of such CAs could not be "minimized" further: after all, there is no way to "throw away" any other computational processes, since these CAs contain a single one.

Contributions by: Joel Dobrzelewski <>
Plamen Petrov <>
Last updated: Jan 17, 1998

Triangle CA (TCA) is a three dimensional reversible CA, found by Joel Dobrzelewski in 1996. TCA is a binary CA (i.e. every cell has only two states).

When presented as a homogeneous digraph, TCA has only two neighbors and uses Fredkin rules in a very simple form:

c[t+1] := c₁[t]c₂[t]

where c₁ and c₂ are the neighbors of the cell c, and c[t] denotes state of the c for time step t.

TCA shows remarkable non-replicative behavior, although being completely homogeneous (instead of CP-homogeneous -- see [Pet96]).

However, the interesting thing about TCA is that this CA might be able eventually to pass the minimality condition. A specially written computer program showed that TCA reaches all possible states within a region of 12 cells (2¹²=4096 possible states) for 60 generations only, starting from a single nonblank cell as an initial configuration.

3.8 How many CAs, which are good candidates for passing the minimality (Petrov's) hypothesis, are known so far?

Contributions by: Joel Dobrzelewski <>
Last updated: Jan 17, 1998

ZigZag For some period of time TCA was the only CA which was supposed to be minimal. Quite recently a specially written computer program found yet another CA (called by us "ZigZag" CA), which might be able to pass the minimality condition as well.

ZigZag is similar to TCA in a sense it is binary and reversible 3D CA with two neighbors only, but is more complicated as a structure. While TCA can be divided into cubes ("packages"), that contain 12 cells only, the smallest "package" of ZigZag is a cube, which contains 24 cells.

However, so far no mathematical proof exists that any of these CAs is (or is not) minimal.

Contributions by: Plamen Petrov <>
Last updated: Jan 20, 1998

If Fredkin's thesis is correct, then Petrov's hypothesis might be incorrect only to some certain extent.

If Universe is a CA, then this CA must be minimal.

Or, let us put the above assertion in the following form:

"If Fredkin's thesis is correct, then there exists some minimal CA, which is isomorphous to the CA which is our Universe."

In other words, there is no doubt that 'The CA', which we seek for, is minimal; what is unclear is how many CAs contains the set of all minimal CAs.

If the set of all minimal CAs contains more than one element, we may still try to "tighten" the condition of 'minimality' by seeking more '-transformations'. Or, at least, we may compare the abstract mathematical models, "proposed" by some of these minimal CAs, to the mathematical models known from contemporary physics.

Contributions by: Plamen Petrov <>
Last updated: Jan 20, 1998

Even if Fredkin's thesis is incorrect, the 'flavor' of DP is still preserved. If time and/or space are not discrete, and/or physical laws of our Universe are not deterministic, we can try to add more randomness, continuity, whatever to extend the model and continue to search in this way.

We may still try to use the main idea of DP (transformations of one mathematical model into another) in order to "minimize" the set of our abstract models into a single one.

3.11 What is the role of the physical experiment in DP? How DP explains property X, known from contemporary physics?

Contributions by: Plamen Petrov <>
Last updated: Jan 18, 1998

DP is a non-experimental physics.

DP does not attempt to explain property X, known from contemporary physics, by "embedding" it into the model directly.

The main question of DP is:

"What is (are) the simplest theory (theories), which can account for all physical properties observed in our real Universe?"

The main idea of DP is that it might be possible to obtain so long awaited "Theory of Everything" without looking into any physics, i.e. from pure abstraction. Instead of seeking mathematical models of real physical phenomena, DP suggests that studying mathematical models itself might be enough.

To make this point clear, we would like to postulate the following:

"No theory, which uses in any way experimental data in order to obtain mathematical models of the physical world, should be considered to be DP or part of DP."

That is what makes DP essentially different from Lattice Gas Automata (LGA) studies, for example, although LGAs also use cellular automata as a model of physical phenomena.

See also: CA FAQ for a discussion on LGAs