One dimension, three or more states
Markus Redeker
there are a lot of articles about specific binary one-dimensional cellular
automata (rule 110, rule 53, and others). But are there any articles that
describe the behaviour of linear cellular automata with more than two
states?
Here I am interesting in "naturally" occuring automata, not those
constructed for a specific purpose. (Those automata usually have a lot of
states and/or an incomplete rule table. Three states and radius 1 would be
ideal, but I wont't be picky.)
--
Markus Redeker Hamburg, Germany
IzI
There are some k=3 class 4 automata on the DDLab page (see examples)
http://www.ddlab.com/
you can use the software too.
Than McIntosh discussed k=3 rules in some of his posts,
http://groups.google.com/group/comp.theory.cell-automata/browse_thread/thread/eedd3e963691fda2/41f376c8b51455b2?q=clusters&rnum=5&hl=en#41f376c8b51455b2
http://groups.google.com/group/comp.theory.cell-automata/browse_frm/thread/2375d42de9f86ee1?tvc=1&q=clusters&hl=en
http://groups.google.com/group/comp.theory.cell-automata/browse_frm/thread/b4596943ee04f3d6/9fffa47e715ffb7e?q=symmetry&rnum=6&hl=en#9fffa47e715ffb7e
IzI
McIntosh Harold V.
news:1128159151.5...@g47g2000cwa.googlegroups.com
> Then McIntosh discussed k=3 rules in some of his posts, ...
That was quite a while ago, but there are indeed rules or
classes of rules which can be considered interesting for one
reason or another.
1) Reversible rules. There are essentially two clusters of
(3,h) rules, 11 of (4,h) rules, and increasingly more of other
kinds of rules. Large neighborhoods can be reduced to two-cell
neighborhoods, which have been more extensively studied, and
then mapped back to their original size. Kari and associates
have nice results, including a good limitation on the size of
reversing rules. An early result was Fredkin's scheme od carrying
a history along with the states, which always yielded a reversible
rule, although not necessarily one reversing the original rule.
Some lists of results can probably be found in archives.
2) Xenophobic or Xenophilic Rules. Xenophilic rules require the
image to lie amongst the neighbors, xenophobic rules exclude
neighbors. This is vaguely related to the subautomaton structure
of the rule; anyway it can produce come interesting evolutions.
Somewhat related are the Paper, Scissors, Stone Rules, wherein
a cyclic dominance rule governs the evolution. Scientific
American once had a nice article featuring such a two-dimensional
rule, wherein random fields developed interesting spiral patterns.
3) It is always possible to search for Wolfram's Class IV rules.
The one-dimensional Rule 110 may have distracted the world from
a search for other rules of this type, and in truth it is far
more involved and interesting than other rules which have been
found. That shouldn't necessarily mean that the search is over.
4) Majority Rules, according to which the automaton is supposed
to evolve to some clearly recognized final configuration which
classifies the original configuration; the simplest example is
binary and should reveal any preponderance of one of the states.
5) Firing Squad Rules, whose objective is to evolve to a given
target state, usually constant, in finite time irrespective of
the original state.
There are no doubt others, such as the Chaté-Manneville Rules
(mostly in three dimensions and beyond) which challenge the
law of large numbers.
- hvm
--
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG
Tim Tyler
> 3) It is always possible to search for Wolfram's Class IV rules.
> The one-dimensional Rule 110 may have distracted the world from
> a search for other rules of this type, and in truth it is far
> more involved and interesting than other rules which have been
> found. That shouldn't necessarily mean that the search is over.
I'm inclined to think that:
http://www.ics.uci.edu/~eppstein/ca/wolfram.html
...means that the search is over, though.
--
__________
|im |yler http://timtyler.org/ t...@tt1lock.org Remove lock to reply.
Mcintosh Harold V.
news:Inq29...@bath.ac.uk
> I'm inclined to think that:
>
> http://www.ics.uci.edu/~eppstein/ca/wolfram.html
>
> ...means that the search is over, though.
As a greek philosopher reputedly asked, "If you don't know what you are
looking for, how will you know when you have found it?" Unfortunately,
Class IV is a rather vague concept; possibly only Stephen Wolfram (who
originated the concept) is qualified to judge its membership. Recall the
Supreme Court Justice who said, "I can't define pornography, but I sure
know it when I see it!"
Anyway, whatever Class IV represents, it has come to be associated with
Universal Computing (whatever that is), and the concept that evolution
according to Class IV could be demonstrably unpredictable. Is that any
worse than Class III, which is merely chaotic? Anyway, with the advent
of Rule 110, interest seems to have fallen off; my point in mentioning
Class IV as an area of possible interest is due to the fact that I am
not convinced that the subject is really exhausted. Especially if
several
conflicting themes are disentangled.
The cited reference to Eppstein's page is certainly interesting; I
hadn't
been aware such variety and limitations existed, although I must confess
to not keeping up with these developments as closely as I should. But
the
original inquiry sought interesting multistate one-dimensional automata.
There is still ample opportunity to clarify Class IV as a concept; one
idea which I have had is to look for return maps with a stable quiescent
state and a superstable neutral state. Rule 110 doesn't quite fit that
picture (maybe I need to think about this more carefully) but there
seems to be an agreement about its lying in Class IV. That it has such
interesting computational propeerties is just so much to the good, and
certainly confirms Wolfram's expectations (if it is so considered).
So maybe my point 3) should be broken down further:
3a) continue the search for a good definition of Class IV, or
propose another scheme for classifying automata. Beware: this
has certainly been tried.
3b) Just continue looking at Class IV candidates to see whether
they have any characteristics of note, such as a populous
glider family, interesting collisions between gliders, or
whatever.
3c) Make an extensive analysis of Cook's tag system. At the very
least it should make an interesting toy to play with, much as
simple Turing Machine exercises play a role in computer science
classes. Anyway, the Old Science demands a verification, peer
review, evaluation, applications, etc. It will never make a
practical computing system, no more than a Turing Machine
would, but there should still be a lot of interesting games
left in it.
3d) Rule 110 is nicely minimal, but are there other rules with
similar properties? Turing Machine models have certainly been
constructed; avoiding them was surely what the original inquiry
meant by calling for "natural rules." Thanks to Cook's
analysis,
Tag Systems are also fair game. Can they be realized under
other
circumstances?
Tim Tyler
> "Tim Tyler" <t...@tt1lock.org> wrote in message
> > I'm inclined to think that:
> >
> > http://www.ics.uci.edu/~eppstein/ca/wolfram.html
> >
> > ...means that the search is over, though.
>
> As a greek philosopher reputedly asked, "If you don't know what you are
> looking for, how will you know when you have found it?" Unfortunately,
> Class IV is a rather vague concept; possibly only Stephen Wolfram (who
> originated the concept) is qualified to judge its membership. Recall the
> Supreme Court Justice who said, "I can't define pornography, but I sure
> know it when I see it!"
>
> Anyway, whatever Class IV represents, it has come to be associated with
> Universal Computing (whatever that is), and the concept that evolution
> according to Class IV could be demonstrably unpredictable. Is that any
> worse than Class III, which is merely chaotic? Anyway, with the advent
> of Rule 110, interest seems to have fallen off; my point in mentioning
> Class IV as an area of possible interest is due to the fact that I am
> not convinced that the subject is really exhausted. Especially if
> several conflicting themes are disentangled.
Universality is interesting - though as a means of classifying CA it
suffers from the disadvantage of not being easily recognisable.
I think a significant selling point of Wolfram's classification scheme
was the idea that there was some sort of association between class IV
automata and universality.
However that now looks questionable - the classification scheme is
based around the idea of evolution from disordered states (or on
what "most" configurations do, depending on which Wolfram paper
you are working from). Evolution from disordered states doesn't
tell you much about what can happen with ordered states,
and it appears that universal automata exist in all Wolfram's
classes. If there's an association between universality and
class VI automata, it's not a very strong one.
There /are/ some other ways to classify CA that *do* throw light
on the universality issue.
One way is how linear they are. No linear CA are universal. There are
classes of "quasi-linear" CA that are proven not to be universal either.
Looking at CA from this direction actually tells you something
concrete about whether the CAs are universal or not.
Another perspective is the one Eppstein mentions. If a CA can
never expand its bounding box, it can't be computaion universal
either - unless it has an infinite initial configuration. Again,
that actually tells you something about its universality.
Then there's the idea of hunting for gliders. Gliders seem more
strongly assocatied with universal computation than the Wolfram
class is. If a CA is class I, II, or III - *and* gliders have
been found in it - I'd rate that information more highly than
its Wolfram class as an indication of universality.
A search of small objects for gliders is probably a bit more
work than looking at what "most" disordered states evolve into -
but we have fast computers these days - and we might as well
make use of them.
I'm sure there are other things besides universality that a CA
classification scheme might illuminate - however if universality
is of interest, IMO, you can generally make a better start with
classification than by looking at what Wolfram class an automaton
is in.
Ilmari Karonen
>
> Then there's the idea of hunting for gliders. Gliders seem more
> strongly assocatied with universal computation than the Wolfram
> class is. If a CA is class I, II, or III - *and* gliders have
> been found in it - I'd rate that information more highly than
> its Wolfram class as an indication of universality.
Of course, it probably goes without saying, but just having a glider
or two isn't enough to make a rule interesting; the gliders must also
interact in nontrivial ways. A rule in which all gliders move at the
same speed in the same direction, pass through each other without ever
interacting or always vanish on collision is unlikely to be universal.
--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.
"String theory is all very well, but I think I can beat it with my
chewing-gum and elastic band theory." -- Lemming on ahbou.d
Tim Tyler
> Tim Tyler <t...@tt1lock.org> kirjoitti 03.10.2005:
> > Then there's the idea of hunting for gliders. Gliders seem more
> > strongly assocatied with universal computation than the Wolfram
> > class is. If a CA is class I, II, or III - *and* gliders have
> > been found in it - I'd rate that information more highly than
> > its Wolfram class as an indication of universality.
>
> Of course, it probably goes without saying, but just having a glider
> or two isn't enough to make a rule interesting; the gliders must also
> interact in nontrivial ways. A rule in which all gliders move at the
> same speed in the same direction, pass through each other without ever
> interacting or always vanish on collision is unlikely to be universal.
On reflection, my idea about gliders probably isn't worth very much.
The presence of gliders doesn't say much about universality.
An absense of gliders doesn't mean a CA isn't universal either -
gliders are one way of transmitting signals - but they are far
from the only way.
Markus Redeker
>So maybe my point 3) should be broken down further:
[...]
> 3c) Make an extensive analysis of Cook's tag system. At the very
> least it should make an interesting toy to play with, much as
> simple Turing Machine exercises play a role in computer science
> classes. Anyway, the Old Science demands a verification, peer
> review, evaluation, applications, etc. It will never make a
> practical computing system, no more than a Turing Machine
> would, but there should still be a lot of interesting games
> left in it.
> 3d) Rule 110 is nicely minimal, but are there other rules with
> similar properties? Turing Machine models have certainly been
> constructed; avoiding them was surely what the original inquiry
> meant by calling for "natural rules." Thanks to Cook's analysis,
> Tag Systems are also fair game. Can they be realized under other
> circumstances?
You have touched here something that interests me for a long time (and which
is one reason why I am interested in cellular automata): What kind of
computation is "natural" for a certain system. Cook's solution with tag
systems looks a bit forced; surely there must be some simpler method to do
computation with Rule 110.
In a way, computational universality is here a kind of red herring. The
Turing Machine gives us a good way to define computable _functions_ -- those
that can be computed by a Turing Machine -- but it doesn't say anything
about computing _systems_. Given a system, it would be interesting to know
which is the easiest way to use it for computation, in which way the input
data should be arranged in the system, how the behaviour of the system can
be described in terms of computation (where are the variables, where is the
program stored), etc.
[My original question about a "naturally occuring" CA rule was a bit
misguided. There can't be something like Rule 110 among the CAs with two
states, which was found after examining all 256 possible rules: A
corresponding search among the rule with 3 states and radius 1 would have to
consider 3^27 candidates!
Nevertheless, I am a bit disappointed that apparently nobody has studied one
of them in detail.]
McIntosh Harold V.
news:sokbid...@ID-219982.user.uni-berlin.de
> You have touched here something that interests me for a long time (and which
> is one reason why I am interested in cellular automata): What kind of
> computation is "natural" for a certain system. Cook's solution with tag
> systems looks a bit forced; surely there must be some simpler method to do
> computation with Rule 110.
I wish that were true; before Cook's solution became available we
invested
quite a bit of time trying to figure out how he did it. We have a
language
called REC (Regular Expression Compiler) which embodies about as simple
a
control structure as you can get. It looked for a while like the EBar -
C
collisions could be interpreted as functions working on arguments, but
the
main readon that didn't work out was that we couldn't see a way to get
parenthesis levels, and the necessary selective skipping to get to a
closing
parenthesis. Skipping backwards was no problem because the data could
be fed multiple copies of the program and it could wait until a new
version of an earliar program location showed up again.
Solitons are an essential ingredient in his construction, and it seems
to be an interesting question whether anyone noticed them and why not?
Setting up Rule 110 on the CAM/PC and letting it run, you can't avoid
them. But 1) you think of CAM/PC as being for two dimensional, not one
dimensional automata and 2) the one dimensional programs such as LCAU
were never let run long enough to get to the part where solitons
manifest.
CAM/PC was so fast and that was its nature, to run on and on, so that it
was just a matter of not applying it to Rule 110.
However, the attempt to design a computer, using Rule 110 or whatever
else,
runs contrary to the philosophy of choosing an automaton and letting it
run just to see what it will do. As I understand, Conway's discovery
that "Life is universal" fit in with the latter philosophy.
> [My original question about a "naturally occuring" CA rule was a bit
> misguided. There can't be something like Rule 110 among the CAs with two
> states, which was found after examining all 256 possible rules: A
> corresponding search among the rule with 3 states and radius 1 would have to
> consider 3^27 candidates!
I think there is a little distortion in this comment. Rule 110 >is< a
two
state automaton. What is for sure as that two state, two neighbor rules
aren't universal, they're just the sixteen Boolean functions of two
variables. Going to three states, there is an analogous algebra of
three-valued logics, but again, two neighbors is the starting point.
Actually, Rule 54 (among Wolfram's binary, first neighbor rules, shows
promise; it has lots of gliders and they are more manageable than for
Rule 110. (2 x 54 = 108, so it's slightly less than half as complicated
as Rule 110, if you like misplaced numerology). Work is still in
progress
however.
Anyway, I still think that Rule 110 hasn't been fully analyzed. And
except for explicit Turing Machine simulations by Alvy Ray Smith and
others, automata with more states of larger neighborhoods are largely
unexplored.
IzI
Have you tried to group all the rules of 2 or 3 neighbors and 3 states
into equivalent classes. I know that Harold tried, but did he finished
the job. Can anybody produce a table of the number of equivalent
classes depending on neighborhood size and number of states?
I am working on a method (algorithm, software) for counting equivalent
classes given the neighborhood size, number of states, number of
dimensions and the known simetries (permutation, reflection, rotation
in 2D, ...).
I am colecting literature at the moment, but I would welcome any help.
IzI
Tim Tyler
> Here is a question for both Marcus and and Harold
>
> Have you tried to group all the rules of 2 or 3 neighbors and 3 states
> into equivalent classes. I know that Harold tried, but did he finished
> the job. Can anybody produce a table of the number of equivalent
> classes depending on neighborhood size and number of states?
>
> I am working on a method (algorithm, software) for counting equivalent
> classes given the neighborhood size, number of states, number of
> dimensions and the known simetries (permutation, reflection, rotation
> in 2D, ...).
Equivalent in what sense?
McIntosh Harold V.
> Here is a question for both Marcus and and Harold
>
> Have you tried to group all the rules of 2 or 3 neighbors and 3
> states into equivalent classes?
This was a fairly ambitious project, depending on what is meant
by equivalence. At its simplest, Wolfram already considered
reflective symmetry and complementation symmetry; for his (2,1)
automata that meant four rules which differed only by reflection,
changing black for white, or both. For some highly symmetric
rules the classes were smaller. The concept generalizes readily,
for more states, and more dimensions. Reflections and rotations
of neighborhoods are possible, and may not change the rule.
Totalistic and semitotalistic rules are good starting examples
of such symmetries which can leave the rule invariant. Com-
plementation is a little harder, but in essence it is just a
permutation of states. For binary automata there is just one
non-trivial permutation, and that is complementation. So Wolfram
reduced 256 (2,1) automata to 58 symmetry classes, if I remember
the numbers correctly.
Wuensche, in his Atlas, made use of a futher symmetry, resulting
in what could be clusters. The automata of a cluster may look
quite different in their evolution, but they all obey the same
statistics. Variance, at least, is given by a sum of tensor
squares of the de Bruijn matrices, so operations which conserve
that particular sum of squares result in similar rules. The concept
is particularly useful when working with reversible automata. In
essence, a cluster results from composing an additional state
permutation with one of the Wolfram symmetries.
We did work out some lists of clusters for small automata; but the
lists grow rapidly - more or less exponentially, as do the total
number of rules - so the project was not pursued very far.
Wolfram also considered mappings between types of automata, as dod
Culick and others. A particularly good emulation is to create two
neighbors by assigning all the partial neighborhoods as states.
However, it seems rather hopeless to come up with something like the
classifacation of vector spaces according to dimension and field of
coefficients. What is a homomorphism? What is a normal subgroup, or
ideal, or whatever? Of course, automata are monoids, a la Eilenberg,
so the questions make sense. But I am still struggling to see the
reversible 4h automata as semigroups. Semigroups have been classified,
although the classification depends in turn on the classification of
groups themselves.
IzI
found in
http://www.cogs.susx.ac.uk/users/andywu/gdca.html
I will probably have to use some of the words in Harolds last paragraph
although I still have to learn what they mean (groups, semigroups,
homomorphism...).
The problem should have a combinatorial solution, my intention is to
only produce the number of equivalent classes when there are a lot of
rules and to list the rules in each class only when their number is not
too big.
I would like to observe symmetries in 2D and 3D. I tried to do some
paperwork but I got lost quickly with only 256 rules (2D, 3 cell
neighborhood), so I decided a software solution would be a better idea.
IzI
Tim Tyler
> For Tim, the explanation of equivalent classes and clusters can be
> found in
> http://www.cogs.susx.ac.uk/users/andywu/gdca.html
There are many ways of mapping the space of CA onto itself in ways
that preserve various properties.
You can permit - or deny - transformations that involve state space
rotation, state space permutation, spatial mirroring, spatial rotation,
temporal inversion - and so on.
Which properties you select as being important - and which properties
you regard as unimportant - determine which CA are considered to be
equivalent.
Markus Redeker
>The problem should have a combinatorial solution, my intention is to
>only produce the number of equivalent classes when there are a lot of
>rules and to list the rules in each class only when their number is not
>too big.
>I would like to observe symmetries in 2D and 3D. I tried to do some
>paperwork but I got lost quickly with only 256 rules (2D, 3 cell
>neighborhood), so I decided a software solution would be a better idea.
Could you explain in more detail what you did (or tried to do)? And what
kind of results do you want to get?
IzI
Here is again the link to the book "Global dynamics of CA" from
Wuensche and Lesser.
http://www.cogs.susx.ac.uk/users/andywu/gdca.html
A part of this book is dedicated to equivalence classes of binary
rules, it should be a good introduction.
My intention is to produce an automated software that would output the
number of equivalence classes for arbitrary CA parameters (number of
states per cell, neighborhood size, space symmetries (depend on the
number of dimension).
It is known that there are 88 equivalence classes (see book) for
boolean, three cell neighborhood CA (256 possible rules). Rules in the
same equivalence class behave identically (they are equivalent) so it
is enough to observe one rule in each equivalence class.
There are unsolved problems even for the above example, the reality is
that Weunuche missed some equivalence relations and there so there
should be fewer equivalence classes.
Equivalence is usually defined using equivalence relations. Two rules
are equivalent under spatial symmetry and permutation of symbols for
cell states ({0,1} ->{1,0}). A better definition would be the
equivalence of the basin of attraction, but this definition is not yet
useful for computation (nobody knows how to use it).
I will restart this discussion after some months when I get a better
insight into the problem.
IzI