FOM: CAs as turing complete odds&ends

[vznuri@earthlink.net]

hi all; re the recent thread on wolfram & CAs as turing
complete etc.

Ive been looking for the proof that rule 110 is
turing complete attributed to matthew cook. one
web page called it "unpublished". does anyone know
a reference? the closest I can find is this comprehensive analysis
of "gliders" via rule 110. presumably a TM can be constructed
out of the glider rules.  the author says here people on the list
were "awaiting further details".

http://delta.cs.cinvestav.mx/~mcintosh/oldweb/rule110/rule110.html

this review of New Kind of Science by kadanoff
says the proof dates to 1994 and is "still unpublished"

http://es.arxiv.org/html/nlin.CG/0205068

afaik it is undecidable to prove whether CAs are turing
complete in general. but maybe there are some "sufficient
conditions" that can be established to attack the problem.

afaik, von neuman gave the 1st proof for turing completeness
of a CA system after which (as I understand it) he lost interest. 
sorry, I dont have the reference, maybe someone else does.

conway was the 1st to prove that life rules
are turing complete, in one of the more remarkable
proofs of the 20th century, imho (and a precursor
to 21st century ideas, along wolframs line of thinking).
however, its not very visualizable. it requires massive
amounts of space.

the following gem turned up in 2000 for turing completeness of Life.
paul rendell gave an interesting construction, and theres
a nice little picture on his web page. definitely 
"a new kind of science."  see the section describing
all the subcomponents, its really neat stuff. although
it looked to me like one has to set up empty tape squares 
via patterns ahead of time.

http://www.rendell.uk.co/gol/tm.htm