Searching detailed description of Codd's automaton
Frank Buss
E.F. Codd, "Cellular Automata", Academic Press (1968).
in which Codd describes a 2D CA with 8 states, which has the same
capabilities as von Neumann's 29 state CA (both 5 neighbor model). I want
to implement it as a Java applet, because on my way to implement a
universal CA computer I want to study important researchs first, but I
can't find the rule set and the initial setup anywhere, and the book is out
of print, so I've tried to buy it as a used book at Amazon, but I don't
know, if there is one available.
Do you know a web site with the rule set and the CA setup or can someone
eMail me scanned images of the relevant pages from the book?
--
Frank Buß, f...@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Tim Tyler
: There is a book from Codd:
: E.F. Codd, "Cellular Automata", Academic Press (1968).
: in which Codd describes a 2D CA with 8 states, which has the same
: capabilities as von Neumann's 29 state CA (both 5 neighbor model). I want
: to implement it as a Java applet, because on my way to implement a
: universal CA computer I want to study important researchs first, but I
: can't find the rule set and the initial setup anywhere, and the book is out
: of print, so I've tried to buy it as a used book at Amazon, but I don't
: know, if there is one available.
: Do you know a web site with the rule set and the CA setup or can someone
: eMail me scanned images of the relevant pages from the book?
Codd's book was a neat thing at the time, (and I can't help you in
your search for it - unless you live near me) but I'm not sure it
makes a good starting point for explorations today.
I would probably recommend starting with Langton's loop.
That was inspired by Codd's structures - and inherited 8 states and
three-layer "wires" from them - but the size of the smallest known
self-reproducing agent was vastly reduced - as the constraint of
universal computation was dropped.
http://www.bekkoame.ne.jp/~ishmnn/java/langton.html has Langton's
loop in an applet.
--
__________
|im |yler http://timtyler.org/ t...@tt1.org
Frank Buss
> I would probably recommend starting with Langton's loop.
>
> That was inspired by Codd's structures - and inherited 8 states and
> three-layer "wires" from them - but the size of the smallest known
> self-reproducing agent was vastly reduced - as the constraint of
> universal computation was dropped.
I've considered this first, but I've read that this is based on one of
Codd's structure only ("periodic emitter"), so perhaps there are more
interesting ideas in Codd's book. Why reinventing the wheel? And of course,
universal computation is important, too, for my CA computer. But for
studying the self replicating concept, Langton's loop is a good idea.
Paul Chapman
I designed a 4-state 2D CA from scratch with the goal of universal computation back in October 2002. It isn't quite outer-totalistic: orthogonal and diagonal neighbours (in a Moore neighbourhood) are summed separately, but the CA's behaviour is still invariant under rotation and reflection.
I have given some idle thought to extending and adapting it to allow (computation-driven) self-replication. Your goal of 8 states might be achievable.
For a rough description, head for http://www.igblan.com/ca/camrm.html.
If you want to investigate further, I can provide you with the rules by email, and also an MCell implementation written by Gabriel Nivasch.
Cheers, Paul
Frank Buss
> I designed a 4-state 2D CA from scratch with the goal of universal
> computation back in October 2002. It isn't quite outer-totalistic:
> orthogonal and diagonal neighbours (in a Moore neighbourhood) are
> summed separately, but the CA's behaviour is still invariant under
> rotation and reflection.
Why it is important, to design totalistic or outer totalistic rules? I can
see that it will be easier to implement in hardware. Is it helpful for
programming a CA computer, if we have rotation and reflection invariant
rules (which is one consequence of totalistic rules, if I have understand
it correctly) ? Or is it possible to write shorter rules and programs with
non-totalistic rules?
> I have given some idle thought to extending and adapting it to allow
> (computation-driven) self-replication. Your goal of 8 states might be
> achievable.
Yes, Codd demonstrated it :-)
> For a rough description, head for http://www.igblan.com/ca/camrm.html.
>
> If you want to investigate further, I can provide you with the rules
> by email, and also an MCell implementation written by Gabriel Nivasch.
I think I have to implement a CA doing universal computation by myself for
a better understanding, like my first test for setup a CA from serial
input (http://www.frank-buss.de/automaton/fbautomaton.html), but it is
always a good idea to see what ideas there are already invented, so you
can send me the rules and MCell implementation, or better, publish it on
your web page for other people, too. I can translate it to an Java applet,
if you like, which will be published under GPL, so you can include it on
your web page as well.
Paul Chapman
> Why it is important, to design totalistic or outer totalistic rules?
There seems to be a general feeling among CAers that totalistic CAs are "cleaner" or "simpler" than non-totalistic rules. I guess the bigger the gap between the complexity of the rules and the complexity of the emergent behaviour, the more startling ("deep"?) it is that the latter is a consequence of the former.
> Is it helpful for
> programming a CA computer, if we have rotation and reflection invariant
> rules (which is one consequence of totalistic rules, if I have understand
> it correctly) ?
Certainly some of the "components" I used in my design (particularly the signal merge and split components) are used in many different orientations, so it was helpful to start with the transformational invariance of a quasi-totalistic CA.
OTOH, my original notes are full of different ideas about how to lay out the various parts of the circuit. Had I chosen a different layout, maybe transformational invariance would have been less important. Chicken and egg.
> Or is it possible to write shorter rules and programs with
> non-totalistic rules?
It could well be. One problem I encountered with totalist rules was having to add rules here and there to "stabilize" the behaviour I wanted, eg to ensure that reactions where neighbours whose totals were the same but whose arrangment around the centre cell was different (for example HHOO versus HOHO) didn't produce undesirable side-effects.
The relative precision of non-totalistic rules would have removed this kind of problem.
Even so, from my limited experience I'd expect that a non-totalistic CA capable of computation would have more rules.
> > I have given some idle thought to extending and adapting it to allow
> > (computation-driven) self-replication. Your goal of 8 states might be
> > achievable.
>
> Yes, Codd demonstrated it :-)
Well, I meant starting from the particular CA I'd already built. :)
Mitchell's review, which you cited above, also mentions a 4-state UC/SR CA by Banks in 1971. (Incidentally, in her description of the operation of Von Neumann's original SR, she leaves out the tape-copy step. She does however mention that this step is needed in any computation-driven SR later on.)
> I think I have to implement a CA doing universal computation by myself for
> a better understanding
I agree. More instructive and much more fun that way.
> ... publish it on your web page for other people, too.
I have added the rules for my 4-state CA to the end of http://www.igblan.com/ca/camrm.html.
I shall ask Gabriel Nivasch for permission to publish his MCell .DLL on my site.
> I can translate it to an Java applet,
> if you like, which will be published under GPL, so you can include it on
> your web page as well.
I was thinking of doing something similar, but haven't had the time. If you happen to write a Java applet anyway, I'd be delighted to be able to include it.
Cheers, Paul
Frank Buss
> Even so, from my limited experience I'd expect that a non-totalistic
> CA capable of computation would have more rules.
Yes, perhaps you are right.
Another question: What about 3D instead of 2D? I think in 3D you can do
easier signal routing (but it would be slower to simulate on PC, if not
optimized, for example skipping regions of empty cells fast).
> I have added the rules for my 4-state CA to the end of
> http://www.igblan.com/ca/camrm.html.
Nice. I've implemented it as a Java applet:
http://www.frank-buss.de/automaton/mrmautomaton.html
Perhaps it should be enhanced to show the data input and output as normal
numbers.
Frank Buss
> There seems to be a general feeling among CAers that totalistic CAs
> are "cleaner" or "simpler" than non-totalistic rules. I guess the
> bigger the gap between the complexity of the rules and the complexity
> of the emergent behaviour, the more startling ("deep"?) it is that the
> latter is a consequence of the former.
That's true. I've implemented a trivial hexagonal totalistic CA and it is
really amazing how complex the behaviour looks like, even with only 3
states and very simple rules:
http://www.frank-buss.de/automaton/hexautomaton.html
In general I think it is easier to implement a CA with universal computing
capabilities and self-replication capability with hexagonal space, because
then you have 3 axis for gliders without more rules or states, compared to
only 2 axis for normal quadratic space. 3 axis in 2 dimension should help
building some interesting automaton.
For 3D CAs the space should be something like this:
http://mathworld.wolfram.com/Space-FillingPolyhedron.html
Perhaps a tetrakaidecahedron in the regular form of the truncated
octahedron would be the best (I've build one out of paper :-)
http://mathworld.wolfram.com/Space-FillingPolyhedron.html
Paul Chapman
> Another question: What about 3D instead of 2D? I think in 3D you can do
> easier signal routing...
True, although the signal routing in the MRM is pretty straightforward. The main gain, perhaps, from more dimensions would be reduced average distance between the states and storage.
> Nice. I've implemented it as a Java applet:
>
> http://www.frank-buss.de/automaton/mrmautomaton.html
Fast work! I'll add a link to my site later.
One optimization you could add would be to look only at H cells and their neighbours when animating. This would mean maintaining sets of M, H and T cells, ie three (hashed) sets of points.
I might look at adding this optimization myself later.
> Perhaps it should be enhanced to show the data input and output as normal
> numbers.
Up to you. :)
Cheers, Paul
Kent Paul Dolan
> In general I think it is easier to implement a CA with universal computing
> capabilities and self-replication capability with hexagonal space, because
> then you have 3 axis for gliders without more rules or states, compared to
> only 2 axis for normal quadratic space. 3 axis in 2 dimension should help
> building some interesting automaton.
Umm, you aren't limited to the major axes in designing gliders. The
Langton's virtual ants (vants) equivalent of gliders is building a
repeated path away from the original starting mess in O(n) time per
pixel of axis advance, and I've found a wealth of rational x/y angles
such a path should take, back when I obsessed on vants for a couple of
years. I'm sure CAs are equally capable of shooting a glider along
any rational x/y path given sufficient glider and rule complexity, and
postings here by Tim Tyler seem to point the same way.
Thus, even in a square grid, you have a potential countable infinity
of glider path angles.
xanthian.
Tim Tyler
: Frank Buss <f...@frank-buss.de> wrote:
I once wrote a CA capable of sending gliders in any "rational" direction.
http://finitenature.com/soliton_essay/
...and...
http://finitenature.com/soliton/ (Java applet)
...have the details.
For other automata (e.g. the game of life) a range of glider directions
are known - but there's not yet any known construction that results in
such gliders - or even a proof that such structures exist.
However, if you're trying to make a computer it might make sense to
try and use small gliders to send signals - for efficiency's sake -
and with small gliders there are severe limits to the number of
available directions.
Of course I'm very keen on doing things with hexagons - as
http://hex.org.uk/ attests.
Hexagons are the often the best way of packing things together in 2D.
This is naturally true of small scale electronic components with lots
of small identical units - such as FPGAs.
Unfortunately, today's circuit designers seem stuck in a rectangular
world. ;-)
Frank Buss
> Umm, you aren't limited to the major axes in designing gliders. The
> Langton's virtual ants (vants) equivalent of gliders is building a
> repeated path away from the original starting mess in O(n) time per
> pixel of axis advance, and I've found a wealth of rational x/y angles
> such a path should take, back when I obsessed on vants for a couple of
> years. I'm sure CAs are equally capable of shooting a glider along
> any rational x/y path given sufficient glider and rule complexity, and
> postings here by Tim Tyler seem to point the same way.
Vants applet:
http://www.ecst.csuchico.edu/~amk/foo/cscijava/labs/lab2/hall/SimVants.html
Looks like it is not difficult to have multiple angles, even in a square
grid. But I think the rules have to be more complex in a square grid than
in a hexagonal, given a fixed number of angles, at least if you use a 4-
neighbour totalistic CA. For 8-neighbour totalistic CAs probably the rules
will be of the same complexity for 8 directions as the rules for 6
directions on a 6-neighbour totalistic hexagonal grid CA.
BTW: I've found a spinning emitter, added it to the applet and added some
pictures: http://www.frank-buss.de/automaton/hexautomaton.html
Frank Buss
> One optimization you could add would be to look only at H cells and
> their neighbours when animating. This would mean maintaining sets of
> M, H and T cells, ie three (hashed) sets of points.
Yes, this would speed up the animation. There are not many H and T cells,
so a fixed array should do it.
>> Perhaps it should be enhanced to show the data input and output as
>> normal numbers.
>
> Up to you. :)
I don't want to do it (not interesting enough for me), but if someone like
to implement it, I'll publish the changes on my web page. Perhaps the
numbers should be displayed near the structures which represents the
numbers (drawString(...) in update after image drawing, has to be double
buffered).