Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!udel!haven.umd.edu!umd5!newton.cs.jhu.edu!callahan From: callahan@cs.jhu.edu (Paul Callahan) Newsgroups: comp.theory.cell-automata Subject: Re: Winning Ways (again) Message-ID: Date: 8 May 91 22:38:50 GMT Lines: 36 In article <1991May8.203654.7838@doc.ic.ac.uk> ijp@doc.ic.ac.uk (I J Palmer) writes: > But, I say, >what about getting Life to find (at this point I'd like to point out the >nice allignment of Life (the word) in this paragraph) a `Garden of Eden' or >Orphan (pad pad..) Life pattern. This is, I think, a computable problem >which, by definition, Life (it had to stop somewhere) can not solve !!!! > >Or perhapse I'm thick, but if this is the case where does my logic (eek) >fall down ????? Not a bad try, but here's where it fails. Life can simulate itself at a level more amenable to this kind of meta-reasoning than the actual life grid. For example, one could probably construct big life patterns fitting in, say, 1000x1000 squares, such that when these patterns are packed into a grid in the normal way, the resulting interactions simulate a Life grid (i.e., each pattern acts as a cell in a cell-automaton with data stored according to a fixed encoding scheme using glider interactions for computation, and this cell-automaton happens to obey the same rules as Life). If you believe that Life can simulate itself in this manner (there are lots of other ways, of course), it is not hard to imagine introducing extra controls in the simulation (for example, allowing the setting and resetting of a arbitrary cells) which would make it possible to construct any Life pattern for testing purposes, *including* those that no parent can give rise to. In other words, Life can simulate a computer which simulates Life, but allows some extra tinkering not specified by the Life rules. This should allow it to reason about the existence of Garden of Eden patterns. Obviously, there's more to it than this, but my point is simply that the inability of a Life pattern to construct an "actual" Garden of Eden pattern does not imply an inability to construct a simulation of a Garden of Eden pattern, which is all that people can do, after all. -- Paul Callahan callahan@cs.jhu.edu