A problem with Eppstein's CA classification scheme
Tim Tyler
http://nojava.cafaq.com/classify/?open=eppstein
...I noticed that there seems to be a problem with David Eppstein's
CA classification scheme.
Recall, Eppstein's CA classification scheme is described at:
http://www.ics.uci.edu/~eppstein/ca/wolfram.html
There are basically four categories:
1. All patterns expand;
2. No pattern expands;
3. No pattern contracts;
4. Both expansion and contraction possible;
Eppstein writes of category 3:
``If a rule (such as B378/S012345678 above) includes S01234,
the bounding box of a pattern can never shrink, no gliders
exist, and the rule is not universal. A similar phenomenon
happens with rules involving B23/S0, such as the first entry
in the table above.''
However - I note:
``[...] it appears that there may be a problem with Eppstein's
classification scheme as well.
Some 1D rules are universal. A 2D temporal plot of the history of their
evolution is also a CA - and is also universal. However, a 2D temporal
plot of the evolution of a 1D CA apparently fulfills the "no pattern
contracts" condition above - since cells are only ever added.
This suggests that the description of these rules as not being universal
is mistaken. While they can not contain gliders, they /can/ still
contain ladders and other "pseudo-propagating" structures that
are capable of doing the same job.''
In other words, not shrinking is not enough to prevent universal
computation from occurring. A ball of CA-stuff can continuously
expand - and never delete a single cell - while still managing to
perform calculations on its outer surface.
I believe Eppstein's CA classification scheme is in need of
adjustment to take account of this fact.
--
__________
|im |yler http://timtyler.org/ t...@tt1lock.org Remove lock to reply.
Siamak
> ``[...] it appears that there may be a problem with Eppstein's
> classification scheme as well.
>
> Some 1D rules are universal. A 2D temporal plot of the history of their
> evolution is also a CA - and is also universal. However, a 2D temporal
> plot of the evolution of a 1D CA apparently fulfills the "no pattern
> contracts" condition above - since cells are only ever added.
>
> This suggests that the description of these rules as not being universal
> is mistaken. While they can not contain gliders, they /can/ still
> contain ladders and other "pseudo-propagating" structures that
> are capable of doing the same job.''
Whether a CA is capable of universal computation depends on how do we
expect to see the result of computation on a CA. That is, it depends
on how much powerful is the OBSERVER --- whether it can recognizes the
result of computation in a (possibly complex, padded) configuration
(or sequence of configurations).
As an exaggerating example, suppose the observer has an overkilling
ability of seeing the density at t=\infty of the cells containing 1.
Then one can design a CA that computes incomputable functions.
I believe D. Eppstein has had a special (probably not enough general)
notion of how should the result of computation be seen, in his mind;
i.e. he's supposed that the result of computation should appear in a
"pre-specified" region of the lattice.
Siamak
David Eppstein
David Eppstein <epps...@ics.uci.edu> wrote:
> What I actually originally wrote was that the question of whether a
> pattern lives or dies can not be universal in an always-expanding rule.
> This is true, but as Tim points out there are other questions than
> life-or-desk that you could ask about the evolution of a pattern, so
> these rules can be universal in other ways. I've updated my page to
> include Tim's observation, with a pointer to this thread.
Sorry for the interesting typo. That should be life-or-death, obviously.
--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science
David Eppstein
ta...@dpir.com (Siamak) wrote:
> I believe D. Eppstein has had a special (probably not enough general)
> notion of how should the result of computation be seen, in his mind;
> i.e. he's supposed that the result of computation should appear in a
> "pre-specified" region of the lattice.
What I actually originally wrote was that the question of whether a
pattern lives or dies can not be universal in an always-expanding rule.
This is true, but as Tim points out there are other questions than
life-or-desk that you could ask about the evolution of a pattern, so
these rules can be universal in other ways. I've updated my page to
include Tim's observation, with a pointer to this thread.
But I think it's important that the notion of the result of the
computation should be well specified. If you're vague on this point,
then you can hide too much of the computational complexity in the
question you're asking instead of in the actual behavior of the CA.
Jochen Fromm
> But I think it's important that the notion of the result of the
> computation should be well specified. If you're vague on this point,
> then you can hide too much of the computational complexity in the
> question you're asking instead of in the actual behavior of the CA.
>
My personal impression is this : Stephen Wolfram's Class IV
automata are not capable of universal computation at all.
Melanie Mitchell, Jim Crutchfield et al. have tried to
perform calculation with CA at 'the edge of chaos' with
negative results. See
http://www.santafe.edu/projects/evca/Papers/papers.html
One flaw of cellular automata is : automata with stable
patterns (Class I & II) are simple and boring, automata
with interesting behavior (Class III & IV) show complex
but unstable or short-lived patterns. Complex patterns
appear *and* disappear rapidly. It is similar to the
uncertainty relation in Quantum Mechanics : the more
complex the pattern is, the faster it disappears again.
According to your new classification, the interesting
but short-lived behavior appears in the class "Both
expansion and contraction possible".
Simple CA are not able to simulate the behavior of
complex *and* stable systems, only either complex
or stable systems. Cellular automata are closed systems,
and similar to isolated systems in thermodynamics, in
which disorder and entropy can not decrease, there is no
evolution to higher forms of complexity possible.
It would be interesting to study or construct some
kind of open CA, with a continuous pump-in and
pump-out of energy or information.
By the way, I think the new classification is interesting,
because it has some similarities with the stretching and
folding process in strange attractors.
McIntosh Harold V.
news:bp118n$1ikkoi$1...@ID-177680.news.uni-berlin.de
> My personal impression is this : Stephen Wolfram's Class IV
> automata are not capable of universal computation at all.
Isn't it true that Wolfram, in his recent ANKOS, goes to
considerable effort to claim the contrary?
> Melanie Mitchell, Jim Crutchfield et al. have tried to
> perform calculation with CA at 'the edge of chaos' with
> negative results. See
> http://www.santafe.edu/projects/evca/Papers/papers.html
It seems to me that they were mainly interested in
information flow, which isn't necessarily the same thing
as computation.
> [...]
> By the way, I think the new classification is interesting,
> because it has some similarities with the stretching and
> folding process in strange attractors.
Didn't Wolfram state, or at least imply, that his scheme of
classification was modelled on the hierarchy to be found in
dynamical systems? He began his work around the time that
Stephen Smale was promoting the "strange attractors." Up
until then fixed points and limit cycles were the norm,
although Poincare knew about more complicated alternatives
long before.
The original contention in this thread seems to me to be
quite valid; that to recognize a computation, you have to
know what you are looking for.
- hvm
--
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG
Jochen Fromm
new, and there are other good books about CA
( for example "Cellular Automata", Andrew Ilachinski,
World Scientific, 2001 )
Even if he proves that Class IV automata are capable
of universal computation (I haven't read the
corresponding part of the book in detail, it
is more than 1000 pages long)
a) he can be wrong
b) you can calculate nothing *concrete*
with CA capable of *universal*
computation
CA produce beautiful patterns, but they
are not good in solving mathematical or
algorithmic problems. It is hard to find the
solution for a complex differential equation
or a geometric problem with a CA. All they can
do is produce typical CA patterns.
A class I or II automata does not calculate
or computate anything. It shows always the
same pattern. A class III automata is chaotic,
with random output patterns. A class IV automata
shows complex patterns, but you can not predict
what the output is in 100, 200 or 300 time steps
ahead. A computation where you can not predict
the result is for me a strange kind of computation.
People have speculated that the complex interactions
of Class IV automata *could* support complex information
processing or even universal computation. Chris
Langton speculates in his article "Life at the Edge
of Chaos" (Artificial Life II, Addison-Wesley, 1992)
if CA could be a universal computing device.
His article is great, but the part about computation
is not convincing. It was only a (bad) speculation.
Yes, Steven Wolfram has formulated his four classes
as an analogy to the behavior of dynamical systems.
Class I CA evolve to *limit points*
Class II CA evolve to *limit cycles*
Class III CA evolve to *chaotic* behavior
execpt
Class IV CA, which have very long transients, but no direct
analog among dynamical systems.
Both CA and dynamical systems show complex
behavior. The complexity in both cases originates in
stretching and folding processes (or merging and
splitting of components). So I think David Eppsteins
classification scheme in terms of expansion and
contraction is maybe the better choice, because
it is closer to the mechanism which creates
complexity, whereas Wolfram's classic scheme
is closer to observed phenomena.
David Eppstein
"Jochen Fromm" <Jochen...@t-online.de> wrote:
> A class III automata is chaotic,
> with random output patterns.
Actually, this part is my biggest complaint about Wolfram's
classification -- it's based on random fields. Class III produce random
output patterns if you start with random input patterns. If you start
with something highly structured, it can stay structured and perform
universal computations. E.g. see
http://www.ics.uci.edu/~eppstein/ca/b35s236/
for a description of patterns capable of universal computation in a rule
in which random fields stay random looking.
Siamak
> Wolfram's Book is not the Bible.
Agree... though I've seen neighter. ;-)
> CA produce beautiful patterns, but they
> are not good in solving mathematical or
> algorithmic problems. It is hard to find the
> solution for a complex differential equation
> or a geometric problem with a CA. All they can
> do is produce typical CA patterns.
I'm afraid you've totally misunderstood.
A quote from 2500 years ago:
``Let no one ignorant of geometry enter
within these walls'', Plato
Just kidding of course! All discussions with regard to the CAs are
welcome here.:)
> A class IV automata
> shows complex patterns, but you can not predict
> what the output is in 100, 200 or 300 time steps
> ahead. A computation where you can not predict
> the result is for me a strange kind of computation.
A computation where you can predict the result is actually worthless,
since you know the result beforehand.
best,
Siamak
Brian Prentice
support. Namely:
Oscillators
Ships
Guns
Puffers
Replicators
Stretchers
And then perhaps, subdivide these. For example:
Ships
Orthogonal Ships where (dx = 0) or (dy = 0)
Diagonal Ships where abs(dx) = abs(dy)
Knight Ships where abs(dx) <> abs(dy)
Puffers
Generates Oscillators
Generates Ships
And then ask questions such as:
What are the fundamental rhythms that a rule possesses that cause it
to support some of these objects and not others?
Tim Tyler
> Why not simply categorize 2D CA by the types of objects that they
> support. Namely:
>
> Oscillators
> Ships
> Guns
> Puffers
> Replicators
> Stretchers
>
> And then perhaps, subdivide these.
The existing classification schemes tend to be such that
rules can be assigned automatically to one or other of
the categories by an unintelligent computer program.
These classification schemes are mostly "well-defined" -
and you don't wind up with the situation of classifying
a CA as gliderless and then have to reclassify it later
when someone finds a glider.
G. Waleed Kavalec
[...]
> b) you can calculate nothing *concrete*
> with CA capable of *universal*
> computation
I don't follow you there.
By definition any "real world" computation can be set up in such a case.
G. Waleed Kavalec
Brian Prentice
#MCell 4.20
#GAME User DLL
#RULE InteractingStates2,S1;X ,S2;X ,S3; ,S4;,S5;
#RULE ,S6; ,S7; ,S8; ,C1; XXX XX,C2;X X
#RULE ,C3; ,C4; ,C5; ,C6; ,C7;,C8;
#BOARD 400x400
#WRAP 1
#CCOLORS 9
#L AA
The DLL required to run this pattern is here:
David Eppstein
bpre...@webenet.net (Brian Prentice) wrote:
> Is this a 2D example?
Example of what?
Is it possible for you to post such patterns in a way that allows
non-Windows-users to view them?
Jochen Fromm
> I don't follow you there.
> By definition any "real world" computation can be set up in such a case.
>
> G. Waleed Kavalec
>
I said you can calculate nothing *concrete*
with a CA capable of *universal* computation,
because it may take an infinite amount
of work, time and memory to do it.
You can in fact simulate a very simple and primitive
kind of "universal" computer with special structures
like spaceships, "p68 oscillators" and gliders. This
is possible, but such a simulated computer would
be awfully slow. And I doubt you can do anthing useful
with it. With a universal computer you can in principle
simulate anything, but it may take an infinite amount of
time and memory.
I'm still thinking about Wolfram's and Eppstein's
classification schemes. Consider for example the
different 1-dimensional CA applet at
http://www.sussex.ac.uk/space-science/ca.html
2-dimensional CA (Game of Life, etc.) can also
be found at the site. The only negative point is
that the site may take some time to load.
How do you formulate Rule 30 and Rule 110
http://mathworld.wolfram.com/Rule30.html
http://mathworld.wolfram.com/Rule110.htm
in terms of expanding and contracting patterns ?
Hmm. Pure black, extended patterns collapse and
are replaced by a white pattern except the left and
right edges, which stay black ??
Anyway, there is another problem. If you look at
all the different 1-dimensional rules, you can not
see a clear distinction between Class II and Class IV
rules, or between Class III and Class IV rules.
Some rules depend on initial conditions,
other don't. Rules 18,22,54,60,62 (118), 122 (126)
have a regular, fractal structure (for example a
Sierpinksi Triangle) with single point default
conditions and a chaotic structure for random
starting conditions. What class are they,
class II (regular, periodic) or class III (chaotic) ?
Rule with propagating lines or structures
(rule 9,10,11,25,41,106,107,..) look also different
for single point starting conditions and random point
starting conditions. The "propagation structure" is
multiplied or replicated. Are they class II or
class IV ?
Rule 62 (or 118) looks for single point starting
conditions like Class II, for random conditions like
Class IV ??
The interesting rules that produces chaotic or
random behavior (Rule 30,45,75,110) seem to be
independent from the initial conditions. They always
produce the same triangle pattern. If they are independent
from the initial pattern, a structured input should be
destroyed or dissolved. But David Eppstein said
"Class III produce random output patterns if you
start with random input patterns. If you start
with something highly structured, it can stay
structured and perform universal computations
[..] random fields stay random looking".
I am a bit irritated and confused. Is here
an expert about CA who can explain this ?
Perhaps Tim Tyler ?
Brian Prentice
An example of a rule that does not support contraction but does
support 'life' like patterns including the period 4 glider.
> Is it possible for you to post such patterns in a way that allows
> non-Windows-users to view them?
No, I use MCell almost exclusively and my patterns usually require
DLL extensions to that program. I always include the DLL source code
however.
Kent Paul Dolan
> I said you can calculate nothing *concrete*
> with a CA capable of *universal* computation,
> because it may take an infinite amount
> of work, time and memory to do it.
Umm, from non-expert me, that looks like a really
bad misuse of "infinite", or you're muddling in
the halting problem, which exists for plain vanilla
Turing machines, or you're simply misunderstanding
what is meant by "universal computation capability".
Turing machines aren't famous for blinding speed
compared to RAMs, either.
xanthian, more than likely to be proved incorrect.
Kent Paul Dolan
>> Is it possible for you to post such patterns in a way that allows
>> non-Windows-users to view them?
> No, I use MCell almost exclusively and my patterns usually require
> DLL extensions to that program. I always include the DLL source code
> however.
Fair call; near any Really Useful(*) computer, there is nearly bound
to be some MS-Windows computer gathering dust. <grin>
xanthian, being a brat again(**).
(*) courtesy Thomas the Tank Engine.
(**) Oh, how I wish mailgate supported crossposts to
alt.destroy.microsoft ; I suppose that's an example
of some benign spirit trying desperately to save me
from myself.
Brian Prentice
computer and are willing to blow the dust off it, I have updated the
zip file at:
http://linuxenvy.com/bprentice/MCell/IS2.zip
The file contains a new version of the DLL together with some example
patterns which use rules in Eppstein's category 3. One of these
patterns shows Life's original glider gun operating on an expanding
background.
Siamak
> I said you can calculate nothing *concrete*
> with a CA capable of *universal* computation,
> because it may take an infinite amount
> of work, time and memory to do it.
as Turing machines and RAM machines. Nonethelss, it is not clear what
you mean by concrete.
Note that using gliders and spaceships, and ... to simulate a computer
is only one of a kind to compute with CAs. It is more likely that one
uses this kind of universality to show that a *specific* CA rule may
has a quite complicated and unpredictable behavior; actually not do
real-world computation.
But neat and efficient rules can be run on CA machines. You should not
expect to run a PC-optimized database program efficiently on a CA
machine.
cheers,
Jochen Fromm
> This is in common with all other universal models of computation such
> But neat and efficient rules can be run on CA machines. You should not
> expect to run a PC-optimized database program efficiently on a CA
> machine.
>
Yes, of course you are right. "Universal computation" sounds
very powerful - as if you can do anything with it. But in fact you
have to pay a high price for it : slow speed or large memory.
However, I am more interested in the classification question.
Wolfram's classification seems to be very coarse. The same
patterns look as if they were in different classes for different initial
conditions.
Eppstein's classification uses the notions "expanding" and
"contracting". I wonder how you can classify simple 1-dimensional
CA in terms of expanding and contracting patterns ?
It seems to be difficult.
Tim Tyler
> Eppstein's classification uses the notions "expanding" and
> "contracting". I wonder how you can classify simple 1-dimensional
> CA in terms of expanding and contracting patterns ?
> It seems to be difficult.
The categories could do with being formally being pinned
down - in a manner that does not depend on the size of the
neighbourhood, the dimensionality of the space, a
totalitarian rule - etc.
Clearly it is assumed that there is a single, known
"background" state.
From the context, it is clear that "expand" and "contract"
don't refer to states where the total number of cells
increases or decreases.
Rather, a classification that allows you to go directly from
the rule to the category is being propesed.
There are currently three categories listed:
My attempt to generalise them follows:
1. All patterns expand, or no patterns contract.
No cells move from non-zero to zero;
Some cells move from zero to non-zero;
[some other conditions?];
2. Patterns can contract, but not expand.
No cells move from zero to non-zero;
Some cells move from non-zero to zero;
3. Both expansion and contraction possible.
[not in either category 1. or 2.]
As you can see, I have failed to find a way of
expressing the "All patterns expand..." condition
in a manner which can be neatly expressed in
terms of the properties of the rule. It seems
like a tricky problem.
However, maybe I should forget about the
"All patterns expand" bit - and merely write:
...
1. No patterns contract.
No cells move from non-zero to zero;
Then it seems that the scheme would be perfectly well-defined.
I suggest dropping the second condition from 2 (or adding
the equivalent to 1) - for the sake of neatness.
As far as I am concerned, the classification scheme's good
point is that we can say that finite regions in category 2
schemes are not capable of computing universal functions -
since they have no access to an unlimited memory store - and
are confined to a region.
I think there is still considerable scope for a
classification scheme that is of some greater
utility in attempting to identify which automata
are capable of universal computation.
As far as I can see, such a scheme should probably look
something like this:
1. Linear - no linear CA can perform computations;
2. Quasi-linear - there's a whole class of "quasi-linear"
automata which are proven non-universal - including rule 18 [1]
3. Non-linear - not linear or quasi-linear - may be capable of
universal computation.
[1]''Predicting Non-linear Cellular Automata Quickly
by Decomposing Them into Linear Ones''
- http://www.santafe.edu/~moore/pubs/semi.html
...has more details about this.
This category may need more pinning down.
Tim Tyler
> Wolfram's classification seems to be very coarse. The same
> patterns look as if they were in different classes for different initial
> conditions.
It is assumed you use "sufficiently large" random blobs to test with.
That way the chances of different trials producing different results is
usually rather small.
David Eppstein
> Clearly it is assumed that there is a single, known
> "background" state.
I think more generally the background should be allowed to be any
repeating pattern, not just a single state. Otherwise you wouldn't be
able to say much about rule 110... But you need to have some way of
restricting the "interesting" part of the pattern to a finite number of
cells, if you want to talk about Turing-completeness, since otherwise
you couldn't simulate the CA on a Turing machine.
I've been experimenting for a while with rules involving B0, which at
first seem to fit the "always-expanding" class, but not if you use a
background of all live cells (for rules with S8) or a background that
alternates between all live and all dead (for rules without S8). There
are a lot of interesting patterns in the alternating-background rules
that I wouldn't have discovered without the right assumption about the
background, e.g.
http://www.ics.uci.edu/~eppstein/ca/replicators/b01367s012.html
Siamak
> I think more generally the background should be allowed to be any
> repeating pattern, not just a single state. Otherwise you wouldn't be
> able to say much about rule 110... But you need to have some way of
> restricting the "interesting" part of the pattern to a finite number of
> cells, if you want to talk about Turing-completeness, since otherwise
> you couldn't simulate the CA on a Turing machine.
>
It would be good for a classification, to put the isomorph rules in
the same classes.
The isomorphism can be considered in the sense that some bijection
maps the space-time blocks of one CA to the space-time blocks of the
other.
Tim Tyler
> David Eppstein wrote:
You refer - I presume - to the fact that these "tiled" and
"periodic background" CAs are isomorphic to other CAs with
a uniform background - but a larger neighbourhood.
McIntosh Harold V.
news:bqa8o5$20hsgn$2...@ID-99702.news.uni-berlin.de
The nesting of these quotes is getting a bit deep, but let's look all
the
way back. The tiling background in Rule 110 is important for its
operation
just as it is in other automata such as WireWorld. But you don't
necessarily
have to copy the whole background into a Turing maching to close a cycle
of emulation. Once the rules for glider collisions have been given for
Rule 110, and it has been verified that they are a complete and accurate
set, the automaton lattice can be set aside and further calculations
need
only deal with the abstraction. In WireWorld, once the equivalence to
wiring diagrams has been established, you only need to know that you can
realize each diagram as it is needed.
Otherwise, presumably you could program the emulation to add new cells
as required, just as Turing's machine can call fom more tape as
required.
An alternative approach to Rule 110 would be to treat the space-time
evolution of Rule 110 as a two-dimensional Shift of Finite Type, making
explicit use of the tiling which it generates. Unfortunately this kind
of
dynamical system seems to be quite complicated, and there seems to be
scarce literature devoted to it. One question which could be asked, is
whether Cook's gliders account for all the possibilities? A tiling
approach assigns A and B gliders maximum velocities, and establishes a
gap between A and D. Is there a similar gap between C and D?
It is also an interesting question as to whether the tiling is essential
to the operation of Rule 110. It readily exhibits tiles, but do other
rules also define good tilings? This is relevant to the last question
raised, as to whether a larger background could also be simpler. In
this regard, Andrew Wuensche's Discrete Dynamics Lab contains some
interesting filtering capabilities which serve to isolate glider-like
structures in otherwise more chaotic backgrounds. This in turn relates
to some other interesting studies, and also to Wolfram's claims that
there are vestiges of Rule 110 embedded in many (most?) other automata.
But if this kind of thinking goes on, you begin to see Turing Machines
lurking everywhere, even in bird songs and babbling brooks!
Siamak
> You refer - I presume - to the fact that these "tiled" and
> "periodic background" CAs are isomorphic to other CAs with
> a uniform background - but a larger neighbourhood.
Exactly! Though there is no need for larger neighborhood if we allow
the "tiles" to have a time component. This has an advantage to include
the background patterns periodic in time as well as those periodic in
space.
Brian Prentice
If there is:
What are the categories?
What can be said about the rules in each category?
Tim Tyler
> Is there still an Eppstein CA classification scheme?
See the bottom of:
http://www.ics.uci.edu/~eppstein/ca/wolfram.html