ttobler@unislc.uucp (Trent Tobler) (03/09/91)
From article <1991Mar5.171804.1429@zorch.SF-Bay.ORG>, by xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan): > In article <5539@acorn.co.uk> 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. > > 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. > Another way is to have the state machine sent a fleet of gliders to the tape reader, containing the information as to whether to move right or left, and the symbol to write. The tape reader would then send back a fleet of gliders that represent the symbol found on the tape. write symbol +--------+ and move left +------+ |State | > > | Tape | | Machine| > |Reader| +--------+ +------+ o o <- tape symbols o +--------+ +------+ |State | | Tape | Tape reader destroys old | Machine| |Reader| symbol and writes a new one. +--------+ +------+ o v o v o +--------+ +------+ |State | | Tape | Tape reader moves then | Machine| |Reader| determines symbol on tape +--------+ +------+ v o v o o +--------+ +------+ |State | < < | Tape | And then sends the symbol | Machine| < |Reader| back to the state machine +--------+ +------+ o o o In this way, the tape can extend to infinity, any number of symbols can be encoded, and the state machine can be a large as possible without the complexity of moving it added. The tape reader can be designed to detect some special symbol called real-end-of-tape, and when it reads this, it creates a new real-end-of-tape to the right, and writes a virtual-end-of-tape at the current location. Or another solution if the number of symbols are known is to know the symbol with the longest response time, and if nothing is heard back within that time, it sends an end-of-tape signal. This has the drawback that it sends off stray gliders into space. As a side note, this machine literally crashes if you attempt to move the tape reader left of the end-of-tape ie. it collides with the state machine creating a mess. :) --- Trent Tobler - ttobler@csulx.weber.edu
ebert@parc.xerox.com (Robert Ebert) (03/10/91)
>>> 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... >>> Any ideas how the moving tape might be constructed? >> >> 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. > >Another way is to have the state machine sent a fleet of gliders to the >tape reader, containing the information as to whether to move right or >left, and the symbol to write. The tape reader would then send back a >fleet of gliders that represent the symbol found on the tape. I missed the beginning of this thread, but it appears that the challenge is to build a real Turing machine, and not just a very good simulation. One potential moving tape solution would be to use a "just in time" delivery system on the tape. That is, start with a short, finite tape and, when you need a space that doesn't exist, enlarge the tape in that direction. This way the tape will never actually need to be infinitely long, at least, not in any finite amount of time, and so the resources necessary to move the tape will also be finite at any given time. Of course, as we run out of matter and energy (about the time the universe ends in a sea of luke-warm entropy) things will break down, but then, if you need to build an infinite tape to start the "moving machine" version, you'll never complete it and your machine will never even start processing. Philosophically, isn't this what we're doing now? As we need more computing resources, we simply build them. So, the, we (the intelligent creatures of the universe) can be said to have infinite data storage capacity. Hmm... --Bob