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

Fri Jul 12 12:56:03 EDT 2002

hi all.

re: the recent dialogue here on FOM about wolfram's
book, CAs (cellular automata), and rule 110.

I went hunting down the proof attributed to matthew cook
that CA rule 110 is turing complete, and ran into this
very unexpected history.  wolfram sued matthew cook
in court over the proof, and its been withheld from the public!! 
I posted on this on the newsgroups & there's a 
thread going on it currently. this was the original
subject of my post here, see below.

meantime I initially submitted a simple writeup of the wolfram-cook
situation here on FOM but encountered 
many requests for clarification on CA background
from a moderator on the FOM board. fortunately CAs really 
interest me, I have several references immediately handy
& its straightfwd to provide the material, & Im happy to be the
one to introduce it all to this elite crowd & forum.

so we have a rough minitreatise & survey on CAs for mathematicians 
at the beginning.

CAs: so what??
---

so, why should mathematicians & theorists care about CAs? lets answer that
in a nutshell. essentially CAs are just another potentially
turing-complete version of computation, along with many, many
other models I hope someone writes a web page or book on turing completeness
someday and all the places its been discovered or mapped to, 
an excellent and fascinating subject.  some of the more remarkable:

- diophantine equations. this settled the famous hilbert question
about decidability via the matiyasevich & robinson proof, arguably
one of the most important proofs of the 20th century.
- nonlinear dynamics. a result due to doria and daCosta
- economics, related to arrow-debreu equilibrium
- I think I just ran across a paper finding it in elliptical functions

however there is some case to be made that CAs are 
one of the simplest forms of turing complete systems possible.  
the rules are extremely simple.

moreover, because CA computations are so simple, it is easy
to argue that they are readily "implemented" in physical
models and perhaps even frequently naturally "emerge". 
wolfram is suggesting that physical reality might have
many different contexts to "implement" CA rules. he is also arguing
an idea that dates mainly to fredkin, that the underlying universe
is a 3D CA computation, and all "surface" phenomena are the
outcome of its rules!! 

that is, the assertion is that the underlying physics of reality
is a CA. I personally strongly endorse this, although not as a proven fact, 
but as an outstanding ongoing research program with strong circumstantial
evidence, and my own intuition behind it!

CAs went through a fad phase in the scientific literature and
then tended to die out. they are vulnerable to "toy" status.
it was similar to fractals-- before their
deeper implications were apparent, conservative scientists
had quite legitimate reason to question whether they were anything 
substantial or just "pretty wallpapering now covering the planet" (in one
famous criticism.)  but the turing completeness of some CAs seems to
resolutely counter any claims they are trivial.

turing completeness in CAs
--

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. 

this is not so surprising given the authors treat it almost
more as a question of physics than mathematics (initial inquirers
were von neumann & ulam, both atomic physicists).
basically what the authors all do (starting with 
von neumann) is show that there exists some initial pattern 
in the chosen CA system that
fully mimics a turing machine, in this sense:

- one turns on or off certain "input cells" of the CA according 
to the initial tape contents of the turing machine, they are scattered
over the CA at regular intervals. all other cells are set according to
the "initial configuration pattern" that constructs a "machine" with
a tape head, state table, etc all encoded in CA patterns. depending
on the CA rules, it may be straightfwd or far more abstract.

- one shows that the evolution of the CA after this point by the
deterministic state transition tables/rules also fully mimics the
exact behavior of a TM.

- at some point the TM might halt and "accept" the computation
if the input is in the set of terminating inputs.
this may be mirrored in the CA as "no further evolution" of any patterns
i.e. a steady state. the tape will contain the same end results on the
tape (available via decoding the particular squares)
the TM machine did. (so one could compute arithmetic or whatever.)

- on the other hand, by nature, the computation may
never stop, represented by an overall pattern that continues 
to evolve forever.

- a true TM doesnt limit the size of a tape. but to
accomplish this in a CA may require setting up an infinite periodic pattern
for the tape length in the initial conditions, as opposed to 
a finite size pattern in some cases.

these items would be the basic criteria that could be turned into a 
strict formal definition more satisfactory to mathematicians.

