Universal Cellular Automata.

[Harold V. McIntosh]

Hassan Masum <hmasum(at)ALFRED.CCS.CARLETON.CA> asks:
>
> 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.
>
That depends somewhat on how you define a universal computation. If you
follow Turing's line of thought, that you have a specific algorithm or
process or concept that you call computation in mind, and then set out to
design a mechanism which will realize that computation, then you have one
point of view.
-
On the other hand if you have some natural (or artificial) phenomonon which
either looks or is provably complicated, you may conclude that you need an
artifact at least as complicated as Turing's Universal Computer to analyze
it. You might then say that your phenomonon was participating in a univerasl
computation, or performing one, or whatever.
-
Taking the first point of view, it is not hard to conjure up a one dimensional
cellular automaton which follows the lines of Turing's original design; this
was already done back around the fifties, as von Neumann's ideas about cellular
automata began to circulate.
-
There is also a famous result of Shannon, concerning the tradeoff between
states and symbols in a Turing machine, whence one concludes that their product
ought to be constant, whose minimal value has been a result of a certain amount
of speculation. Marvin Minsky discusses the issue in his book, 'Computation:
Finite and Infinite Machines.'
-
In recent times attention has again been paid to the issue. Karel Culick III
and collaborators have discussed some tradeoffs in cellular automata, wherein
the size of a neighborhood may be compensated by an increase in states. Other
authors have pondered such issues as the effect of an infinite number of read
heads on the automaton, or of guaranteeing an infinite supply of tape.
-
Specific results would not seem to go much beyond those reported by Minsky.
In general, even a radius 1/2 automaton can model a Turing Machine, but the
Universal Machine needs a certain minimum of states, whose exact value is not
known.
-
If a cellular automaton cannot be modelled on a Turing Machine that is only
because it operates in parallel and is infinite. So if you want to suggest
that cellular automata are more powerful than Turing Machines, you are talking
about models of infinity and may have an opportunity to do something original.
Otherwise Turing's thesis, or Church's thesis, or whatever, is that everything
that we are accustomed to call computing, can be modelled on a Turing Machine.
-
Stephen Wolfram, among others, has poetically referred to processes performing
'universal computations,' and we come to the second point of view mentioned
above. But, in a supplement to one of A.K. Dewdney's articles in Scientific
American, he states that to establish the universality of a cellular automaton
it would be necessary to relate its activity to a Turing Machine, or some other
model which has been shown equivalent.
-
One of these would be a Post Tag System, whose equivalence was established by
Minsky; there is also Minsky's Register Machine, which was used by Berlecamp,
Conway and Guy to prove Life universal. And of course, WireWorld would let you
build a General Purpose Computer, although maybe it wouldn't have infinite
memory.
-
Of course, you could always show that a given automaton was NOT universal
by solving its halting problem. That usually takes care of very, very small
automata.
-
Harold V. McIntosh |Depto. de Aplicaci'on de Microcomputadoras
MCIN...@UNAMVM1.BITNET |Instituto de Ciencias/UAP
mcin...@unamvm1.dgsca.unam.mx |Apdo. Postal 461
(+52+22)43-6330 |72000 Puebla, Pue., MEXICO

[Dan Gordon]

In article <930110031...@Early-Bird.Think.COM>,

MCIN...@unamvm1.dgsca.unam.mx ("Harold V. McIntosh") says:
>Hassan Masum <hmasum(at)ALFRED.CCS.CARLETON.CA> asks:
>> 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.
>>

>-********** Material deleted *****************************

>Stephen Wolfram, among others, has poetically referred to processes performing
>'universal computations,' and we come to the second point of view mentioned
>above. But, in a supplement to one of A.K. Dewdney's articles in Scientific
>American, he states that to establish the universality of a cellular automaton
>it would be necessary to relate its activity to a Turing Machine, or some
>other
>model which has been shown equivalent.

>-***********************************************************************

In reference to Wolfram's contributions, he defines the notion of a
_totalistic_ cellular automaton, in which the state-transition function
depends only on the sum of the states of the cell's neighborhood, and
the sum includes the cell's own state. Each state is considered as a
nonnegative integer, and the quiescent state is 0. Wolfram conjectured
that even these simple cellular spaces are computation universal. Perhaps
this is an example of what the first poster means by "simple" cellular
automata. Note that the game of life is not totalistic: the transition
function depends on the cell's own state and on the sum of the neighboring
states.

It has been shown that even 1-dimensional totalistic cellular automata are
computation-universal, and this result proves Wolfram's conjecture. See:
D. Gordon, "On the computational power of totalistic cellular automata,"
Mathematical Systems Theory, vol. 20 (1987), pages 43-52.