Andrius Kulikauskas
Minciu Sodas
Lithuania
Registered: Nov 2005
Posts: 34 
Methodology
Stephen Wolfram's "A New Kind of Science" makes evident the stunning nature of Rule 110: "...in cellular automata, not only can the underlying rules be simple, but the initial conditions can also be simple  consisting say of just a single black cell  and still the behavior that is produced can be highly complex" (Chapter 2, The Crucial Experiment, The Need for a New Intuition).
Yet we can have initial conditions that are even simpler. Just as a Dirac delta function can be thought of as an infinite series of trigonometric functions, so might we consider the behavior of a single black cell (which has infinite period!) in terms of periodic inputs such as "all white cells", "all black cells", or the infinite repetition of any aperiodic word (any Lyndon word). These aperiodic words may be thought of as states in a state transition diagram. The cellular automaton acts uniformly on such periodic inputs (with period of length N) as if it had N cells in a circle. Each such input must ultimately lead to some state which appears with regularity, thus a cycle of states, an attractor, what we see as a background pattern that is periodic horizontally (because the input was periodic) and vertically (because the states must at some point start to repeat). The state transition diagram for the automaton is thus a set of structures, each of which has a cycle (an attractor) into which transient states lead into, along the way forming trees that lead into the cycle at different places. Stephen Wolfram takes this approach in his paper "Algebraic Properties of Cellular Automata" (1984).
Independently, I also took this approach at the 2008 "A New Kind of Science" summer school. For the homework, I created a very effective filter that for each automaton considered how long it took for a nontrivial periodic state to settle down into a background pattern. After the summer school, I wanted to study more patterns and I needed a more effective way to generate them comprehensively. In many cases it is possible to derive directly from the automata rules how the states are organized in the state transition diagram, and in particular, to generate the background patterns and to have a formula to know whether or not a state is in a background pattern. Stephen Wolfram does this algebraically for additive cellular automata in his paper. He also shows that other automata, such as Rule 18, can be analyzed "by a straightforward but lengthy analysis". I propose to do this analysis for all of the 256 twocolor, threecell automata. In my preliminary results, I have shown that such analysis can make headway even in understanding Rule 30.
The essence of this approach is to establish the extent to which a cellular automaton's rules can be reversed. The automaton takes every state (periodic input) B to a successor, a subsequent state C. But does B have a predecessor, a state A that precedes it?
Given a state, do its chains of predecessors always terminate? Then it is a transient state. Otherwise, it is in a cycle, and is an attractor state. In order to answer these questions, we look for ways to tell which states have no predecessor, which have exactly one predecessor, and which have more than one predecessor and are thus branching states. We also look for ways to distinguish amongst predecessors, which if any of them is in a cycle?
The approach works casebycase, analyzing particular inputs and working backwards to consider what constraints there might be on its production. My plan is to do several specific cases and then to build with Mathematica more general analytical tools, at first semiautomated and then automated, which would discover the relevant constraints or point out the obstacles that obscure such deduction.
I imagine the cellular automaton as a transformation that takes us from irreversibility to reversibility. The attractor states (the background patterns) are precisely those states which are in a cycle and thus for which we can define a unique predecessor as far back as we like. In this sense they are "reversible". Indeed, for a reversible automaton, the state transition diagram is simply a set of loops and cycles. In this way, we can think of the state transition diagram as distinguishing states that are in a cycle (a background pattern) and thus "reversible" (attractors) and those that are "not reversible" (transients).
Furthermore, we can consider the transient states as graded in terms of the maximal length of their chain of predecessors. Some of the transients have no predecessors at all, and for others we can take a few steps back. An analysis of the automata rules can make evident what is happening here. For example, the twocolor, twocell rule 14 allows for the "all white" state but otherwise everything tends towards the "all black" state. The length of the longest block of white cells is the parameter that indicates how far away the state is from "reversibility". With each step towards the attractor, the length of the longest block goes down by one. The attractors of the twocolor, twocell rule 6 (the Sierpinski gasket) are states whose sums are even over all cells but also over any equivalence classes of cells, defined as follows. The equivalence classes are relevant when the lengths are divisible by 2**k and two cells are in the same equivalence class if they can reach each other by shifts of size 2**k. (For example, when k=1, then there are two equivalence classes, and they are gotten by taking every other cell.) The automaton works methodically to transform a state with odd sum to a state with even sum, and then makes sure that the equivalence classes have even sums, until they all do. (I need to work out these details.)
I find this a satisfying way to think of the automaton's action because we can give the local rules a global purpose. That purpose is to transform inputs stepbystep so that they satisfy some invariant which establishes their reversibility. The transients can be ranked or graded in terms of the degree to which they do not satisfy that invariant, which accords with the number of steps that the automaton will require to alter the transient until it does satisfy the invariant.
I will look for connections with other areas of mathematics and computer science. We can also think of this as a halting problem: Given a state, will we come to it again (and so it halts) or will we never come to it again (and so it never halts)? We can think in terms of combinatorial involutions, where some states are fixed points and other states are paired up with those of opposite sign and cancel away. Reversing the automaton is perhaps the solving of systems of linked equations. We can think in terms of the transients, attractors and periodic states of chaos theory.
I expect that after exhaustively studying the twocolor, threecell automata in this way, I will uncover a way to classify automata in terms of how explicit we can make its global purpose, its attractors and transients, its invariants, its gradation of transients, as described above. This will advance our qualitative understanding of particular automata and general classes.
__________________
Minciu Sodas http://www.ms.lt laboratory for serving and organizing independent thinkers.
Report this post to a moderator  IP: Logged
