Xref: utzoo rec.puzzles:8245 sci.math:15597 comp.theory.cell-automata:314 Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!ukc!reading!minster!cjhs From: cjhs@minster.york.ac.uk Newsgroups: rec.puzzles,sci.math,comp.theory.cell-automata Subject: Re: How Intelligent are the Winning Ways? Message-ID: <668315039.11879@minster.york.ac.uk> Date: 7 Mar 91 03:04:00 GMT References: <1991Mar5.171804.1429@zorch.SF-Bay.ORG> Distribution: rec Organization: Department of Computer Science, University of York, England Lines: 99 in article <1991Mar5.171804.1429@zorch.SF-Bay.ORG>, xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) says: > > In article <5539@acorn.co.uk> dseal@armltd.uucp (David Seal) writes: >> Incidentally, how would one go about building a Life Turing machine? I The method proposed in "Winning Ways" is to construct a machine which has the same computational power as a turing machine, using counters that can hold arbitrary integers. To build something corresponding directly to a turing machine with an infinite tape... >> can see one very long-winded technique, with a stationary tape and a >> moving state machine: the state machine could move by emitting fleets >> of gliders to (a) destroy itself; (b) reassemble an exact copy of >> itself one tape spacing to the left or right. However, this seems like >> an awful lot of work: a moving tape, stationary state machine Turing >> machine would seem a lot more efficient. Any ideas how the moving tape >> might be constructed? > > Won't work, or at least won't act like a Turing machine. > > You have to be able to reverse direction on the tape. Rebuilding the > head one space left rather than one space right is at least feasible, > but reversing the motion of a tape which is by definition infinite in > length is not. Actually, I think it IS possible. What we may be able to do is represent a finite tape which can be moved to the left and the right, and also extended as necessary. As long as we insist that the infinite tape is such that at any given time all symbols sufficiently far from the read write head are OFF (or zero), then this extendible finite tape is essentially the same thing. We now come to a fun application of a remarkable pattern recently posted to the net by Paul Callahan: This pattern is one which I would have said was impossible, until it was explicitly provided. I have tried it out using Xlife, and it works as advertised. The pattern provided is a extendible delay loop. It is a pattern which encodes some number of bits of information as an endlessly circling ring of gliders, and by sending gliders at the pattern in appropriate ways one can rewrite any bit, or (dig this!) INSERT an extra bit into the stream. We need two such delay loops to represent the tape, and a finite control for the turing machine itself. The initial input tape is encoded onto the initial delay loops, and must (of course) have only a finite number of ON (or one) symbols. The bits on the delay loop are grouped into pairs, so that four symbols can be represented. They are HEAD, TAIL, ON, OFF. Each delay loop always has exactly one HEAD symbol, one TAIL symbol, and some number of ON and OFF symbols between them. The symbol under the read write head of the tape is kept in the finite control. The symbols on the tape to the "left" of the read write head correspond (in order) to the symbols coming after the HEAD symbol on the left hand delay loop. The TAIL symbol represents an infinite sequence of OFF symbols. And analogously for the right hand side. To move the tape to the left, the finite control acts as follows. It waits until the HEAD symbol is about to come around on the left hand delay loop, then overwrites it with any symbol, and overwrites the following symbol with HEAD. At the same time, this following symbol must also be tested, and some signal sent back to the finite control representing ON or OFF. Tricky co-ordination required here, but far from impossible. At some point the delay stream must test for the HEAD symbol, and then send a timing signal back to the finite control. At the same time, the finite control must insert into the right hand delay loop (after the HEAD symbol) the bit which is to replace the symbol which was under the read write head. Voila! This turing machine has some unfortunate properties. In particular, each step of the machine will take more life cycles than the step before it. Even worse, the extendible delay loop grows very rapidly and without limit, even if you are not inserting bits into it. Thus any implementation would bog down before the turing machine had executed its first couple of cycles. Even so, I am strongly of the opinion that a turing machine could be implemented in life EXPLICITLY, and the pattern actually run with the xlife program using a reasonable amount of memory. You just won't have the patience to wait for it to do anything useful. I don't want to spend the time to figure out the pattern. If anyone else does, go for it. Don't forget to acknowledge Paul and myself when you publish! I have the pattern for Paul's extendible delay loop, if anyone needs it. But I have lost his excellent comentary. So better you mail Paul first, if you are interested. Ciao -- Christopher Ho-Stuart University of York cjhs@uk.ac.york.minster or possibly cjhs@minster.york.ac.uk