these proofs are all very ingenious and remarkable, they resemble
feats of mechanical engineering almost more than mathematics. or rather
they show a sort of amazing fusion of mathematics & mechanical engineering.
it all captures a striking analogy between physics and information
that wolfram & others are so understandably enamored with.

so the cook proof would basically follow these approaches. for another
example see the rendell link I include below-- in this case
especially a picture is worth thousand words. as I undertand it his requires
an infinite periodic pattern in the initial conditions for the tape. in
other words if you have only a finite number of initial cells turned on,
then its like a TM that runs on a finite tape.

the simple way to imagine all this is that the CA cells behave sort
of like "atoms" that have semiphysical properties. an "on cell" is
like an atom, an "off cell" is like space, and one can establish
rules for cellular-atomic interactions (such as types of "motion" and
"collisions" and the aftereffects), so to speak. one maps out the
"physics" of the CA and uses it to construct machines with "moving
parts". (hence the plausibility in fredkins idea that the 
universe may be a massive 3D CA, where particles are persistent patterns.)

brief history of CAs
--

very nice summaries of CA background on a popsci level are given in 
john casti's "complexification" or "artificial life" by levy.

von neumann started to consider the problem of patterns in CAs that
could "self-reproduce" themselves, and asked what would be required. 
he reduced this problem to that of creating a simulation 
of a turing machine (TM) via CA patterns. he chose a 2D CA to show this.

his work revealed that a system that was composed of a "machine plus
its blueprint" was sufficient. the "machine" within the CA grid
read its own blueprint & created a new version of itself from the
blueprint. this work was done BEFORE the discovery of DNA by watson
& crick, hence considered one of the great prescient
scientific foreshadowings of the 20th century by von neumann.

so von neumann proved two important results: (a) some CA patterns
could self reproduce based on CA rules (b) 
some CA rules were sufficient to simulate
TMs in the patterns. the two results are intertwined.

the results were extended to Life by conway. the Life game is
just one implementation of 2D CA rules, but it has been shown
to be one of the few "interesting" cases of 2D rules. 
conway extended von neumann's result to show that 
Life could contain a turing machine simulation.

the Cook proof follows this line of thinking and purportedly
proves turing completeness of a 1D CA system.  but alas the
details & clarification are not yet available.  I am personally
somewhat hoping wolfram will relent under the 
public glare & release the proof.

1D CAs
---

the 1 dimensional CAs have been numbered and explored by wolfram, there 
are a total of only 256 rules.  some of the behaviors are obviously
not "sophisticated" enough to support turing completeness.
but rule 110 has particularly unusual behavior and was analyzed closely.
it was speculated that it could simulate a turing machine and indeed
a proof was discovered by matthew cook in about ~1995.

as far as I know, none of the other 255 1D rules have been proven
turing complete, although some may still be conjectured to be.
so rule 110 may indeed be a theoretical gem: possibly the simplest
form of turing completeness ever discovered. its certainly a prime
candidate. although, so far, I dont know of anyone advancing its case
relative to all the other simple TM rules. (another excellent topic for
scientific paper(s).)

wolfram has his own book of collected papers,
Cellular Automata and Complexity, which is mainly an empirical
& statistical analysis of their properties, a mapping of some of
the more obvious features. "but is it science?" imho, absolutely.
"is it a new kind of science?" imho, absolutely. one that indeed
foreshadows the trend of 21st century algorithmics & mathematical 
inquiry.

for more on rule 110 and the other rules see wolframs book or
this link below maintained by tim tyler that gives the 
wolfram numbering scheme.

http://alife.co.uk/ca/wolframnumbers/

rule 110 & legal action!!
---

first a little more background.
usually I can track down many papers very quickly on the internet
with the help of google & citeseer.  and more researchers
are putting up their old papers on their own web sites.
(sometimes researchers put papers on their own web 
sites & home pages that are technically
copyright by journals or in books!) 
there is some tension between researchers & publishers
right now in this area, to say the least. 

anyway, I figured it would be easy to track down this CA 110 proof
and was looking forward to getting into some of the juicy details. 
but as I wrote, there seemed to be a scarcity.

