[math-fun] Life universality -- the nature of the proof
The construction by Conway of a universal computer inside LIFE (it's in his book with Berlekamp & Guy on games) had a (1) a processor and (2) a memory, and the memory was extendible (via software command) arbitrarily much. But it also could fire gliders into (3) a third region at, I think, arbitrary delays (controllable in software) and at arbitrary (achievable) angles, this region again being extendible via software command to make it grow as large as desired. Thus it was both a universal computer with infinite memory (despite initial state being finitely bounded), and also a glider "experimental particle physicist." Of course, region (3) could not be "isolated" from regions (1) and (2) because no known isolation method has ever been invented. Conway's construction was extremely inefficient, but faster versions with only polynomial slowdown not ultra-exponential, were cooked up later by others, who also worked out full details (Conway did not). Incidentally this computer can self-reproduce like actual "life" if it wants. My "immortality" question seems basically equivalent to whether it is possible to make the Conway computer "error correcting" and "fault tolerant" enough to probably last exponentially long even in the presence of "noise." This question, as far as I know, is wide open.
On Tue, Dec 6, 2011 at 10:26 PM, Warren Smith <warren.wds@gmail.com> wrote:
Of course, region (3) could not be "isolated" from regions (1) and (2) because no known isolation method has ever been invented.
This is a question that this thread has gotten me to think about. Can you build an "indestructible wall" in life? More precisely, is there a finite configuration S, and a particular cell P in S that is in the "on" state, such that given any configuration of the infinite plane that is a extension of S to the whole plane, cell P will remain in the "on" state forever. This is a wall that protects a single cell; you can ask an analogous question about protecting a larger configuration, but I suspect the answer will be the same. But I have no idea what the answer is. Can the right collection of gliders aimed at it in the right order break through any wall? Or are there impenetrable configurations? Andy
participants (2)
-
Andy Latto -
Warren Smith