Xref: utzoo sci.math:15704 comp.theory.cell-automata:322 alt.flame:29469 rec.puzzles:8307 Path: utzoo!utgpu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!emory!att!pacbell.com!tandem!zorch!xanthian From: xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) Newsgroups: sci.math,comp.theory.cell-automata,alt.flame,rec.puzzles Subject: Re: How Intelligent are the Winning Ways? Message-ID: <1991Mar12.155051.16488@zorch.SF-Bay.ORG> Date: 12 Mar 91 15:50:51 GMT References: <1991Mar5.171804.1429@zorch.SF-Bay.ORG> <5717@acorn.co.uk> Followup-To: comp.theory.cell-automata Organization: SF-Bay Public-Access Unix Lines: 111 dseal@armltd.uucp (David Seal) writes: > xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) writes: > dseal@armltd.uucp (David Seal) writes: > >> Incidentally, how would one go about building a Life Turing machine? I >> 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. By which I should have clarified that I meant that in terms of the number of cycles needed to complete an operation, operations that have the same order statististics for a Turing machine have very different order statistics for the moving tape case in Life. Example: move right writing a symbol into each blank frame "forever", and doing that but pausing one "step" time at each frame are both order N time operations in the number N of frames traversed on a Turing machine. The first is still order N on a moving tape Life emulation of a Turing machine, but the second is (at least) order N*N, since the emulation has to wait for the cessession/resumption of motion to reach the (ever more distant) left end of the tape and report back between each pair of steps. >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. And as several folks have written me, the unwritten piece of the tape can be implicit, so only a finite tape need be considered in real use. This doesn't remove the objection that what you end up with doesn't have behavior subject to the same analysis as a "real" Turing machine. > Some vague thoughts I've had about a moving tape: > Suppose you have a pattern which can contain an arbitrarily long > string of data: > A B C D ... Y Z > And that you can control it from its head to either shift the data outwards, > adding a new entry: > A B C D ... Y Z > ->nAB C D ... Y Z > ->n ABC D ... Y Z > ->n A BCD ... Y Z > ->n A B CD... Y Z > ->... > ->n A B C ...XY Z > ->n A B C ... XYZ > ->n A B C ... X Y Z > Or to shift the data inwards, removing the head in the process: > A B C D ... Y Z > -> B C D ... Y Z > ->B C D ... Y Z > ->B C D ... Y Z > ->B C D E... Y Z > ->... > ->B C D E ...Y Z > ->B C D E ... Z > ->B C D E ... Z > Then you could construct a moving tape out of two of these: you shift the > tape right by shifting its left half inwards and its right half outwards, > moving the symbol taken from the head of the left half on to the right half: > z y ... d c b a | A B C D ... Y Z > -> z ... e d c b | a A B C ... X Y Z > You would of course need to take special action if the left hand side > is empty: this simply consists of pretending you read a "0" from the > left hand half-tape, extending the right hand half-tape with a "0", > and not attempting to shorten the left hand half-tape. Shifting the > tape leftwards would be similar. > An important part of this scheme is that the actual shift of the tape > would take place as a "wave" moving out along the tape at some > constant speed, as indicated in the diagrams above. Furthermore, > provided both the "compression wave" generated by shifting a tape half > outwards and the "expansion wave" generated by shifting a tape half > inwards move at the same speed, you don't have to wait for the tape > movement to complete - you merely have to wait for a suitable period > to ensure that two successive waves don't interfere with each other. > This should be a constant amount of time, independent of the length of > the half-tape. But the capability to move that wave down the tape is the capability to record and erase an arbitrary current state, remember and write the previous state, and move one step; i.e., pretty much the capabilities of the moving head of an (at least) alphabet*alphabet state Turing machine. If you can send that wave, whatever means you use to promulgate it is pretty much the functional equivalent of the thing you were trying to use it to replace, a moving head. Being that close to solving the problem of a moving head that rebuilds itself with saved stateone step left or right, it looks simpler to finish the job than to build an immobile head which can also build this moving "almost a head" in two versions. I don't see that solving the problem, more making it worse, but I'm willing to listen. Kent, the man from xanth.