Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.)

share|improve this question
2  
@vzn 1) no, this is not the "real question," it's an altogether different question; Gil's question is about robustness of a simple computational model to noise, not about the power of randomness; 2) TMs with a random tape are no more powerful than deterministic TMs, see this answer: cstheory.stackexchange.com/a/1415/4896 –  Sasho Nikolov Jun 7 '13 at 6:26
2  
The real question here is if the stochastic/noisy versions of the "Game of Life" still support computation. (If these version support computations in P then their power may go all the way to BPP.) It is possible that the computational power of these stochastic versions of the game of life is much lower. –  Gil Kalai Jun 8 '13 at 18:25
3  
Perhaps I'm stating the obvious, but you can just duplicate a configuration enough times so as to guarantee with high probability that a version of the configuration doesn't even have one cell flipped. My personal belief is that we can do much, much better, but at least it's a simple lower bound. –  user834 Jun 12 '13 at 16:33
4  
I'm not sure the question is well-defined. Suppose $t=10^{−9}$. It seems to me that you might be able to find a computer that deals with all one-bit errors in the "Game of Life", giving you fault-tolerant computation unless you spontaneously get a large block of errors all at once. But I don't think anything can be robust against all errors. For example, suppose the errors spontaneously create a malevolent adversary determined to disrupt the computation. You might be able to show your computation succeeds with probability $>1−10^{−9}$ but fails with probability $>10^{−10000}$. Does this count? –  Peter Shor Jun 13 '13 at 13:20
2  
Peter, if your computation succeed with probability 2/3, I am happy. –  Gil Kalai Jun 15 '13 at 11:57
show 14 more comments

4 Answers 4

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?)

share|improve this answer
add comment

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.
share|improve this answer
    
"If it is not ergodic, then it will preserve its universality" ... do you have any evidence for this statement? Is this a theorem? Where is it proved? I believe that Gacs's work shows that this is true in at least one case, but I don't see how that proves it holds for Conway's game of Life. –  Peter Shor Aug 4 '13 at 12:15
    
Thanks for pointing out. It is not a theorem but an interesting open question. Not being ergodic seems too little to ask for such a strong statement. –  user8719 Aug 4 '13 at 13:45
add comment

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.

share|improve this answer
    
Wow! Thanks for the drive-by-downvote! At any rate, I've revised my post, adding some information and sources. Sorry I didn't have the time to do that when I first posted this. I could modify this answer even further to fit community standards, if it wasn't for the fact that no reason was given for the downvote. –  Hawkwing Jul 5 '13 at 20:23
5  
As a non-voter, I don't see how this answers Gil's question. You address the question of whether "any device can effectively resist random alterations to its state", which is not what Gil asked. –  András Salamon Jul 6 '13 at 11:39
    
Thanks (non-sarcastically this time) for the comment, András Salamon. I'd vote it useful myself, but I'm still a new user on this overflow site. Anyways, I'm sorry my answer seems off-topic. I did perhaps address the question more loosely than I'd intended, but I feel my answer does respond to the original question by answering a similar question and then drawing parallels between the two. Is this perhaps too roundabout a way of answering? –  Hawkwing Jul 8 '13 at 12:16
add comment

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.

share|improve this answer
    
(mysterious voting here) A quantitative answer would be very speculative. There can't be a more precise answer than "yes, conditionally" without extensive experimentation on some chosen implementation of a UTM. A normal computer in a high-radiation environment is still practically a UTM, if only briefly. –  user130144 Mar 4 at 1:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.