Jason Cawley
Wolfram Science Group
Phoenix, AZ USA
Registered: Aug 2003
Posts: 712 |
First a minor technical forum point - we have provided a set of special tags to refer to pages of the NKS book, square brackets containing the letters pg, with the usual / slash in the trailing instance to close the tag. A number contained within those will be interpreted as a link to the corresponding page of NKS Online. This is just a convenience to shorten links that reference the book. Now to the content of your post.
Of course Wolfram has looked at multiple color CAs. You can find the dicussion of them starting on page 60, and continuing through page 70. As he notes, there are 7.6 trillion general 3 color rules, too large a space to span exhaustively, but simple enough to sample randomly. In that section of the book, Wolfram considers a simplified slice of 3 color rules in the form of totalistic rules. Those add the states of cells in their neighborhood, effectively treating each cell equally. Since each cell ranges from 0 to 2, the total ranges from 0 to 6, or 7 possibilities. There are thus 3^7 or 2187 rules of this type, and Wolfram shows a number of them that make interesting structures.
Before jumping to the whole 3^3^3 space of general rules, one can also consider outer totalistic rules. The idea is the same as the previous, but this time the center cell is allowed to matter independently. The possibilities are therefore 0-2 for the center cell times 0-4 for the outer total, or a total of 15 cases. There are 3^15 or 14.3 million rules of this type. The built in CellularAutomaton function in Mathematica will generate any of these, any number of colors, and higher dimensions. To look at a sample of general range 3 rules, for example, you only have to type -
somerulenumbers = Table[Random[Integer, 3^3^3 - 1], {96}];
Show[GraphicsArray[Partition[Table[ArrayPlot[
CellularAutomaton[{somerulenumbers[[i]], 3, 1},
{{1}, 0}, 20, {All, All}],
DisplayFunction -> Identity],
{i, 1, 96}], 8],
ImageSize -> 1200]]
I'll explain those lines. The first just generates a sample of 96 random numbers up to 3^3^3 and stores them in a variable name. The second has several layers. The outer "Show" and "GraphicsArray", with the "ImageSize" option at the end, just display all the resulting plots as one graphic. The "Partition" and "Table", with the answering "8" and "{i,1,96}" just generate plots for each of the rule numbers we created before, and divides the resulting list of 96 plots into 16 lines of 8 plots each. The "ArrayPlot" and "DisplayFunction->Identity" produce the graphics themselves, but hold their display until the surrounding "Show". The "CellularAutomaton" function call generates the array of {0,1,2} data that is passed to ArrayPlot. Its fourth argument, "{All, All}" says to include all cells that might have been changed by the CAs evolution, which keeps all the plots the same size, for display in our GraphicsArray. "20" is the number of steps we run each rule for. "{{1},0}" is out initial condition, of a single gray cell surrounded by a background of 0s. Last, the first argument gives the rule number as one element of our random sample, and specifies this as a 3 color, range 1 rule.
The first thing one notices is that the much greater number of possible forms does not produce any fundamentally new pattern we haven't seen before in the 2 color ECAs. (E is for "elementary", the basic 256 2 color range 1 CAs). One does see more intermediate types and "mixes" of behaviors. That happens because the larger rule tables can differ is subtler ways, cases that apply rarely for instance. Whereas one ECA differs from another in one case out of eight. One can think of this as "coarser" differences between the patterns seen. But there isn't a class 5, class 6, etc behavior just waiting to be found when one goes to 3 colors, nor additional class n behaviors as the number of colors increases further.
Old engineering intuition suggests you'd get more complexity out indefinitely, as you increase the allowed number of colors. But at least one point of the principle of computational equivalence is, that once you are past the threshold of universality, there isn't any fundamentally new behavior to add. Maximal complexity is already there, in a sense. The reason Wolfram focuses so much on the ECAs is some of them are already across that threshold. It is easier to find great complexity in higher color (or longer range) rules. But the great complexity found has the same character as that already seen in rule 110 (the class 4s), or rule 30 (the class 3s). Wolfram deliberately started with the simplest case to find the threshold of complexity. It isn't a contest to see how much extraneous detail one can add beyond that threshold, any more than mathematically stated laws try to find polynomial forms with as many terms as possible.
All that said, of course the 3 and 4 color rules are of interest in their own right and do lots of funky things.
As for consideration of "errors" and of added randomness, there are many ways one can tweak CA code to incorporate them. Chapter 6 as a whole is about starting from random initial conditions. It also considers difference patterns from flipping one cell in a given initial condition (see page 250, and the sensitivity to initials thus understood. A note on page 945 shows the result of generating the center cell of a CA evolution randomly at each step, as a minimalist form of continually injected randomness. As for multi-valued transitions, the NKS book considers them as multiway systems. In chapter 12 there is a discussion of non-deterministic Turing machines, which have "choices" of evolution at each step, and a scheme is shown that emulates a non-deterministic TM with a single CA rule, with different initial conditions for the CA corresponding to different possible evolutions of the TM. (See page 767).
There has also been considerable work on various multi-valued schemes since the book came out, discussed previously on this forum. First there is the GCA idea, the G standing for "global", which originated in a conversation between Wolfram and Paul Davies. The idea with GCAs is to let the rule applied on a given step depend on some global variable that is a function of the prior step (density, even or odd number of black cells, etc). A thread on GCAs can be found here -
http://forum.wolframscience.com/sho...?s=&threadid=62
A later development of this idea is the ICA or "interactive" cellular automata, which is a "machine with input" version of a CA. At each step, one rule out of a list is applied, the "choice" which depending on an external sequence. A standard CA evolution thus formally corresponds to an ICA with constant input sequence. There exists some ICA sequence that corresponds to a GCA global control rule, though it may in general be hard to find that sequence. ICAs are a natural way of modeling a CA like system in continual interaction with an external environment. They can also be used to simulate multi-valued CAs with one indeterminate case in their rule table, by choosing a list of rules for the ICA that differ in only a single location e.g. Then the external sequence specifies how that case is to be handled on that step.
One can also just let such an ambiguous case be determined randomly. Last and a little more intricate to code, but not to understand, one can specify the behavior at each instance of an ambiguous case application, by an external ("ICA-like") sequence. This is effectively "pulling out" the sequence of "coin flips" involved in a random-case CA evolution. It lets one do sensitivity analysis on the resulting behavior, more readily than just generating a sample of random CA evolutions. There was a thread on these, prompted by a desire to pin down ideas about "emergence" offered by Paul Davies again, here -
http://forum.wolframscience.com/sho...s=&threadid=788
That one includes code for evolving ICAs.
What does one find, investigating these generalizations? The basic forms of behavior are the same as those already seen. It is easier to find intermediary cases. One can "tune" between one known behavior and another more readily. They are natural models of cases where feedback effects or maximizations can realistically be expected in the system being modeled. In principle, a deterministic CA that is universal can model the same computations, encoding states differently in configurations of cells, and potentially using other colors to "impact" the base color evolution at some later point. But such formal, constructable equivalences are no reason to avoid using multi-valued models where those are simpler and more natural for the real system.
As for the statement that only the introduction of errors can approximate nature's complexity, it does not follow. It is not the case that randomness must be continually injected from the environment, for complexity to arise. Indeed, formal systems in which there is no such injection are computationally as sophisticated as any finite process. See the discussion on mechanism for randomness starting on page 299.
Moreover, we see complexity in natural systems distinct from and prior to life, in which there is no question of natural selection operating. So complexity does not require such mechanisms to arise. It undoubtedly does involve such mechanisms in the case of life, but that is distinct from the claim they are necessary for complexity. And they simply are not. Note that I say, for complexity - not everything, not all of life. Just "complexity", a single distinct phenomenon, which it turns out is not as hard to get as people might have supposed in the past.
There is complexity in fracture patterns, in weathering, in turbulent flow, and in simple deterministic formal systems, the former not needing all the additions of life, and the latter not needing randomness or continuous reals. No explanation of complexity that requires things CAs lack is correct, since CAs are already complex without those things.
As for Ashby, his law was not continual injection of randomness, merely "requisite variety". And there is sufficient "requisite variety" in systems with modest numbers of elements, as soon as those elements can interact in arbitrary ways, "combinatorially", rather than in ways that add or cancel in simple ways. The requisite variety to name every particle in the universe exists on a Go board. We say, arrangement possibles are for practical purposes always larger than dynamically reached actuals.
That is precisely why we are interested in rules, simple invariants of dynamics that determine which states are actually visited out of those we can imagine as possible. We don't have to consider every possible arrangement for the simple reason that the universe can't possibly visit them all in finite time. Consider for example the number of possible arrangements of DNA base pairs of the lengths seen in typical genomes, and the number of DNA molecules that can have existed in the history of life, in any crude approximation you like. The former swamps the latter. Ergo, the requisite variety to specify such life as has actually occurred is dramatically lower than all possible DNA sequences. Actual life is a tiny speck in its possibility space. So the dynamics matter - which possible states are actually reachable? We don't need all the permutations because nature can't reach them all, either.
It is true that perturbations allow a transition from one path in a deterministic system's state space to another. Sometimes to portions of that space reachable from different initial conditions, sometimes not. For rules with sufficient structure, the dynamically reachable region is still going to be smaller than the entire imaginable configuration space. And that is not a drawback. If one thought each state of the system were an arbitrary number of bits at each step, and the mapping between them were an arbitrarily changing map, you'd just have a disjoint series, f of some real goes to some other real, g of that then goes to some third, etc, without any order. We don't want an arbitrary mapping. "Everything imaginable happens, who knows when" isn't a model, it is broad underspecification, and empirically we know it will turn out false. (There isn't time enough for everything to happen).
The point is to keep the maximum amount of determinism and structure possible, while preserving the variety of behaviors seen in the real system - not to underspecify the system as potentially able to go anywhere. In Ashby's terms, we only go to a multivalued model if the observed protocol resists recoding as a deterministic system. First we try to find a single-valued transformation that accounts for what we see, imputing additional states (microconfigurations etc) if necessary. If we can dramatically simplify our model by letting one case be multi-valued, fine we can do so. But there is no prior reason to start there.
I hope some of this helps. Fine questions to raise, by the way.
Report this post to a moderator | IP: Logged
|
09-12-2005 05:26 AM
