Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!caen!uwm.edu!linac!att!pacbell.com!pacbell!osc!jgk
From: jgk@osc.COM (Joe Keane)
Newsgroups: comp.theory.cell-automata
Subject: Re: How Intelligent are the Winning Ways?
Message-ID: <4671@osc.COM>
Date: 16 Mar 91 01:10:14 GMT
References: <1991Mar5.171804.1429@zorch.SF-Bay.ORG> <5717@acorn.co.uk> <1991Mar12.155051.16488@zorch.SF-Bay.ORG>
Reply-To: jgk@osc.COM (Joe Keane)
Organization: Versant Object Technology, Menlo Park, CA
Lines: 43

A Turing Machine is just a special case of a one-dimenstional cellular
automaton.  We can consider a Turing machine to have tape states and control
states, where there is always exactly one instance of the latter.  The control
states and tape states can be added together or multiplied, it's not really
important.

How do we do this in Life?  We want the tape patterns to be something that
doesn't move around, for example configurations of blocks are fine.  We can
also use blinkers or something that flips between states because we probably
have constraints on what time we'll look at it.

We want the control patterns to be something which interacts with the tape
patterns in some predictable way.  An operation of the Turing machine consists
of a control pattern interacting with a neighboring tape pattern.  A new
control pattern is created where the tape pattern was, and a new tape pattern
is left where the control pattern was.

It's not clear how to construct such control patterns in a direct way.  In
general, two arbitrary patterns will not interact in a nice way, instead
they'll make a mess.  But you could try a lot of possibilities for control and
tape patterns, and reject the ones that produce undesirable interactions.  It
seems that if you try enough, you may be able to come up with a small subset
with only desirable interactions.  As far as i know, no one has done this, but
i think it'd be a good area for Life hackers to explore.

You may know that certain combinations of tape and control states can't occur
in your Turing machine.  You can take advantage of this to simplify the
construction of your control states.  Then if there's a programming error and
one of these forbidden combinations occurs, the machine may self-destruct.

With Life we have an additional advantage that it's two-dimensional.  So maybe
we can put the control states above the tape states.  I don't know if this
gains you anything, but it's fun to think about a big complicated control
spaceship flying over a long row of tape patterns.  The spaceship can fire
gliders or scout ships at the tape pattern and analyze what returns to decide
what to do next.

Note we don't really have to worry about constructing an arbitrary Turing
machine.  We only need to find a way to make one universal Turing machine.
This UTM could even have its program on a separate tape, given that we have a
lot of space.
--
Joe Keane, amateur mathematician