CAs and universal computing
Ross Rhodes
proving that a 2-state 5-neighborhood CA can be computation universal. This
is the "wonderful train of logic" that Ed Fredkin cites to when discussing
universal CAs.
Parts 1 and 2 discuss Boolean logic and CAs generally, which may seem a bit
elementary for this group. The operative section is Part 3 which takes up
Banks' proof.
Here is the link:
http://www.bottomlayer.com/bottom/banks/banks_commentary.htm
Your comments are solicited.
- - - - - - - - - - - - - - - - - - - - - - - -
His
RhodesR -at- BottomLayer.com
Mark
- - - - - - - - - - - - - - - - - - - - - - - -
Ross Rhodes <www.bottomlayer.com>
daniel B miller
think perhaps I should.
Just to clarify: it appears that this is *not* a reversible CA.
Furthermore, to compute with this CA one would have to find a way to set
up the 'wires' and such in a complex pattern. In practice it would seem
that the wireworld approach is somewhat more efficient (ie
http://karl.kiwi.gen.nz/CA-Wireworld.html). By using three states, you
can cut down the complexity of your layout by about an order of magnitude.
All of these schemes seem to suffer from the fact that you need to
pre-wire the CA to do anything useful. If I recall correctly, Ed
Fredkin has said that Banks also came up with a 4-state CA that was
capable of universal construction, ie there is a way to get portions of
the CA to copy themselves into 'virgin' territory, which I take to mean
all 0's or some such low-entropy initialized state. Previously, Von
Neumann had done it with 29 states (Perhaps there were intermediate
reductions in the number of states required?). I'm going to track this
one down.
-dbm
Tim Tyler
> If I recall correctly, Ed Fredkin has said that Banks also came up
> with a 4-state CA that was capable of universal construction, ie there
> is a way to get portions of the CA to copy themselves into 'virgin'
> territory, which I take to mean all 0's or some such low-entropy
> initialized state. Previously, Von Neumann had done it with 29 states
> (Perhaps there were intermediate reductions in the number of states
> required?). I'm going to track this one down.
History in this area is usually given as:
JVN: Theory of Self-Reproducing Automata, ed. Arthur Burks;
Codd, 1968: http://www.amazon.com/exec/obidos/tg/detail/-/0121788504/
Conway's game of life - a two state, universal self-replicator;
Langton's loop: http://www.bekkoame.ne.jp/~ishmnn/java/langton.html (applet)
The early works were all to cumbersome to actually construct at the time -
but implementing self-replicating CAs is now a fairly trivial task.
http://www.cs.bgu.ac.il/~sipper/selfrep/ fills in the blanks in the history.
--
__________
|im |yler http://timtyler.org/ t...@tt1lock.org Remove lock to reply.
Ross Rhodes
> Fredkin has said that Banks also came up with a 4-state CA that was
> capable of universal construction, ie there is a way to get portions of
> the CA to copy themselves into 'virgin' territory, which I take to mean
> all 0's or some such low-entropy initialized state. Previously, Von
> Neumann had done it with 29 states (Perhaps there were intermediate
> reductions in the number of states required?). I'm going to track this
> one down.
Banks' description of his 4-state constructor CA is given at Part VIII,
pages 35-42 of his thesis, and illustrations at Appendix IV. He cites to
von Neumann and Codd as earlier work in this area. It is quite interesting,
but also "considerably more complex" than the 2-state machine that I
discuss.
RR
Eray Ozkural exa
> I have pretty much finished a commentary on Roger Banks' 1971 MIT thesis
> proving that a 2-state 5-neighborhood CA can be computation universal. This
> is the "wonderful train of logic" that Ed Fredkin cites to when discussing
> universal CAs.
>
> Parts 1 and 2 discuss Boolean logic and CAs generally, which may seem a bit
> elementary for this group. The operative section is Part 3 which takes up
> Banks' proof.
>
> Here is the link:
> http://www.bottomlayer.com/bottom/banks/banks_commentary.htm
>
> Your comments are solicited.
It's an amazing account of a work not as widely known by computer
scientists as it should. Thank you very much for this rigorous and
digestible commentary. The animations were quite informative, as well.
After seeing them, one looks at computation differently. Seeing the
signal propagate itself through the gates defined by mere bits, in a
beautiful example of simulacra, makes one ponder: is this the bottom
layer?
Best Regards,
--
Eray Ozkural
Frank Buss
> It's an amazing account of a work not as widely known by computer
> scientists as it should.
At least I know it :-)
http://groups.google.com/groups?selm=b41ot8%242ic%241%40newsreader2.netcologne.de
> Seeing the signal propagate itself through the gates defined by mere
> bits, in a beautiful example of simulacra, makes one ponder: is this
> the bottom layer?
I think it must be a bit more complex, because the simple 2 state
automata from banks needs pre-wired wires, but Banks "Self-Reproducing
Universal Computer, Universal Constructor" on page 35 of his thesis (
http://www.bottomlayer.com/bottom/banks/banks_thesis_1971.pdf ) is a
good candidate (looks a bit like the virtual CA
http://www.frank-buss.de/automaton/virtual/index.html ). But it is not
reversible, which is probably needed for "the bottom layer" (assuming you
mean the idea, that the universe is a CA).
--
Frank Buß, f...@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Ross Rhodes
news:c5mj7c$du9$1...@newsreader2.netcologne.de...
RR
Eray Ozkural exa
"Ross Rhodes" <sor...@beans.com> wrote in message news:<107ume6...@corp.supernews.com>...
> > I think it must be a bit more complex, because the simple 2 state
> > automata from banks needs pre-wired wires, but Banks "Self-Reproducing
> > Universal Computer, Universal Constructor" on page 35 of his thesis (
> > http://www.bottomlayer.com/bottom/banks/banks_thesis_1971.pdf ) is a
> > good candidate (looks a bit like the virtual CA
> > http://www.frank-buss.de/automaton/virtual/index.html ). But it is not
> > reversible, which is probably needed for "the bottom layer" (assuming you
> > mean the idea, that the universe is a CA).
> >
> > --
> > Frank Buß, f...@frank-buss.de
> > http://www.frank-buss.de, http://www.it4-systems.de
> >
> Great stuff! Terrific animations! And links to more good stuff.
> RR
Yes, reversibility would be needed for the bottom layer. Thanks for the link Frank.
Best Wishes,
--
Eray
dan miller (moderator, s.p.d)
> moderator: I am doomed! My posts don't show up on google!
>
with the full header versions of your dropped posts! Ed & I have
already sent them numerous emails about this problem. We have no idea
why some posts get dropped; it's very random, though some people
apparently always get dropped. We have very little leverage with Google
as it's a free service; I hope some emails from non-moderators of the
group will help get their attention.
Meanwhile, I encourage everyone to stick with a news server until this
gets sorted out.
- dbm