someone that subcribes to theory-edge tipped me off that 
the proof had actually been restricted from publication 
by a court order issued by wolfram!! with this info I was
able to track down some of the info from google newsgroup
archives, which I attach below.

basically, apparently wolfram SUED his own employee, matthew
cook, over the CA 110 proof. from what I can piece together
(some of this may not be exact) cook formulated and wrote up the proof
completely in a paper that was also available on his web site,
maybe around 1995, and apparently even presented it at a CA
conference. the paper was submitted for publication in
the book New Constructions in Cellular Automata coedited by
chris moore, who reviewed the proof & accepted it. 

http://www.amazon.com/exec/obidos/ASIN/0195137175/

however apparently wolfram obtained a COURT ORDER against cook to stop
publication of the paper (or something like that), 
at which point the CA book was delayed
and eventually released without cook's proof, 
"one of the most interesting results presented at the conference" acc.
to SFI web site. 

the paper was yanked from the web site also. apparently wolfram claims
it was a "trade secret". I actually tracked down the case number
on the LA civil complaint via the web (see below), maybe someone can get
more info on it, I assume it is part of the public record.

what's the ethics & propriety of all this???
---

now I havent read NKS yet, but my understanding is that while
crediting cook, it doesnt refer to the court order, and it
does NOT give the full proof. so as far as I know, one cannot
obtain the full info anywhere. maybe wolfram (inc.) wants to sell it to
the highest bidder someday? I can only speculate. one could easily
argue the commercial value of the proof is nil whereas its
scientific value is signficant, esp as a centerpiece for 
wolframs claims for a Principle of Computational Equivalence in
nature.

I think wolfram needs to answer for all this & I am hoping
to see a scientific dialogue/debate on the subject, maybe here
but ideally, even in professional journals, debating the ethics
& implications of it all. it cuts to the core of the intellectual
property debate that is bouncing through cyberspace and courtrooms
in many dimensions (academic publishing being one area), and
also the "science versus business" or "science versus profit"
battlelines..

one could argue its a profoundly **antiscientific** 
action on wolframs part, a skeleton in his closet. scandalous!!

the whole affair is quite strange. I wonder why it got
to the point of a court order, which also mentions Caltech.
did Cook initially refuse or resist? that seems to be implied
by the presence of an actual court filing, which is usually a last resort.
there is a big story in here somewhere.

some speculated that wolfram exerted the "blackout" because he
wanted to publish the proof in his own book, but that 
apparently did not happen. so, steven wolfram, what is the 
idea behind all this???

the CA 110 proof
---

the proof is said to be very ingenious.  indeed, acc. to moore as quoted
below, it is based on the glider rules as I speculated earlier.
rule 110 glider rules are very complicated and I was hoping to read
a tour-de-force paper.

by the way, the other link I gave seems to have broken sublinks;
this seems to be a complete version of an examination of
glider rules, although alas the
.tex file source file is missing (I would rather read it as
a paper than a hyperlinked document, but oh well)

http://delta.cs.cinvestav.mx/~mcintosh/comun/RULE110W/RULE110.html

I sent email to cook at his caltech address, but he has
not responded. I dont know if he still works for Wolfram Inc.
I would like to hear more of the story on all this.

"a new kind of science"
---

I am strongly in accord with wolfram that a new kind of science
is being born as we speak. imho he has nailed some aspects of it:

- greater influence of empirical research on scientific 
investigation via computer simulation
- possibly less emphasis on proof
- mathematics as subservient to, and reformulated as a subbranch of,
algorithmics
- the universe as a computation, low-level physics recast 
in terms of CA rules, a good candidate for a TOE (theory of everything), 
etcetera (ideas mainly already dating to fredkin)

however, reading reviews, it sounds to me that wolfram is weak
on one crucial point, which mathematicians can rightly lambaste
him on. this whole CA 110 affair seems to indicate a strange attitude
of his toward **mathematical proof**. 

isnt it astonishing that the book contains almost no mathematical proofs, 
and the one proof that it does, was not found by wolfram but by cook,  
and in fact **suppressed** for publication by him via the heavy
handed tactics of wolframs obtaining a court order against his own
employee??

