Does a noisy version of Conway's game of life support universal computation?

Question

Quoting Wikipedia, "[Conway's Game of Life] has the power of a universal Turing machine: that is, anything that can be computed algorithmically can be computed within Conway's Game of Life."

Do such results extend to noisy versions of Conway's Game of Life? The simplest version is that after every round every live cell dies with a small probability $t$ and every dead cell becomes alive with a small probability $s$ (independently).

Another possibility is to consider the following probabilistic variant of the rule of the game itself.

• Any live cell with fewer than two live neighbours dies with probability $1-t$.
• Any live cell with two or three live neighbours lives with probability $1-t$ on to the next generation.
• Any live cell with more than three live neighbours dies with probability $1-t$.
• Any dead cell with exactly three live neighbours becomes a live cell with probability $1-t$.

Question: Do these noisy versions of the Game of Life still support universal computations? If not, what can be said about their "computational power"?

Related information on the computational power of cellular automata and noisy versions of cellular automata will be also much appreciated.

(This question developed from this question on MathOverflow. Vincent Beffara's answer on MO gave interesting references for related results on computational aspects of noisy cellular automata.)

Answer 1

Here are some "nearby best" references, for what it's worth. It would seem the way to go on this question is to reduce it to a question on "noisy Turing machines", which have been studied (somewhat recently), and which are apparently the nearest relevant area of the literature. The basic/general/reasonable answer seems to be that if the TM can resist/correct for noise (as is demonstrated in these references), it's quite likely the CA can also, within some boundaries/thresholds.

The question of how to reduce a "noisy CA" to a "noisy TM" (and vice versa) is more open. It may not be hard but there does not appear to be published research in the area. Another issue is that the noisy TM is a new model and therefore there may be multiple (natural?) ways to represent a noisy TM. For example, the following papers look at disruptions in the state transition function, but another natural model is disruptions in the tape symbols (the latter being more connected to noisy CAs?). There may be some relation between the two.

• Fault-tolerant Turing Machine by Ilir Capuni, 2012 (PhD thesis)

  The Turing machine is the most studied universal model of computation. This thesis studies the question if there is a Turing machine that can compute reliably even when violations of its transition function occur independently of each other with some small probability.

  In this thesis, we prove the existence of a Turing machine that with a polynomial overheadcan simulate any other Turing machine, even when it is subject to faults of the above type, thereby answering the question that was open for 25 years.

• A Turing Machine Resisting Isolated Bursts Of Faults by Ilir Capuni and Peter Gacs, 2012
• Noisy Turing Machines by Eugene Asarin and Pieter Collins, 2005

(Another question: could there be some connection between noisy TMs and probabilistic Turing Machines?)

Answer 2

Gil is asking if the GL is forgetting everything about its initial configuration in time independent of the size, when each cell "disobeys" the transition function independently of other cells with some small probability.

To the best of my knowledge, this is not known for the GL. It is a very interesting question though. If it can withstand the noise, then it should preserve its universality.

A quick overview of the state of the art is as follows.

1. Toom's rule can save one bit forever faults that occur independently of each other with some small probability.
2. It was widely believed (the positive rates conjecture) that all 1 dim CA are ergodic until P. Gacs constructed his multi-scale CA that can simulate any other CA with moderate overhead even when subjected to the aforementioned noise.
3. The question if G(acs)K(urdiumov)L(evin) rule can save one bit forever in the presence of the above noise is still open. Kihong Park -- a student of Gacs --- showed that it wont, when the noise is biased.
4. When the work in 2 was published, M. Blum asked if a TM can carry on its computation if at each step, the transition is not done according to the transition function with some small probability independently of other steps, assuming that the information stored on the tape far from the head does not decay. A positive answer was given by I. Capuni (another student of Gacs) in 2012.

Answer 3

For starters, keep in mind that research in Conway's Game of Life is still ongoing and future developments may present a far less complicated solution.

Now then. Interestingly enough, this is a topic that is actually as much in line with biology and quantum physics as with traditional computer science. The question at the root of the matter is if any device can effectively resist random alterations to its state. The plain and simple answer is that it is impossible to make a such a machine that is perfectly resistant to such random changes. Of course, this is true in much the same way that quantum mechanics could cause seemingly impossible events. What prevents these events from occurring (leading most people to declare them strictly impossible) is the stupendously small probability such an event has of happening. A probability made so small by the large scale difference between the quantum level and the human level. It is similarly possible to make a state machine that is resistant to small degrees of random change by simply making it so large and redundant that any "change" noticed is effectively zero, but the assumption is that this is not the goal. Assuming that, this can be accomplished in the same way that animals and plants are resistant to radiation or physical damage.

The question then may not be how to prevent low-level disturbances from doing too much damage, but rather how to recover from as much damage as possible. This is where biology becomes relevant. Animals and plants actually have this very ability at the cellular level.(Please note: I am speaking of cells in the biological sense in this answer) Now, in Conway's game of life the notion of building a computing device at the scale of single cells is appealing (it does, after all, make such creations much smaller and more efficient), but while we can build self-reproducing computers (see Gemini), This ignores the fact that the constructor object itself may become damaged by disturbances.

Another, more resilient, way I can see to solve this is to build computers out of self-reproducing redundant parts (think biological cells) that perform their operations, reproduce, and are replaced.

At this point we can see another interesting real-world parallel. These low-level disturbances are akin to the effects of radiation. This is most appreciable when you consider the type of damage that can be done to your cellular automata. It is easy to trigger the cascade failure or "death" of a cell in Conway's Game of Life, much the same as what happens to many cells exposed to radiation. But there exists the worst-case possibility of mutation, creating a "cancerous" cell that continues to reproduce faulty copies of itself that do not aid in the computational process, or produce incorrect results.

As I've said, its impossible to build a system that is entirely foolproof, you can only make it less and less likely for a fault to compromise the entire system. Of course, the fundamental question here is really "are probabilistic simulations themselves Turing complete" which has already been decided to be true. I would have answered that fundamental question initially, save that it wasn't what you asked.

Answer 4

I am reminded of xkcd 505: A Bunch of Rocks.

Any real-world computer is subject to some level of noise. A simulation of a universal computer in the ideal infinite Conway's Life universe will have a mean time between failures dependent on the engineering details of its design. It will compute reliably for a probabilistically quantifiable period, unreliably for a period of accumulating errors, and then not at all.

I would expect a fuzzy logic or quantum superposition model to demonstrate clearly what reliability should be expected of a particular construction. One may want to simulate the expected outputs of various components, rather than iterating over all of their cells, to whatever degree they can be isolated from each other. One might be able to quantify expected interference from failing components. A genetic algorithm should be the best way to develop fault-{tolerating,resisting,correcting} components with MTBFs as large as desired for a given noise distribution.