Xref: utzoo rec.puzzles:8292 sci.math:15681 comp.theory.cell-automata:320 Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!psuvax1!wuarchive!udel!haven!umd5!newton.cs.jhu.edu!callahan From: callahan@cs.jhu.edu (Paul Callahan) Newsgroups: rec.puzzles,sci.math,comp.theory.cell-automata Subject: Re: How Intelligent are the Winning Ways? Message-ID: Date: 11 Mar 91 17:27:21 GMT References: <1991Mar5.171804.1429@zorch.SF-Bay.ORG> <5717@acorn.co.uk> Reply-To: callahan@newton.cs.jhu.edu.UUCP (Paul Callahan) Organization: JHU Computer Science Deparment, Baltimore MD Lines: 103 In article <5717@acorn.co.uk> dseal@armltd.uucp (David Seal) writes: [Some stuff about Life Turing Machines with constant slowdown in simulation] It's interesting that this thread has gotten going now, since I posted related material over two months ago that did not generate much commentary. In a recent posting, Christopher Ho-Stuart referred to my construction of an extensible delay loop. Unfortunately, as he and David Seal have pointed out, any TM simulation that used it would have a non-constant slowdown proportional to the current size of the store. On the other hand, it *is* an explicit Life pattern (available in Xlife format), and for this reason, I find it a little more satisfying than most of the general schema that have been proposed. It would not be all that hard to add a finite control and turn it into a universal machine, but I have not had the time recently. However, if we are speaking of general approaches instead of explicit patterns, then there is a straightforward general method for constructing a constant time simulation of an arbitrary 1-D cell automaton (with finite states per cell and transition function based on left and right neighbors), and it doesn't take much imagination to see that this implies a constant time simulation of an arbitrary Turing Machine. We first note that it is possible to construct any finite logic circuit with glider guns, and that glider guns can be produced by a collision of gliders. There is a construction called a "rake" (or a "glider puffer") that produces a glider at regular intervals (like a gun) but which itself propagates either horizontally or vertically. There is a technique for constructing rakes with arbitrarily long periods, which I discussed in some detail in early January. It turns out that this last point was not well-known (i.e. not discovered by Gosper in the early 70s), but essentially the same approach had been discovered a little earlier by Dean Hickerson. To make a long story short, it is possible to construct a class of rakes whose period grows exponentially with the size (measured either by cell population or area of bounding box) of the construction. Again, I have an Xlife pattern that illustrates the technique, and if some kind reader wishes to dredge up the accompanying text of my two articles about this pattern, I can repost. The famous breeder pattern (see any Life reference) consists of a growing sequence of glider guns left in the wake of a flotilla of interacting rakes. As long as our rakes are of sufficiently long period, we can construct a sequence of finite logic cells in the same manner (modulo a few details about how to get the logic cells in the right initial state). The logic cells are themselves composed of glider guns, so the gliders-->glider-gun collision is all we really need. Our 1-D cell automaton consists of an infinite sequence of cells lying along a horizontal line. They are initially quiescent with the exception of a finite interval around the origin (call these the active cells). We allow cells to wake up neighbors and send symbols back and forth, with the internal state changing according to some transition function. In the Life construction, logic cells would interact by sending gliders to their neighbors. Gliders, of course, propagate diagonally, not horizontally, but we may get around this by leaving a trail of "shuttles" (also constructable by a glider collision), parallel to the cells, to reflect the gliders 90 degrees back to the horizontal axis (details left as an exercise). Alternatively, we can use horizontally propagating "spaceships" to carry information, as these can be produced in the logic cell using appropriate glider collisions. To construct a Life pattern corresponding to such an automaton with a given initial configuration, we construct the active cells explicitly (note there are finitely many) and we develop two rake flotillas to build the infinite sequences of quiescent cells to the left and right (note that we could get away with an automaton that is infinite in just one direction). The rake flotillas move at half the "speed of light," so the sequence of new cells is produced very rapidly. As long as the propagation of data between the cells is slower (and it will be), we are guaranteed that before any cell tries wake up its neighbor, it will, in fact, have a neighbor to wake up. The number of steps it takes to compute the transition function in the logic cell gives us the constant slowdown. Otherwise, the pattern is a direct simulation of an arbitrary 1-D cell automaton. The catch is that we need a rake for every glider to make the logic cell, and a cell may require hundreds of gliders even if its transition function is quite simple. Thus, our rake flotillas consist of very large (but finite) populations of cells. However, all of the pieces (logic cells, rakes) can be easily constructed explicitly, so it is not as bad as a simulation that relies on universal constructors. The essential difference is that rake flotillas are pre-programmed constructors that perform a very specific job. Hence, they are much easier to design than universal constructors. I believe that with a suitable encoding scheme in which rakes are treated as aggregrates identified by position and phase-shift (rather than cell populations), it would be possible to explicitly construct and verify such a pattern using readily available computational power (e.g. a desktop workstation). If we had some CAD tools along the lines of "silicon compilers" for Life logic, then the design process would be much easier. Of course, all of this is merely a question of filling in the details of proofs that are generally agreed upon. Besides the simple pleasure of building a machine and watching it click and whir, there may be little merit to such activity. -- Paul Callahan callahan@cs.jhu.edu