From: Fred W. Helenius Subject: Re: The Game of Life - Part II (was: alt.atheism Scientist of the Month Nomination) Date: Mon, 19 Jun 2000 02:58:42 -0400 Newsgroups: alt.atheism,sci.skeptic,sci.philosophy.meta,alt.talk.creationism,sci.physics,sci.math Summary: [missing] [newsgroups trimmed to those with some relevance] daveg@u.washington.edu (David B. Greene) wrote: >Ken Cox wrote: >>It's also, as I'm sure you know, computationally equivalent >>to the one-dimensional one. David Greene would apparently >>have a problem with that, as obviously the machine with the >>two-dimensional tape can "reach patterns" that the one with >>the one-dimensional tape cannot. >Irrelevant and bogus. The 1-D UTM can reach all 1-D computable >results. The 2-D UTM can reach all 2-D computable results. The >GoL which is 2-D cannot reach all results that the 2-D UTM can >reach. I don't understand your point; the dimension and reachable states of any implementation of a Turing machine are irrelevant as long as it can achieve a set of states which are in one-to-one correspondence with those of a universal Turing machine and make the correct transitions among them. In any case, the argument is moot since a UTM in the Game of Life has recently been constructed. You can see it and read all about it at http://rendell.server.org.uk/gol/tm.htm . -- Fred W. Helenius ============================================================================== From: Dean Hickerson Subject: Re: The Game of Life - Part II Date: 19 Jun 2000 14:15:14 GMT Newsgroups: alt.atheism,sci.skeptic,sci.philosophy.meta,alt.talk.creationism,sci.physics,sci.math In sci.math Fred W. Helenius wrote: > In any case, the argument is moot since a UTM in the Game of Life > has recently been constructed. You can see it and read all about > it at http://rendell.server.org.uk/gol/tm.htm . That's not quite true. The tape in Paul Rendell's construction has a fixed (but arbitrary) size. To really emulate a universal Turing machine, the tape would have to grow larger, so that the program that's being run would never hit the end of the tape. It's been known for about 30 years that a UTM *can* be constructed in Life, but all of the mechanisms that are known for providing an infinitely extensible memory would make the pattern so slow that nobody's ever bothered to build one. Dean Hickerson dean@math.ucdavis.edu ============================================================================== From: Dean Hickerson Subject: Re: The Game of Life - Part II Date: 19 Jun 2000 20:51:43 GMT Newsgroups: alt.atheism,sci.skeptic,sci.philosophy.meta,alt.talk.creationism,sci.physics,sci.math I wrote: >In sci.math Fred W. Helenius wrote: >> In any case, the argument is moot since a UTM in the Game of Life >> has recently been constructed. You can see it and read all about >> it at http://rendell.server.org.uk/gol/tm.htm . > >That's not quite true. The tape in Paul Rendell's construction has a fixed >(but arbitrary) size. To really emulate a universal Turing machine, the >tape would have to grow larger, so that the program that's being run would >never hit the end of the tape. > >It's been known for about 30 years that a UTM *can* be constructed in Life, >but all of the mechanisms that are known for providing an infinitely >extensible memory would make the pattern so slow that nobody's ever >bothered to build one. Edward Green replied: > This is completely irrelevant to the question at hand. Which "question at hand" are you referring to? Fred claimed that a UTM had been constructed in Life. I pointed out that that's not true. That seems relevant to me. > These are > not efforts to build a "practical" computer. It's a question of > feasibility. What would it mean to "build" a UTM in "the game of > life" anyway? A formal definition can be found, for example, in "Cellular Automata" by E. F. Codd, Academic Press, New York, 1968. A less formal discussion of how to build one in Life appears in the last chapter of "Winning Ways for Your Mathematical Plays", by Berlekamp, Conway, and Guy, Academic Press, 1983. Roughly speaking, it would mean that every Turing machine, including its program and initial tape, can be emulated by a finite Life pattern. The pattern would have two parts: One of them is independent of the particular program and initial tape being emulated; the other encodes, in a simple way, the program and initial tape. If the program halts, the pattern will eventually indicate that, e.g. by setting a particular cell. If the program doesn't halt, then that cell will never be set. A consequence of Life's ability to emulate an arbitrary TM is that there's no algorithm to decide if a given finite pattern will ever set a particular cell. Other questions can also be shown to be uncomputable, such as: Does a given pattern eventually die out completely? Does the population of a given pattern tend to infinity? > So far as I know all you can do is implement a given > instance of one, with a particular tape, on an ordinary computer, > running a program which simulates "the game of life". You seem to be talking about implementing Life on a real computer, rather than implementing a computer within Life. That's not what Fred was referring to. > Your comment conflates several layers of abstraction. Please clarify what you mean. Dean Hickerson dean@math.ucdavis.edu