Xref: utzoo rec.puzzles:8354 sci.math:15782 comp.theory.cell-automata:324 Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!usc!apple!olivea!uunet!mcsun!ukc!acorn!dseal From: dseal@armltd.uucp (David Seal) Newsgroups: rec.puzzles,sci.math,comp.theory.cell-automata Subject: Re: How Intelligent are the Winning Ways? Message-ID: <5822@acorn.co.uk> Date: 14 Mar 91 05:44:19 GMT References: Sender: uucp@acorn.co.uk Distribution: rec Organization: Acorn Computers Ltd, Cambridge, England Lines: 108 In article callahan@cs.jhu.edu (Paul Callahan) writes: >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. I've only recently found and started reading this group, because of the crossposting of this thread to sci.math! >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. ... >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. ... >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 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. Interesting idea. However, rather than using the 1-D cellular automaton directly to simulate the Turing machine, why not just use the same idea to generate a moving tape? In other words, produce something like the following: +-----------------+ |State machine for| | Turing machine | +-----------------+ | | | +-----------+ | Special | +----+ +----+ | read/write| +----+ +----+ ... ---|Cell|---|Cell|---| cell |---|Cell|---|Cell|--- ... +----+ +----+ +-----------+ +----+ +----+ with the rows of cells being generated by rakes disappearing into the distance, as in your suggestion. I haven't worked out a detailed state diagram for the cells being generated, but it should be fairly simple. Essentially, the two halves of the tape are mirror images of each other. Each cell can contain no bits, one bit, or two bits. No bit cells would grab the bit from the next cell out along the tape, converting it to a no bit cell, while one bit cells would be passive and two bit cells would force their outermost bit into the next cell out along the tape, converting it into a two bit cell. To ensure that everything worked smoothly, I suspect the tape state machine would have to cycle at something like twice the speed of the Turing state machine. Overall, I'm fairly certain such a tape would require a lot less logic per cell than a 1-D cellular automaton that is capable of simulating a Turing machine. This would presumably make designing and setting up a suitable pattern of rakes considerably 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. Yes, indeed. I enjoy simple pleasures! :-) In fact, I even enjoy the thought experiments involved in working out how one might go about doing such a design, regardless of whether the details are ever filled in. David Seal Preferred email address is "dseal@armltd.uucp". Please use "dseal@acorn.co.uk" instead if this doesn't succeed - "armltd.uucp" is not known everywhere yet.