Let me reword my question about the 2D "life" cellular automaton more carefully. QUESTION (IS EXPTIME "IMMORTALITY" MATHEMATICALLY POSSIBLE?): Does there exist a lifeform, which enjoys "homeostasis"? That is, suppose we use the usual life time-evolution rule, but with "epsilon random noise" added, i.e. each cell independently disobeys the rule with probability epsilon at any given timestep. Does there exist an epsilon>0 and P>0 and C with 0<C<1 such that for every sufficiently large number N, there exists a life pattern of initial diameter N that, with probability>1/2, will evolve for exponential(N^P) timesteps (staying nonempty) in the noisy world, in such a way that the Hamming distance between its no-noise and noisy evolution, is always upperbounded by C*diam^2 [where diam>0 is the time-varying diameter of the no-noise version]? -----------------------------CLAIMED SOLUTION (OR NEARLY) Peter Gacs, in a very long and difficult paper (really, a "book"...), claimed to have shown immortality *is* possible in certain universal 1D cellular automata and he also can achieve this in higher dimensions more easily than 1D (not for the "life" CA rule, though): http://www.cs.bu.edu/~gacs/papers/long-ca-ms.pdf "Reliable Cellular Automata with Self-Organization", J. Statistical Physics 103, 1/2 (2001) 45-267. "Reliable computation with cellular automata", Journal of Computer System Science 32,1 (1986) 15-78 http://www.cs.bu.edu/faculty/gacs/papers/GacsReliableCA86.pdf Note Gacs et al in many of their papers require the entire infinite space to be preset to whatever values he needs. That is, Gacs is showing that an immortal lifeform of infinite size can exist in a suitable CA. He is not showing that a compact finite-size lifeform with exptime survival, exists. (I think.) The difference is that the world external to the lifeform has to be preset to some fixed value, or periodic pattern ("homogeneity"). However in his huge paper, it appears he does solve the latter problem. This is a fantastic achievement but very few people understand it. Including me among those who do not understand it.