I have posted this also at the Wolfram Science Forum.

Research Proposal: Exhaustive Study of Cellular Automata State Transition Diagrams

Research proposal from AndriusKulikauskas of MinciuSodas to StephenWolfram of WolframResearch.

Purpose

Stephen Wolfram's paper "Algebraic Properties of Cellular Automata" (1984) establishes techniques which I propose to extend for an exhaustive study of the varieties of behavior of two-color three-cell cellular automata along with implications for automata with more colors and more cells.

The two-color three-cell cellular automata exhibit different levels of complexity: class 1 (simple), class 2 (fractal), class 3 (random), class 4 (complex). However, as of yet there is no definitive classification of these 256 automata as to which class each belongs to. I propose a research approach that would provide a clear answer for each automaton. Furthermore, I believe that we will be able to automate this approach and apply it to analyze and classify, to a greater or lesser degree, cellular automata with any number of colors or cells. This will make it possible to construct filters that could determine efficiently from the rules of a cellular automaton whether it is class 1, class 2 or more complex, perhaps even distinguish between class 3 and class 4.

The approach will yield a qualitative understanding of each cellular automata's overall behavior. I will create a Mathematica algorithm that will deduce from the automata rules the background patterns (the attractors) that the automaton can generate from periodic input as well as other key information about the automaton's state transition diagram. I will provide a detailed account of specific obstacles that prevent the patterns from being deduced efficiently for any of the 256 automata.

Given a cellular automaton, and without simply running it step by step: Can we formulate all of its backgroud patterns? Given a periodic input for that automaton, can we calculate whether or not it is part of a background pattern? and which background pattern it leads to?

There are many practical problems which could be solved if it was possible to generate and/or analyze the possible background patterns. Here are several from Stephen Wolfram's, "A New Kind of Science: Open Problems and Projects", Incomplete Preliminary Version, June 26, 2003, pages 5, 11-15, 27-28:

• find initial conditions that make for nested patterns, take longest to settle down.
• discover an explicit formula for the cell colors for rule 225
• determine which growth rates of patterns can be achieved
• study the 3-color, 2-cell automata
• (this is the essence of my proposal!) develop a classification of cellular automata from simple initial conditions, and "develop an automated system that decides for most cellular automata where they should lie in the classification". "Develop automated ways of finding "interesting" automata" (filters). "Find ways to estimate the frequencies of different types of cellular automaton behavior."
• discover, what repetition periods can be achieved by simple cellular automata? What forms of nesting can cellular automata produce? Is nesting associated with some form of additivity? Build a general tool for recognizing patterns that should be considered nested.
• find the long term behavior of particular automata such as codes 1635 and 1599.
• discover, which cellular automata generate patterns that take longest to stabilize?
• study compositions of cellular automaton rules and the patterns they produce - an algebra of composing succesive rules, and what patterns can result.
• analyze typical changes in behavior as more complex rules are allowed. Can one make explicit measures that reflect that above some low threshold, the behavior that classes of systems exhibits no longer gets fundamentally more complex?

• invent other convenient types of cellular automaton rules.
• investigate cellular automata based on complex numbers, quaternions, other systems from abstract algebra.
• develop well-codified principles for computer experiments.
• catalog surprises in computer experiments.

Christopher Alexander's "The Timeless Way of Building" argues that harmonious structures arise by applying a sequence of patterns, starting on the biggest scale and working down to the smallest scale, and optimizing each step along the way. We know of cellular automaton that for certain input do weave such harmonious output. How might we think of cellular automaton as a sequence of patterns? We can think of a cellular automaton's rule set (in more than one way) as the result of a sequence of extensions such as adding a color or adding a cell. We can likewise consider how the automaton's state transition diagram and background patterns evolve with such extensions. As I do the research above, I will look for informative examples and general results for how the properties of an automaton unfold as its rules get extended, and in particular, for any effects that observe "levels of scale". I will look for a general theory for understanding cellular automata with any number of colors and cells.

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 two-color, three-cell 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 case-by-case, 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 semi-automated 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 two-color, two-cell 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 two-color, two-cell 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 step-by-step 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 two-color, three-cell 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.

Preliminary Results

Two-color, one-cell automata

Two-color, two-cell automata

Rule 6

The Sierpinski gasket is an additive cellular automaton (mod 2) and so Section 4 of Stephen Wolfram's paper "Algebraic Properties of Cellular Automata" applies.

Rule 14

Table with all of the rules

Note that we took the square on the left, but we could have constructed a different table by looking at the square on the right.

Two-color, three-cell automata

Rule 105

Rule 105 can be thought of as adding (mod 2) the values of all the cells plus 1.

Rule 105's state transition diagram consists of long and short cycles and also trees that promptly collapse into loops. Lyndon words of length 3, 6 and 12 collapse into the trees. Lyndon words of length 9 do admit of a cycle which consists of one-fourth of such words, the other three-fourths being transients into this cycle.

Rule 30

Rule 101

Rule 101' s state transition diagram has long transients and long cycles but few branchings.

Rule 110

Rule 110' s state transition diagram has long transients and also many brachings.

Deliverables

Within six months I will deliver for each of the 256 two-color, three-cell cellular automata the following answers:

• An explicit formula for determining whether an aperiodic word (periodic input) is part of a background pattern (is an attractor state) or not (is a transient state).
• An enumeration of the background patterns which the automaton can possibly generate.

I will summarize my results with a set of rules that definitively classify each of the 256 automata and relate them to Stephen Wolfram's classification system.

I will describe a general method for providing the answers and the classification.

• as a mathematical paper
• as a popular account
• as a set of Mathematica functions, including an algorithm for deducing the answers starting from an automaton's rules

I will make the functions, filters and tools available as Mathematica packages and demonstrations.

I will engage the public in related discussion at the New Kind of Science forum and Minciu Sodas online venues, including the extension of automata in terms of adding cells and colors, and the implications of entropy reversal as observed in Stephen Wolfram's paper "Algebraic Properties of Cellular Automata".

All of my work will be in the Public Domain.

Qualifications

The work outlined is straightforward but creative and may yield thought provoking results. It is central to the understanding of cellular automata and builds on Stephen Wolfram's fundamental work. I believe the work that I propose would make for an interesting Ph.D. thesis and may lead to many new research questions.

In 1993, I received a Ph.D. in mathematics from the University of California at San Diego. My thesis was in algebraic combinatorics, "Symmetric Functions of the Eigenvalues of a Matrix". It reflects the rigor which I can apply to analyzing the cellular automata. I also attended six graduate courses in automata theory, Turing machines and recursively enumerable functions. My goal is "to know everything and apply that knowledge usefully" which I approach by studying the limits of what we can conceive. I lead the Minciu Sodas laboratory and as I do this work I can engage the public and build a team for future projects. I wish to prepare other proposals to organize social networkers to support "mathematical thinking" using Mathematica, A New Kind of Science, and all manner of tools for mathematical exploration.

Budget $12,000

12, 000 USD = 2, 000 USD x 6 months

AboutThisPage

• ProposalSummary=AndriusKulikauskas is submitting this 6 month, $12,000 research proposal to StephenWolfram.
• ProposalStatus=Will be submitting in August, 2008.

Upload:AndriusKulikauskas/researchproposal.nb