Xref: utzoo rec.puzzles:8273 sci.math:15645 comp.theory.cell-automata:317
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!elroy.jpl.nasa.gov!decwrl!parc!ebert
From: ebert@parc.xerox.com (Robert Ebert)
Newsgroups: rec.puzzles,sci.math,comp.theory.cell-automata
Subject: Re: Life Turing Machines (was Re: How Intelligent are the Winning Ways?)
Summary: But does it need to be infinite?
Message-ID: <1991Mar9.211629.29650@parc.xerox.com>
Date: 9 Mar 91 21:16:29 GMT
References: <1991Mar5.171804.1429@zorch.SF-Bay.ORG> <1991Mar8.203020.26148@unislc.uucp>
Sender: news@parc.xerox.com
Distribution: rec
Organization: Xerox SSU
Lines: 35

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