Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!ukc!acorn!dseal
From: dseal@armltd.uucp (David Seal)
Newsgroups: comp.theory.cell-automata
Subject: Re: How Intelligent are the Winning Ways?
Message-ID: <5823@acorn.co.uk>
Date: 14 Mar 91 05:44:24 GMT
References: <1991Mar12.155051.16488@zorch.SF-Bay.ORG>
Sender: uucp@acorn.co.uk
Distribution: comp
Organization: Acorn Computers Ltd, Cambridge, England
Lines: 40

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

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

Yes, I agree that the capabilities of a tape cell as I described it are
roughly the same as those of a moving head, or quite possibly even more
complicated. I'm not recommending the moving tape machine as a particularly
easy way to construct a Life Turing machine.

But what I was wondering about was the possibility of producing a constant
rate Turing machine - i.e. one for which you can say "One step of the Turing
machine always takes exactly C Life generations, where C is a known
constant". The moving head implementation does not meet this criterion: it
can take an arbitrary amount of time for data being written to get to the
head and for data being read to return from the head. The moving tape
implementation *could* have this property, provided a suitable tape could be
designed, because of the possibility of being able to start the movement of
the tape, wait a constant amount of time to let the movement wave go far
enough that it is not going to interfere with whatever you're doing at the
moment or with further movement waves, then proceed.

Paul Callahan's postings now indicate that this can be done, by using rakes
either to construct a 1-D cellular automaton (his suggestion) or a moving
tape (my suggestion, in a separate posting).

David Seal

Preferred email address is "dseal@armltd.uucp". Please use "dseal@acorn.co.uk"
instead if this doesn't succeed - "armltd.uucp" is not known everywhere yet.