Xref: utzoo rec.puzzles:8266 sci.math:15634 comp.theory.cell-automata:316
Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!uunet!viusys!uxui!unislc!ttobler
From: ttobler@unislc.uucp (Trent Tobler)
Newsgroups: rec.puzzles,sci.math,comp.theory.cell-automata
Subject: Life Turing Machines (was Re: How Intelligent are the Winning Ways?)
Message-ID: <1991Mar8.203020.26148@unislc.uucp>
Date: 8 Mar 91 20:30:20 GMT
References: <1991Mar5.171804.1429@zorch.SF-Bay.ORG>
Distribution: rec
Organization: unisys
Lines: 86

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