From: Mark A Biggar (mab@wdl57.wdl.loral.com)
Date: Fri Jun 04 1993 - 18:39:37 UTC
In article <1993Jun4.094516.7798@msuvx1.memst.edu> bartlett@msuvx1.memst.edu writes:
> I would like to know if there exists a Universal 1D CA with 2 states.
> i.e. a one-dimensional cellular automaton over a binary alphabet
> capable of simulating a Turing machine. The variable here is
> the radius (or size) of the 1D neighborhood. If anyone knows
> of such a beast, please tell me.
I don't know of a article or book that describes one, but I can tell you how
to construct one.
Take the 4 symbol 7 state machine found in Minsky "Computation, Finite
and Infintie Machines", which I believe is the smallest Universal Turning
machine known. There is an obvious 1D 11 state CA that emulates this machine.
Most of this CA will be inactive having states corresponding to the 4 symbols
and will emulate the turing machine tape. One cell will emulate the Turing
machine head and will be in a state corresponding to one of the UT 7 states.
The cell immediately to the right of the special cell is the tape cell
considered to be under the UT's read/write head. The neighborhood for this
machine is size 4 (each cell, the cell to the left and 2 cells to the right.)
Now to convert to a 2 state 1D CA we will need to greatly expand the
neighborhood to allow for a binary encoding of the above CA. Assume the
the symbol and state sets of the above UT are {' ',A,B,C} for the symbols
and {0,1,2,3,4,6} for the states, Now let's use the following
encodings in binary {00000,10000,10001,10010} for the symbols and
{00001,00010,00100,00101,01000,01001,01010} for the states. Note that none
of the codes has two 1's in a row. This allows us to distinguish sets of
binary cells that emulate a single cel in the 11 state CA by using the
pattern 0110 as a registration mark. For example, if a segment of the 11
state CA has the pattern "A B2C A", this would be encoded in the 2
state CA as:
0110100000110000000110100010110001000110100100110000000110100000110
----- ----- ----- ----- ----- ----- -----
A ' ' B 2 C ' ' A
The new neighborhood is 42 cells wide (you have to be able to see 2 reg marks
to the left and 3 to the right.)
There, we're done except for translating the rules, which I leave as an
execise :-)
There are denser codings that can be used, but this one is easy to describe.
--
Mark Biggar
mab@wdl1.wdl.loral.com
This archive was generated by hypermail 2.1.7 : Tue Oct 14 2003 - 21:44:16 UTC