NetNews Usenet Archive 1993 #1/NN_1993_1.iso/spool/comp/theory/cellaut/598

Internet Message Format | 1993-01-11 | 2.6 KB

Path: sparky!uunet!olivea!sgigate!sgi!wdl1!wdl39!mab
From: [e-mail] (Mark A Biggar)
Newsgroups: comp.theory.cell-automata
Subject: Re: 1D computation-universal CAs
Message-ID: <[e-mail]>
Date: 11 Jan 93 23:31:01 GMT
References: <hmasum.726528479@cunews>
Sender: [e-mail]
Organization: Loral Western Development Labs
Lines: 43

In article <hmasum.726528479@cunews> [e-mail] (Hassan Masum) writes:
>What classes of 1-dimensional CAs have been shown to be capable of
>supporting universal computers?  I've read about 2 or 3 specific
>examples, but I'm more interested in any general results.  Also it
>would be nice to know the 'simplest' 1D CA so far discovered with this
>property.
>Any answers, pointers, etc welcome!

There is an obvious transformation of a N state by M symbol turing machine
into a N+M state 1D CA with a neighbor of size 4.  Most of the 1D CA is used
to similate the turing machine tape with one cell simulating the turing
machines head and internal state.  All cells except the head cell and the
cell imediately to its left and right are quiesent.  Those two cell are
active and only depend on the states of themselves, the cel to the left and
the 2 cells to their right.  Given the 7 state by 5 symbol universal turing
machine in "Finite Machines" by Minsky, that shows the existence of a 12
state size 4 neighborhood 1D CA that is universal.

You can get a CA with a neighborhood of size 3 by using (N+1)*M states,
where again most of the CA simulates a tape, but one cell must encode both
a tape space and the machine state.

There are also methods of encoding a N state 1D CA into a binary 1D CA with
a much larger neighborhood by using more then one cell in the new CA to
simulate a cell in the original CA and expanding the neighborhood accordingly.
For example, supose you have a 4 state 3 neighborhood 1D CA with states
{A, B, C, D}.  If we use the codes {000,100,010,001} to encode those states,
we can lay out a CA like so:

     ...10ddd0110ddd0110ddd0110ddd0110ddd01...
                      aaaaaaa
                bbbbbbbbbbbbbbbbbbb

where the cells marked 'a' simulate a cell in the original CA, the 'd's are one
of the above codes and the 'b's delineate the neighborhood.  The sequence 0110,
which cannot appear in any of the state encodings, acts as a registration
mark to show where the simulated cells are.  Using this method, the described
universal 1D CA above, when transformed into a binary CA, would require a
neighborhood size of 58 cells.

--
Mark Biggar
[e-mail]