hints and topics, anyone?
Bill Trost,Box 607,ext 571,497
backbone's disk drive had fallen over and all the little files had
slid out onto the floor in a big jumble....)
I have embarked on my undergraduate thesis in mathematics, and have
chosen cellular automata as my topic. Of course, this is much too
broad a category, so I've been looking for more specific areas in
which it might work. (This is to be a one-year thesis). So far, I've
mostly been doing work involving computation with automata, but I'm
looking for other ideas as well.
I have a few questions. First of all, in some of my reading I've seen
mention of Conway's and Gosper's proof that life is Turing equivalent.
Would anyone have references on this?
Also, though I've been reading this newsgroup for quite some time,
only recently have I started saving articles from it. Would anyone
out there have archived this newsgroup? That would certainly give me
a basis from which to do further research.
Thanks one in all for replies I get. Please mail replies, whether or
not you post them --- I rarely find time to read news these days.
--
Whaddya mean, these are *my* opinions?? I never wrote that!
Bill Trost
tr...@reed.bitnet, but probably trost%re...@tektronix.tek.com
Rajeev Pandey
From: man@brunix (Mark H. Nodine) writes:
> In article <13...@reed.UUCP> tr...@reed.bitnet (Bill Trost,Box 607,ext 571,497) writes:
> >I have a few questions. First of all, in some of my reading I've seen
> >mention of Conway's and Gosper's proof that life is Turing equivalent.
> >Would anyone have references on this?
> A reference I have found to be very helpful is _The Recursive Universe_
> by William Poundstone, Contemporary Books, Inc.: Chicago (1985).
Another reference that I have found very useful is:
"What is Life?" Chapter 25 of the book _Winning Ways_, Vol. 2, by
Elwyn Berlekamp, John Conway and Richard Guy. (Academic Press, 1982).
In the chapter, there is a proof by construction to show that Life is
Universal (or Turing Equivalent), by giving equivalents to AND, OR and
NOT gates (plus addressing the ideas of input/output streams and auxiliary
storage) using the Glider (discovered by Conway) and Glider Guns (found by
Gosper's group at MIT).
On a different note:
I have gotten interested in Garden-of-Eden configurations in Life. All that
I have been able to uncover thus far is that there are 2 know configurations:
a 9x33 pattern found by Roger Banks et al at MIT in 1971, and
a 6x122 pattern found by J. Hardouin-Duparc in 1974.
Can anyone supply me with references to these or any other work regarding
Garden-of-Eden configurations???
Thanx!
--------
Department of Computer Science | Rajeev "Raju" Pandey
Computer Science Building 100 |
Oregon State University | Internet: rpa...@cs.orst.edu
Corvallis, OR 97331-3902 U.S.A. | UUCP: tektronix!orstcs!rpandey
(503) 737-3273 fax: (503) 737-3014| UUCP: hplabs!hp-pcd!orstcs!rpandey
Mark H. Nodine
>mention of Conway's and Gosper's proof that life is Turing equivalent.
>Would anyone have references on this?
A reference I have found to be very helpful is _The Recursive Universe_
by William Poundstone, Contemporary Books, Inc.: Chicago (1985).
--Mark
Dean Hickerson
says:
>
> I have gotten interested in Garden-of-Eden configurations in Life. All that
> I have been able to uncover thus far is that there are 2 know configurations:
>
> a 9x33 pattern found by Roger Banks et al at MIT in 1971, and
> a 6x122 pattern found by J. Hardouin-Duparc in 1974.
>
> Can anyone supply me with references to these or any other work regarding
> Garden-of-Eden configurations???
The 9x33 is given in William Poundstone's book "The Recursive Universe", in
Martin Gardner's book "Wheels, Life, and Other Mathematical Amusements", and
in issue 3, page 31 of "Lifeline". (The latter was a newsletter devoted to
Life, published by Robert T. Wainwright during the early 1970s; it's an
excellent source of information on the subject. Wainwright has complete sets
(11 issues, 140 pages) of Lifeline for sale for $13 plus $2 postage. His
address is: 12 Longue Vue Avenue, New Rochelle, NY 10804.) Gardner mentions
the 6x122, but I haven't seen what it looks like.
One other good source of Life info is the article "Some facts of Life" by
David J. Buckingham, which appeared in the Dec. 1978 issue of BYTE. (By
the way, if anyone knows Buckingham's current address, could you please let
me know? Thanks.)
Berlekamp, Conway, and Guy's book "Winning Ways" gives a proof that a
Garden of Eden must exist inside a square that's 2325816000 on a side. But
recently, Allen Wechsler sent me a proof (which he learned from Conway
around 1971) which shows that there must be one in a 40x40 square:
Among the 512 patterns in a 3x3 square, it turns out that only 140 cause
the center square to be on in the next generation. Now consider a
3Nx3N square, divided into N**2 3x3 squares. ("**" indicates
exponentiation.) Among the patterns which fit in the 3Nx3N, there are
140**(N**2) which cause all of the 3x3 centers to be on in the next
generation. Now look at the (3N-2)x(3N-2) square obtained by removing the
outer rim of cells from the 3Nx3N. Among the patterns in this square,
there are 2**((3N-2)**2 - N**2) which have all N**2 centers turned on. But
if N=14, then
2**((3N-2)**2 - N**2) > 140**(N**2).
That is, there are more patterns with all centers on than there are
possible predecessors for them, so at least one such pattern must be a
Garden of Eden.