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.

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

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