wolfram has a set of collected papers on CAs (advertising NKS on the
back!!), which struck me as all very creative. but they are very
empirical & statistical. I think wolfram is missing one essence of 
theoretical computer science and mathematics and is weak in those areas. 
his new book consistently **downplays** the necessity, signficance, 
and paramount prominence of mathematical proof.

imho, mainstream scientists can rightly thumb their noses at wolfram
for this gaping blind spot on his part relative to theoretical analysis
and mathematical proof.  as long as his own brand of a 
"new kind of science" thumbs its nose at the supremacy and
indispensibility of mathematical proof for meaningful analysis,
it limps forward on only one leg.

it is not surprising wolfram would have this attitude.
it is of course a age-old blind spot that physicists share 
regarding mathematics. (wolframs earliest work was in particle physics.)

but one still has to ask.. is a hostile court order issued
against his own (virtuoso!! brilliant!!) employee, appropriating his
purely scientific work, wolframs idea of "a new kind of science"??

on one level I really dont care about all this-- I just want to see
that awesome proof!! but I resent wolfram for standing in the way of
me not just clicking on a PDF file and reading it this instant!!

other links
---

the wolfram book is now reverberating through the media.
this SFTimes article states wolfram has already sold 120,000
copies, an astonishing figure. personally I like the fact
that "theory-edge" type science, math, & algorithmics is seeing
widespread exposure and so Ive taken a strong interest in this. 

http://www.sfgate.com/cgi-bin/article.cgi?file=/c/a/2002/07/01/MN108224.DTL

thankfully the media is not totally into 
superficial puff-pieces, and has at least caught
on to deeper stories, such as wolfram's "credit where credit 
is due" problem, which appears esp.
acute relative to the work of fredkin.

fyi I also ran into this very nice link maintained by ed clark
that is compiling all the media reviews on NKS, very thorough
so far. I enjoyed the NYT book review that mused "maybe god
is a software engineer" haha

http://www.math.usf.edu/~eclark/ANKOS_reviews.html

for an example of a beautiful and sophisticated
proof of the turing completeness of a 
CA rule (the cook proof would have some similarity to this), 
consider this proof/construction appearing in year 2000
by paul rendell, for conway's life rules.

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

this page gives a list of all the "subcomponents"

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

I founded & moderate the theory-edge group & we discuss 
some of these themes..

http://groups.yahoo.com/group/theory-edge/

old newsgroup posts on CA 110 rule
---

From: Inka Dinka (inkadinka12 at y...)
 Subject: Cook's Proof & Wolfram 
 Newsgroups: comp.theory.cell-automata
 Date: 2002-06-07 20:23:50 PST 

I understand that Wolfram held up (via a lawsuit) the publication of
the book "New Constructions in Cellular Automata."   Apparently
Matthew Cook wrote a paper for the book that Wolfram's company claimed
ownership of as a trade secret.   Can anyone fill us in on the
details?   I noticed on the SFI web site that the book will soon be
published but is missing Cook's paper:

"Regrettably, one of the most interesting results presented at the
conference is not included in this volume. We hope that this result,
and a full proof of it, will appear in the literature soon."

Does anyone know if this paper was ever available as a pre-print?  
Are copies floating around?   Will it ever be published?

From: David Eppstein (eppstein at i...)
 Subject: Re: Wolfram's new book ... news?? 
 Newsgroups: comp.theory.cell-automata
 Date: 2001-01-05 08:42:06 PST 

In article <3A5587C9.F46DC982 at l...>, mathieu capcarrere 
<msc at l...> wrote:

> > Yes, maybe then he will drop this stupid blackout on Matthew Cook's proof
> > of Turing-completeness for rule 110.
> 
> DO you have an article reference for this rresult
> about 110 ?

No, I don't. It was on the web, and due to be published in the book "New 
Constructions in Cellular Automata" from the Santa Fe Inst. last spring, 
but now the web site is taken down and the book remains unpublished due to 
a lawsuit by Wolfram.  That's what I meant by "blackout".
-- 
David Eppstein       UC Irvine Dept. of Information & Computer Science
eppstein at i... http://www.ics.uci.edu/~eppstein/

