Google Answers Logo
View Question
 
Q: Cellular Automata and the Rule Fredkin ( No Answer,   2 Comments )
Question  
Subject: Cellular Automata and the Rule Fredkin
Category: Science > Math
Asked by: kbarclay-ga
List Price: $10.00
Posted: 16 Nov 2002 17:49 PST
Expires: 16 Dec 2002 17:49 PST
Question ID: 109115
I am looking for references to a mathematical proof of Edward
Fredkin's rule pertaining to Cellular Automata.  This paper must have
been published in the scientific literature, or done by reputable
names (Wolfram, Langton, Fredkin himself).  To satisfy my request I
must be able to read this paper, and the proof must be clearly labeled
and rigorous.

By this rule, I am specifically asking for the rule describing self
replication after a certain number of generations - the so-called
"Parity Rule."  This rule states that if the sum of the Von-Neumann
neighbors is odd, the cell becomes alive.

See 

http://cafaq.com/types/index.shtml#SECTION00011000000000000000 

for a description of the rule.
Answer  
There is no answer at this time.

Comments  
Subject: Re: Cellular Automata and the Rule Fredkin
From: mathtalk-ga on 16 Nov 2002 18:34 PST
 
Hi, kbarclay-ga:

According to Harold V. McIntosh, these are the published sources for
Edward Fredkin's discoveries about replication under the "parity"
rule:

Martin Gardner, Wheels, Life, and Other Mathematical Amusements, W. H.
Freeman and Company, New York, 1983. (ISBN 0-7167-1589-9 pbk)

Brian Hayes, ``Computer Recreations - The cellular automaton offers a
model of the world and a world unto itself,'' Scientific American,
March 1984, pp. 10-16.

A. K. Dewdney, The Armchair Universe, W. H. Freeman and Company, New
York, 1988. (ISBN 0-7167-1939-8 pbk)

http://delta.cs.cinvestav.mx/~mcintosh/newweb/ra/node2.html

According to the same author, writing in this Cellular Automata FAQ:

http://cafaq.com/properties/index.shtml

"In turn, Fredkin has acquired widespread fame for the replication
properties of the <exclusive or> when taken as a rule of evolution.
However, it is difficult to encounter a single reference which can be
cited, for either Toffoli or Fredkin, that can be fairly said to
present their own views. Martin Gardner reported Fredkin's replication
in his second article on Life in 1971, reprinted in [Gar83] thereby
giving the idea worldwide publicity."

I certainly consider Martin Gardner one of the "reputable names" in
the literature of cellular automata, but since he doesn't appear on
your short list, I will have to defer to your own judgement about his
level of rigor, etc.

regards, mathtalk-ga
Subject: Re: Cellular Automata and the Rule Fredkin
From: mathtalk-ga on 23 Nov 2002 14:54 PST
 
Hi, kbarclay-ga:

Since you mentioned Wolfram, I checked his recent book, Cellular
Automata and Complexity, to see how he cites Fredkin's work (located
from the index under "reversibility"), and found that while in the
text he refers to a reference "Fredkin '82", in the actual list of
references (at the end of that chapter) the entry becomes "E. Fredkin,
1981 (unpublished)" and a mention of a demonstration given at Three
Rivers Computer Corp.

-- mathtalk-ga

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy