Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

50 views

Skip to first unread message

Nov 12, 2003, 6:38:39â€¯AM11/12/03

to

While writing the FAQ entry at:

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.

Nov 12, 2003, 2:28:57â€¯PM11/12/03

to

Tim Tyler <t...@tt1lock.org> wrote in message news:<Ho8Lo...@bath.ac.uk>...

> ``[...] 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.''

> ``[...] 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

Nov 12, 2003, 2:36:17â€¯PM11/12/03

to

In article <eppstein-1B8A11...@news.service.uci.edu>,

David Eppstein <epps...@ics.uci.edu> wrote:

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

Nov 12, 2003, 2:35:00â€¯PM11/12/03

to

In article <cf89d01f.03111...@posting.google.com>,

ta...@dpir.com (Siamak) wrote:

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.

Nov 13, 2003, 5:46:04â€¯PM11/13/03

to

>

> 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.

>

> 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.

Nov 13, 2003, 6:46:03â€¯PM11/13/03

to

"Jochen Fromm" <Jochen...@t-online.de> wrote in message

news:bp118n$1ikkoi$1...@ID-177680.news.uni-berlin.de

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

Nov 14, 2003, 9:46:47â€¯AM11/14/03

to

Wolfram's Book is not the Bible. CA are not

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)

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.

Nov 14, 2003, 11:14:36â€¯AM11/14/03

to

In article <bp2phm$1iupsb$1...@ID-177680.news.uni-berlin.de>,

"Jochen Fromm" <Jochen...@t-online.de> wrote:

"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.

Nov 14, 2003, 2:40:50â€¯PM11/14/03

to

"Jochen Fromm" wrote:

> Wolfram's Book is not the Bible.

> 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

Nov 15, 2003, 10:49:05â€¯AM11/15/03

to

Why not simply categorize 2D CA by the types of objects that they

support. Namely:

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?

Nov 15, 2003, 12:06:18â€¯PM11/15/03

to

Brian Prentice <bpre...@webenet.net> wrote or quoted:

> 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.

Nov 21, 2003, 9:48:32â€¯AM11/21/03

to

"Jochen Fromm" <Jochen...@t-online.de> wrote in message

news:bp2phm$1iupsb$1...@ID-177680.news.uni-berlin.de...[...]

> 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

Nov 21, 2003, 12:03:26â€¯PM11/21/03

to

Is this a 2D example?

#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:

Nov 21, 2003, 12:18:13â€¯PM11/21/03

to

In article <28cff77f.03112...@posting.google.com>,

bpre...@webenet.net (Brian Prentice) wrote:

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?

Nov 21, 2003, 4:25:50â€¯PM11/21/03

to

>

> I don't follow you there.

> By definition any "real world" computation can be set up in such a case.

>

> G. Waleed Kavalec

>

> 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 ?

Nov 21, 2003, 6:06:36â€¯PM11/21/03

to

> Example of what?

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.

Nov 23, 2003, 6:02:57â€¯AM11/23/03

to

"Jochen Fromm" <Jochen...@t-online.de> wrote:

> 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.

Nov 23, 2003, 6:09:57â€¯AM11/23/03

to

"Brian Prentice" <bpre...@webenet.net> wrote:

>> 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.

Nov 23, 2003, 10:41:05â€¯AM11/23/03

to

For those of you who are interested, have access to a windows

computer and are willing to blow the dust off it, I have updated the

zip file at:

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.

Nov 24, 2003, 2:37:09â€¯AM11/24/03

to

"Jochen Fromm" wrote:

> 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.

This is in common with all other universal models of computation such> 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,

Nov 26, 2003, 3:10:55â€¯PM11/26/03

to

>

> This is in common with all other universal models of computation such

> as Turing machines and RAM machines. [..]> 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.

Nov 26, 2003, 4:39:34â€¯PM11/26/03

to

Jochen Fromm <Jochen...@t-online.de> wrote or quoted:

> 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.

Nov 26, 2003, 4:42:36â€¯PM11/26/03

to

Jochen Fromm <Jochen...@t-online.de> wrote or quoted:

> 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.

Nov 28, 2003, 7:30:06â€¯PM11/28/03

to

In article <HozAt...@bath.ac.uk>, Tim Tyler <t...@tt1lock.org> wrote:

> 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

Nov 29, 2003, 6:40:51â€¯AM11/29/03

to

David Eppstein wrote:

> 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 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.

Nov 29, 2003, 8:59:33â€¯AM11/29/03

to

Siamak <ta...@dpir.com> wrote or quoted:

> David Eppstein wrote:

> 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.

Nov 29, 2003, 11:26:38â€¯AM11/29/03

to

"Tim Tyler" <seem...@cyberspace.org> wrote in message

news:bqa8o5$20hsgn$2...@ID-99702.news.uni-berlin.de

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!

Nov 30, 2003, 3:40:20â€¯AM11/30/03

to

Tim Tyler 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.

> 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.

Dec 2, 2003, 6:53:47â€¯AM12/2/03

to

Is there still an Eppstein CA classification scheme?

If there is:

What are the categories?

What can be said about the rules in each category?

Dec 2, 2003, 8:55:56â€¯AM12/2/03

to

Brian Prentice <bpre...@webenet.net> wrote or quoted:

> Is there still an Eppstein CA classification scheme?

See the bottom of:

http://www.ics.uci.edu/~eppstein/ca/wolfram.html

0 new messages

Search

Clear search

Close search

Google apps

Main menu