FOM: CAs, rule 110, NKS, and the wolfram vs cook lawsuit

[Rupert McCallum]

--- vznuri at earthlink.net wrote:
<snip>
> 
> as a particular FOM moderator has been delving into & questioning me
> on, 
> the notion of turing completeness in CAs is 
> somewhat fuzzy from a mathematicians point of view of strict
> definitions. now that I think about it I recall some of my own
> "cognitive dissonance" first approaching the subject.
> I actually am not aware of a strict definition of 
> what constitutes turing-completeness in a CA by any author. 
> 

Okey-dokes. As soon as I read your post about rule 110 being Turing
complete I went and looked this up and I found the definition in the
library. Let's see if I can remember it.

According to the book I read, "Cellular Automata" by someone or other
(I'll get the reference for you)...

An n-dimensional cellular space is the set of n-tuples of integers,
called the cells, with a finite set of states, and a neighbourhood
function, which maps any cell x to {x+d_1,x+d_2,...,x+d_k}, where
{d_1,d_2,...,d_k} is a fixed finite set of n-tuples of integers,
addition being component-wise, and a transition function, which is a
mapping, from the set of functions from {d_1,d_2,...,d_k} to the set of
states, to the set of states. So that if x is a cell and f maps d_i to
the state of cell x+d_i at time m, then the image of f under the
transition function gives the state of x at time m+1. You've got to
have one quiescent state, so that if f maps everything in
{d_1,d_2,...,d_k} to the quiescent state, its image under the
transition function is the quiescent state.

A configuration is a function from the cells to the states, whose
support - the set of cells not in the quiescent state - is finite.
We'll also call a function from a finite set of cells to the set of
states a configuration. Now, say you've got two configurations in the
latter sense with disjoint domains, and you take the union of those two
configurations. Then you take the configuration defined on the whole
cellular space whose support is the domain of this latter configuration
and agrees with it there, and let it evolve. Say, at some future time,
you've got a cell which would be in a nonquiescent state if you'd just
had the first configuration evolving by itself, and it's in a different
state now than it would have otherwise been, because of the presence of
the second configuration. Then the second configuration passes
information to the first configuration.

A passive configuration is one which, um, just sits there. When
quiescent cells are everywhere else, it's a fixed point of the
evolution operator.

Now say you've got a bunch of passive configurations in effective
one-to-one correspondence with the natural numbers. That's a Turing
domain. The union of the support of all the configurations in the
Turing domain is the support of the Turing domain. 

Now say you've got a Turing domain, and one special cell called the
stopping cell, disjoint from the support of the Turing domain with one
special state called the stopping state, such that when that cell goes
into the stopping state, even just once, that signals the computation's
done. Now say a configuration, disjoint from the support of the Turing
domain, is such that, if you give it one of the configurations in the
Turing domain (i.e. you've got this configuration disjoint from the
support of the Turing domain, you've got one of the configurations in
the Turing domain, you've got quiescent cells everywhere else, and you
let the cellular automaton go), then if and when the stopping cell goes
into the stopping state, the configuration doesn't pass information to
the configuration consisting of the nonquiescent cells in the support
of the Turing domain, and further that configuration is a configuration
in the Turing domain. That that configuration (with respect to that
Turing domain and that stopping cell and stopping state) is called a
computer. And it computes a partial computable function. I bet you can
guess how to find out which one. A natural number n is in the domain of
the function computed by the computer if and only if if you take the
computer and the configuration in the Turing domain corresponding to
the natural number n, and let the cellular automaton go, the stopping
cell eventually goes into the stopping state at least once. In which
case, the configuration you've got in the support of the Turing domain
corresponds to f(n) where f is the function computed by the computer.
So the output is passive and no further information is passed to it by
the computer, but the computer is not necessarily passive thereafter.

Now, say you've got a cellular space, and for this cellular space you
can find a Turing domain, a stopping cell and a stopping state, with
respect to which, big drum roll, you can find a computer computing any
given partial computable function, then that cellular space, according
to the book I read for which I'll get you the reference, is called
computation universal. And I see no reason why it shouldn't be called
Turing complete as well.

<rest deleted>


__________________________________________________
Do You Yahoo!?
Yahoo! Autos - Get free new car price quotes
http://autos.yahoo.com