Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!thunder.mcrcim.mcgill.edu!snorkelwacker.mit.edu!usc!wuarchive!udel!haven!umd5!newton.cs.jhu.edu!callahan From: callahan@cs.jhu.edu (Paul Callahan) Newsgroups: comp.theory.cell-automata Subject: Questions and comments about Conway's Life (long) Message-ID: Date: 10 Jan 91 17:56:15 GMT Lines: 150 I've been reading about/experimenting with Conway's Life off and on for about six years or so, but I only recently obtained a copy of the latest version of life for X-windows. I was impressed with its speed and its unbounded universe (though I've thought of numerous improvements to the user interface that would allow more structured design and careful experimentation). In any case, I've finally gotten to the point where I've come up with some interesting reactions that I haven't read about or don't remember, in any case (I do not fool myself by calling them "new"). I've been dealing primarily with rake and spaceship interactions for ease of experimentation (a rake will invariably escape before being eaten by even its most hellish progeny, and a spaceship is easy to redraw on the spot). I do have a goal in mind for all of this, but I may never get around to completing it, and I'd like to know if its even worthwhile (i.e. has not been done before). I'm suspecting it has, because it's so natural, but I've never read anything about it. Ok. Here's the main question: We all know Life is universal, but has anyone given a manageable, understandable, _explicit_ construction that proves universality? The literature I've read (such as _The Recursive Universe_ and _Winning Ways_) talks about self-replicating machines, which is fascinating in its own right, but what I have in mind is a bit less ambitious. All I want is a universal Turing machine with one semi-infinite tape. Less exciting, perhaps, but at least something for which one could give an explicit construction that could be easily verified by hand. I have an overall scheme for this construction that appears plausible. Namely, we define each tape cell of the Turing maching as a finite automaton using standard glider gun interactions to compute the logic. This includes "blank" tape cells, which will contain an automaton in some initial configuration. Each automaton will be a duplicate of the TM head's automaton, and its finite memory will consist of the tape cell contents, a flag telling whether the head is currently at that cell, and if so, the state of the head. The tape head will "move" when a cell turns off its "head" flag, and emits a small group of spaceships towards either its left or right neighbor, carrying away the state of the head. I think this can be made to work, with such cells being no harder to verify than any simple digital circuit. The only apparent question is how to get an infinite sequence of them. The answer, which the reader may have anticipated, is to use a flotilla of sufficiently thinned-out rakes, headed towards infinity, which leave a sequence of tape cells in their wake (much as the breeder leaves a sequence of glider guns). So, the first sub-question (which I haven't read about, but may have missed), is whether an arbitrarily thin rake is possible. This turns out to be true. I don't know if there is another standard method, but the following approach works: Consider the collision of gliders from three rakes that produces a medium spaceship in the _same_ direction as the rake. This ship will follow along to the next collision point, which will not produce a spaceship, but rather some stable garbage, consisting of a block and a beehive. The block can be cleaned up with a spaceship, and the beehive can be exploited (using another rake construction) to produce the same spaceship collision each time the beehive appears. In general, the thinning process becomes: Every other collision point forms a beehive --> Every fourth collision point forms a beehive --> Every eighth collision point forms a beehive --> ... To finish the thin rake, we use a construction that sends off a glider every time it eats a beehive. The rakes that produce gliders every 24 turns are sufficiently thin to use as components of the constructions. (I have a rake in xlife format that thins down to sixteenths, which I could post/mail if anyone is interested.) The thinness grows exponentially with the size of the construction, but it is still rather big and clunky. This brings me to my next question, which I think I can partially answer. Suppose we want to create an arbitrary collision of two or more gliders every time we encounter a single glider. Does there exist, for each such collision, a flotilla of spaceships to produce it from a single glider (without destroying the spaceships). I know that a fairly robust set of collisions can be obtained, using glider/spaceship-spark interactions, based on some experimentation on my own. Two interesting interactions that both yield the same result (at different orientations) are the following (where "*" is live, "." is dead). .****** .***** *.....* *....* ......* .....* *....*. *...*. ..**... ..*... ....... ...... **..... ..***. .**.... ..*... *...... ...*.. Note that in the first, the glider is going in the same direction (horizontally) as the spaceship, while in the second, it is going in the opposite direction. The result of the collision is three blocks, two gliders, and the following shape (ship?): **. *.* .** The blocks are easily eliminated by spaceships, and the gliders are useful for initiating other similar reactions. (Note that if this reaction is attempted with gliders from a rake, they must be spread fairly thin to give enough space for the reaction. A 120-step rake, constructed from the 20-step and 24-step rakes, and turns out to be thin enough). A sequence of these interactions (with appropriate clean-up) can be made to yield almost any sufficiently thin pattern of the above shape (and its mirror image). These can be turned into gliders later on, using the following interaction: .*****. *....*. .....*. *...*.. ..*.... ....... ..**... ..*.*.. ...**.. ....... ....... ....... .****.. ******. ****.** ....**. This reaction is (relatively) quick, and requires no cleanup. The advantage to being able to turn a stable shape into a glider is that timing problems in glider collisions are easy to resolve. Also, the exact position of a glider in a collision can be determined as a function of its diagonal path toward the collision point, and the time at which it is released, so we need only place the stable seed on the correct diagonal line for the collision. It's true that these gliders will only go in two of the possible four directions (away from the ship), but pairs of gliders arranged for kick-back reactions can overcome this deficiency. At this point, the single problem remaining is how to make collisions that require densely packed gliders headed in the same direction. Fortunately, these are not needed for glider-gun construction. What I would like to see is a set of CAD tools for life. It would be nice to be able to specify a layout of logic gates, and have a program turn it into a pattern of glider guns, then turn this into a collision of gliders, and ultimately construct a flotilla of spaceships to turn a single glider into this collision. By feeding the flotilla with the output of a thin rake, it should be possible to construct an unbounded linear array of simple computing elements. The result would be a universal machine that could be quite small and easily verified. I would find this to be a more satisfying proof of universality than the more general schema of self-replication, which while certainly correct, requires many details left to the imagination. -- Paul Callahan callahan@cs.jhu.edu