From: Tim Tyler (tt at i...)
 Subject: Re: What is rule 110? 
 Newsgroups: comp.theory.cell-automata
 Date: 2001-06-14 22:34:10 PST 

Bill Taylor <mathwft at m...> wrote:

: I saw it mentioned with trepidation or awe, recently, but I've no idea what
: it was.  Can anyone help out?   Why is it special?

Rule 110 is one of Wolfram's rules - a 1D 2-state R=1 CA.

I have an explanation of Wolfram's numbering scheme at:

http://alife.co.uk/ca/wolframnumbers/

Rule 110 has been in the news of late - partly because of
Matthew Cook's proof of Turing-completeness for the rule - and
partly because of a lawsuit by Wolfram that means that the
proof is still not publicly available, that the web site it was
on no longer exists, and that the book which was going to carry it -
Griffeath and Moore, Eds., "New Constructions in Cellular Automata"
http://www.amazon.com/exec/obidos/ASIN/0195137175/ - has been delayed.

Reputedly the construction is of interest:

``While the computation is highly inefficient, the construction is
  extremely clever, and relies on interactions between various naturally
  occuring gliders in the system.'' - Chris Moore, SFI.

My best rule 110 link:

http://delta.cs.cinvestav.mx/~mcintosh/comun/RULE110W/RULE110.html
-- 
__________
 |im |yler  http://rockz.co.uk/  http://alife.co.uk/ 
http://atoms.org.uk/

the civil action, wolfram vs. cook
---

from a court news web site, apparently a civil complaint 
was indeed filed 8/31/2000 (as I read it) case 8/31 CV00-9357 CBM

http://www.courthousenews.com/cda/X-11/newcom11.html

>The following are summaries of new civil complaints 
>in the Central District, including case number. The attorneys 
>listed first are those that filed the paper bringing the matter 
>into federal court, either a plaintiff filing a complaint 
>or a defendant removing a matter from state court in which 
>case the plaintiff lawyer is also named. Law firms are located 
>in Los Angeles unless otherwise noted.
>The summaries review allegations only and should not be taken as
fact.
>
>
>
>Wolfram Research Inc. v. Matthew Cook
>
>8/31 CV00-9357 CBM
>
>Notice of joint stipulation and join stipulation re 
>plaintiff Wolfram Research Inc.'s motion to compel the
>production of documents from California Institute of Technology.
>
>
>Michael Kump, Kinsella Boesch

From: W. Edwin Clark (eclark at math.usf.edu)
 Subject: Re: scoop!! scandal!! wolfram sued own employee
 over rule 110 proof!! 
 Newsgroups: comp.theory, sci.math, sci.physics, comp.theory.cell-automata
 Date: 2002-07-03 20:37:04 PST 

"V.Z.Nuri" wrote:
> 
> rule 110 & legal action!!
> ---
> 

Here is a description of the situation from the articles 
"What kind of science is this?" 
by Jim Giles, Nature 417, 216 - 218 (2002) 

-----------------begin quote of Giles------------------------- 
But within the world of complex systems it is difficult to separate
reactions to the man from those to his ideas. One incident in particular
has driven
a wedge between Wolfram and his former colleagues. The rule 110 proof
was actually developed by Matthew Cook, a young mathematician who
worked for Wolfram between 1991 and 1998. After leaving Wolfram's
employ, Cook presented his results at a conference at the Santa Fe Institute.
But details of the talk never made it into the conference proceedings.
Wolfram took legal action, arguing that Cook was in breach of agreements
that prevented him from publishing until Wolfram's book came out. 

"We sympathized with Matthew," says one Santa Fe researcher. "Wolfram
took a privatized view of science." Cook, now a graduate student at
Caltech, says he cannot discuss the matter for legal reasons. Wolfram is
similarly reticent - when pressed he describes the incident as
"regrettable and best forgotten". 

It is not the first time that Wolfram has annoyed complexity
researchers, who feel that he routinely fails to recognize the
contributions made by
others. "He tends to acknowledge people in two-point type," says one
researcher. Indeed, A New Kind of Science lacks conventional references to
prior work - although scientists and mathematicians including Cook are
acknowledged in the book's notes section. 
-------------end quote of Giles----------------------------------