Xref: utzoo rec.puzzles:8289 sci.math:15668 comp.theory.cell-automata:319
Path: utzoo!news-server.csri.toronto.edu!rutgers!uwm.edu!cs.utexas.edu!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: <5717@acorn.co.uk>
Date: 11 Mar 91 11:38:56 GMT
References: <1991Mar5.171804.1429@zorch.SF-Bay.ORG>
Sender: uucp@acorn.co.uk
Distribution: rec
Organization: Acorn Computers Ltd, Cambridge, England
Lines: 106

In article <1991Mar5.171804.1429@zorch.SF-Bay.ORG> xanthian@zorch.SF-Bay.ORG
(Kent Paul Dolan) writes:

>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.

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.

If you want a Turing machine implementation that runs at a reasonable
constant speed, something like this would seem to be the answer. The other
options I've seen by now are:

(a) The moving machine, stationary tape option referred to in my original
    message. Runs at a constant but VERY slow speed.

(b) The technique using extendible delay loops to simulated tape halves,
    described in a posting by Christopher Ho-Stuart. Runs at a non-constant
    speed, roughly inversely proportional to the size of the chunk of tape
    used so far.

(c) A technique described to me by email by Richard Schroeppel, which can be
    summarised as having a stationary tape and a stationary machine with a
    movable read/write head. He says it uses technology similar to that used
    for the sliding block memory to move the head and to read and write the
    contents of the tape. When reading the tape, two pulses are sent out:
    one is returned or not returned according to the contents of the tape,
    while the other is always returned and acts as a timing pulse. This
    again runs at a non-constant speed, this time roughly inversely
    proportional to the distance the tape head has moved from the state
    machine.

What I don't know is how to construct the half-tape required for my moving
tape. I suspect it's quite difficult!

David Seal
dseal@acorn.co.uk or dseal@armltd.uucp

Standard disclaimers apply.