Registered: Mar 2005
Posts: 2

I'm new to this world of Wolfram's CA and I found it very interesting, and a little bit difficult to understand in some cases.
In addition to that, books and references are hard to find at local libraries.

Here are my questions:
Given any Wolfram's Cellular Automata is there a way to find a function f(n) to determine the n-state of that CA in one simple step?

Ok, I've seen that it's possible, but not in all 256 cases (rules). Does anyone know in which cases it would work and why?

Regards,
Miguel

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

It is a fine question. The answer to it starts here - 615. Read right through to 620.

The basic story is that one can set up general schemes that assign a proper formula for the outcome of a CA's evolution for some number of steps. But the logical expressions that result get complicated very fast, for (most of) the complicated looking CAs. You effectively still need to calculate the intervening steps, or a piece of logic just as complicated. No significant compression of the calculative difficulty is achieved this way, when the rule generally shows complex behavior.

There are cases where some regularity in the rule allows one to find a simple formula that tells you the result at step n, without calculating all the intermediate steps to find the solution. This is obvious in simple cases like rules that immediately go to one color, or that alternate, or lay down repetitive patterns in space and time combined.

We call these cases of computational reducibility. The diagnosis is that much of the "effort" involved in updating the CA sequentially, according to its rules, is "wasted" or "redundant" computational effort. You can look at this as lots of cancelling going on in any general scheme representation for those rules.

And it can also happen when the behavior looks complicated from random initials, but shows structure from simple ones. The classic case is rule 90, which is an additive rule. Effectively, information passes through anything else without interference - the effect on a cell t steps later can therefore be found from a t0 step with some modded sum across t0. Rules of this type display a fractal structure from simple initials. The 2n th step on every other square (from a single cell) has to be the same as the nth step on every square. Results from more complicated initials are mod-additive superpositions of the results from simple ones.

That is about as complicated as it gets (though one can make that harder to deal with in practice by increasing the number of colors etc) such that a simple formula can still be found. Beyond that, with real instrinsic randomness generation (e.g. rule 30) or localized structures dependent on details of the initial condition and provable "programmable" (like rule 110), no such reducibility is to be expected.

You can view a CA rule as a mapping from the number its state would represent taken as a digit sequence, and another such number, aka as in iterated map. There are some connections to continuous maps on cantor sets in the infinite size limit. See notes on 869 (Mathematical interpretation of cellular automata) and 959 (Nested structure of attractors). As a representation, it is fine, and it may aid intuition to look at them that way. (E.g. the symmetry of rule 90 as an iterated map is readily apparent). The complexity is there in any representation, though, for the complicated rules. I doubt anyone expects to find one set of explicit and simple formulas for general continuous maps on Cantor sets.

How common reducibility is in CAs is a classic question in NKS. All the class 1s and 2s are reducible. Proofs of universality in the infinite size limit for some class 4s lead most people working in NKS to believe reducibility will prove impossible for all the 4s - although classes of initial conditions, finite widths, lossy mappings of microstate features (e.g. overall statistical behavior) and the like may still allow one to say something about their evolution, in restricted cases or aspects.

Most think the class 3s are in general irreducible. Whether they are also universal in the infinite size limit is the open problem I call "the class 3 problem". Essentially that is the question whether irreducibility and universality are two aspects of the same thing, in practice (with allowance for a logical distinction between them, occasional exceptions, etc).

There is a different problem which I call the problem of the "crackables", which is effectively, how far does reducibility extend into what at first looks like class 3 behavior. Rule 90 nesting, for example, is reducible. From random initials it looks as complicated as rule 30 - and the initial CA classification scheme was based on typical behavior from random initials. One can look at 90 as a marginal case of 2-ness - if one wants the 2-3 divide to track reducible-irreducible, as a distinction. Or one can regard it as a "crack" (as in, cracking a safe) - an apparently complicated behavior that can be solved.

Other examples that support the intuition that maybe there are more crackables out there, some distance into the 3s as it were, comes from cases like the digits of 3^n in base 2, where there is a simple formula, but the behavior looks quite complicated. Or the fact that some things look less complicated in a different representation (e.g. there are numbers with complicated digit sequences but simple continued fraction representations). A formula can take a lot of computational effort to work out, for high n. But often there are shortcuts possible when one has such a formula.

When investigating a class of systems one should be interested in the onset of complexity. Before the system has this much going on, it behaves simply. After it has all this, it can show complexity. OK, focus on the cases that are transitional in how much they have going on. Zoom in on the line between them, as it were. As you approach the edge of simple behavior, you should expect to find some "cracks". That is, the first few cases that look complicated, may in fact have some trick to them, that allows you to reduce them to a simple formula or procedure. You want to solve these because they aren't yet true complexity. Then you marginally complicate the set up (colors, range, whatever). You quickly find ones you can't crack. Is it because there isn't one, or because you haven't seen the trick?

Personally, I think the cracks are a small special case just into the 3s. But it is an open question, how fast they really give out, or what portion of things that look like 3s actually have hard to find reductions. Nothing like all of them, it is pretty clear. But maybe some appreciable fraction have them, just getting harder and harder for us to find. That is what I call the "crackables" question.

I hope this is interesting.

Report this post to a moderator | IP: Logged

Registered: Mar 2005
Posts: 2

Thanks for your quick response. Your answer was clear and helped me a lot.
Regards,
Miguel

Report this post to a moderator | IP: Logged

Registered: Feb 2005
Posts: 2

I have one for you, assuming you know boolean algebra.

code:

f(R,I)={

    (R[0](I[0]I[1]I[2]))+
    (R[1](I[0]I[1]~I[2]))+
    (R[2](I[0]~I[1]I[2]))+
    (R[3](I[0]~I[1]~I[2]))+
    (R[4](~I[0]I[1]I[2]))+
    (R[5](~I[0]I[1]~I[2]))+
    (R[6](~I[0]~I[1]I[2]))+
    (R[7](~I[0]~I[1]~I[2]))}

Where R is the 8-bit rule and I is the 3-bit input (for 1-dimensional cellular automata).

__________________
I feel... Accelerated

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

Sure, but the whole array isn't 3 bits and isn't deciding what value to give to one cell. It is n cells wide and updates all n cells (if the boundary wraps, at any rate - otherwise you import zeros from the edges or some such). What is wanted is a general formula for the 200th line from only the first, where e.g. both input and output are 100 digit binary numbers.


f[{0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 
1, 0, 1, 0,0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 
1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 
1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 
1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1},200] =

{1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 
0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1,
1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0,
1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0,
1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1}


Can one find a simple form of f that does this easily, even for a single complicated rule (say 30, or 110), and for all t (200 in the example)?

(Of course, f is actually -


Last[CellularAutomaton[30, #1, #2]]&


As you can verify with

start = {0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 
1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 
0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 
1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1,
1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1}

Last[CellularAutomaton[30, #1, #2]] &
@@{start,200}

A Mathematica function, rather than a mathematical one.

In the straightforward sequential implimentation, the local neighborhood function is mapped over a moving partition of the first line, and then the whole resulting function is nested 200 pairs of parentheses deep. A computer can work that out for you, but it involves a large amount of computational work. Can one find lots of cancellations and remove parentheses easily and reduce the whole mass of logic operations to a short formula? Answer, with simple behavior rules yes, but in general no.

Report this post to a moderator | IP: Logged