Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!mit-eddie!uw-beaver!zephyr.ens.tek.com!sol!tekchips!ferrari!scott
From: scott@ferrari.LABS.TEK.COM (Scott Huddleston)
Newsgroups: comp.theory.cell-automata
Subject: Re: Berelekamp/Conway proof...
Message-ID: <7824@tekchips.LABS.TEK.COM>
Date: 25 Feb 91 20:28:28 GMT
References: <9102191525.AA08177@t13.lanl.gov>
Sender: news@tekchips.LABS.TEK.COM
Reply-To: scott@ferrari.LABS.TEK.COM (Scott Huddleston)
Distribution: inet
Organization: Computer Research Laboratory, Tektronix, Inc., Beaverton OR
Lines: 45

In article <9102191525.AA08177@t13.lanl.gov> cgl@t13.Lanl.GOV (Chris Langton) writes:
>angelo@gem.stack.urc.tue.nl writes:
>>  .....because now I have also read 'Winning ways'.
>>  I believe that the Life computer presented there (or rather the 
>>  elements to build one) will not work. I hope Callahan's TM will.
>
>  Can you expand on your doubts about this proof? 
>  
>  I have implemented many of the components, and they seem to work
>  as advertised...
>  
>  Where do you think the Life computer presented in Winning Ways 
>  breaks down?

I'm not angelo@gem.stack.urc.tue.nl, but I have some doubts about the
Berlekamp/Conway proof.  Here they are.

I question their constructions that require creating glider guns
at arbitrarily large distances away from a starting configuration.
To transport the gliders used as basic components to their destination,
their construction sends the gliders up between 2 parallel streams
in a kickback reaction.  I have a serious doubt and a minor qualm.

1. Look at the arrival timing constraints on the gliders used to
build a glider gun.  Most can arrive arbitrarily far apart in time,
which will work fine with the Berlekamp/Conway transport contruction.
But one pair must arrive at a precisely synchronized time, a few ticks
behind its predecessor.  How can a Berlekamp/Conway 2-stream kickback
transport accomplish this?
(Comment:  The "standard" (i.e. oft-repeated) construction of a glider
gun from gliders uses 13 gliders.  But 12 suffice (an exercise for the
reader).  My question applies to both constructions.)

2. (minor qualm) The Berlekamp/Conway 2-stream kickback transport for
gliders requires that the streams be synchronized so that they're all
ultimately annihilated.  How is the information and control to accomplish
this handled?

Perhaps my doubts only apply to their claim that a self-reproducing life 
configuration is possible (or one that can reproduce itself arbitrarily
far away).  I'm perfectly happy with their construction of a memory of
arbitrary capacity acheived by moving blocks in and out.
--
Scott Huddleston
scott@crl.labs.tek.com