wolframscience.com

A New Kind of Science: The NKS Forum : Powered by vBulletin version 2.3.0 A New Kind of Science: The NKS Forum > Pure NKS > Proposal: Exhaustive Study of Cellular Automata State Transition Diagrams
  Last Thread   Next Thread
Author
Thread Post New Thread    Post A Reply
Andrius Kulikauskas
Minciu Sodas
Lithuania

Registered: Nov 2005
Posts: 34

Proposal: Exhaustive Study of Cellular Automata State Transition Diagrams

Stephen Wolfram, Michael Schreiber, Todd Rowland, Jason Cawley, Matthew Szudzik, Tommaso Bolognesi,

Thank you for a stimulating New Kind of Science summer school and for your help with my project:
http://www.worknets.org/wiki.cgi?LawsOfArchitecture

I was also greatly encouraged that I could present a proposal
from my Minciu Sodas laboratory http://www.ms.lt for independent thinkers. I would like to organize a culture of investigation, at the heart of which is A New Kind of Science.
http://www.worknets.org/wiki.cgi?ANewKindOfCulture

I spoke with Stephen Wolfram that I would write a smaller version of my proposal that we might start with to show what we can do. However, after the summer school, I worked a bit more on my project and I saw the need for a procedure to generate, for each automata, the background patterns that it yields. I made some conceptual and technical advances, reproducing and extending some of Stephen Wolfram's work from his 1984 paper "Algebraic Properties of Cellular Automata". I decided that the most practical proposal which I could make would be to pursue this theoretical work. Meanwhile, I could prepare proposals for the social networking which our Minciu Sodas laboratory excels at. I share my proposal below and I invite help to fund my proposal, to make theoretical advances and encourage other initiatives.
http://www.worknets.org/wiki.cgi?CellularAutomata

__________________
Minciu Sodas http://www.ms.lt laboratory for serving and organizing independent thinkers.

Last edited by Andrius Kulikauskas on 08-27-2008 at 04:00 AM

Report this post to a moderator | IP: Logged

Old Post 08-27-2008 03:19 AM
Andrius Kulikauskas is offline Click Here to See the Profile for Andrius Kulikauskas Visit Andrius Kulikauskas's homepage! Edit/Delete Message Reply w/Quote
Andrius Kulikauskas
Minciu Sodas
Lithuania

Registered: Nov 2005
Posts: 34

Purpose

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?

The results would also be helpful for several other of Stephen Wolfram's challenges:

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

Background patterns are key to complexity because they are needed as "voids" wherever there are "levels of scale" as in Nikos Salingaros's Laws of architecture. Class 4 behavior is intuitively understood as local activity taking place on some background, which means that the activity can be or not be, and so there must be compatible patterns that represent either case. My research should yield rigorous characterizations of Class 1, 2, 3 and 4 behavior, and quite likely a more detailed characterization.

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.

__________________
Minciu Sodas http://www.ms.lt laboratory for serving and organizing independent thinkers.

Report this post to a moderator | IP: Logged

Old Post 08-27-2008 03:21 AM
Andrius Kulikauskas is offline Click Here to See the Profile for Andrius Kulikauskas Visit Andrius Kulikauskas's homepage! Edit/Delete Message Reply w/Quote
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 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.

__________________
Minciu Sodas http://www.ms.lt laboratory for serving and organizing independent thinkers.

Report this post to a moderator | IP: Logged

Old Post 08-27-2008 03:23 AM
Andrius Kulikauskas is offline Click Here to See the Profile for Andrius Kulikauskas Visit Andrius Kulikauskas's homepage! Edit/Delete Message Reply w/Quote
Andrius Kulikauskas
Minciu Sodas
Lithuania

Registered: Nov 2005
Posts: 34

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.

For those automata for which I am not able to provide complete answers I will explain in detail where and how my methods fail.

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 available a set of filters and tools which can be used on automata with more cells and colors to remove the simple automata.

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.

__________________
Minciu Sodas http://www.ms.lt laboratory for serving and organizing independent thinkers.

Report this post to a moderator | IP: Logged

Old Post 08-27-2008 03:24 AM
Andrius Kulikauskas is offline Click Here to See the Profile for Andrius Kulikauskas Visit Andrius Kulikauskas's homepage! Edit/Delete Message Reply w/Quote
Andrius Kulikauskas
Minciu Sodas
Lithuania

Registered: Nov 2005
Posts: 34

Qualifications and Budget

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 USD = 2, 000 USD x 6 months

__________________
Minciu Sodas http://www.ms.lt laboratory for serving and organizing independent thinkers.

Report this post to a moderator | IP: Logged

Old Post 08-27-2008 03:24 AM
Andrius Kulikauskas is offline Click Here to See the Profile for Andrius Kulikauskas Visit Andrius Kulikauskas's homepage! Edit/Delete Message Reply w/Quote
Andrius Kulikauskas
Minciu Sodas
Lithuania

Registered: Nov 2005
Posts: 34

Preliminary Results

My proposal and some preliminary results:

for two-color, three cell automata Rules 105, 30, 101, 110 and for two-color, two-cell automata


__________________
Minciu Sodas http://www.ms.lt laboratory for serving and organizing independent thinkers.

Last edited by Andrius Kulikauskas on 08-27-2008 at 03:45 AM

Report this post to a moderator | IP: Logged

Old Post 08-27-2008 03:33 AM
Andrius Kulikauskas is offline Click Here to See the Profile for Andrius Kulikauskas Visit Andrius Kulikauskas's homepage! Edit/Delete Message Reply w/Quote
Andrius Kulikauskas
Minciu Sodas
Lithuania

Registered: Nov 2005
Posts: 34

Rule 30

The state transition diagram for Rule 30 for the words of length 12 or less.

Andrius Kulikauskas has attached this image:

__________________
Minciu Sodas http://www.ms.lt laboratory for serving and organizing independent thinkers.

Report this post to a moderator | IP: Logged

Old Post 08-29-2008 06:22 PM
Andrius Kulikauskas is offline Click Here to See the Profile for Andrius Kulikauskas Visit Andrius Kulikauskas's homepage! Edit/Delete Message Reply w/Quote
Andrius Kulikauskas
Minciu Sodas
Lithuania

Registered: Nov 2005
Posts: 34

Rule 30

I was surprised to find regularity even with Rule 30.

Andrius Kulikauskas has attached this image:

__________________
Minciu Sodas http://www.ms.lt laboratory for serving and organizing independent thinkers.

Report this post to a moderator | IP: Logged

Old Post 08-29-2008 06:32 PM
Andrius Kulikauskas is offline Click Here to See the Profile for Andrius Kulikauskas Visit Andrius Kulikauskas's homepage! Edit/Delete Message Reply w/Quote
Andrius Kulikauskas
Minciu Sodas
Lithuania

Registered: Nov 2005
Posts: 34

Rule 30

Here's an example of my empirical research (for words of length up to 12) and the kind of reverse analysis that I would like to do.

Andrius Kulikauskas has attached this image:

__________________
Minciu Sodas http://www.ms.lt laboratory for serving and organizing independent thinkers.

Report this post to a moderator | IP: Logged

Old Post 09-03-2008 01:09 AM
Andrius Kulikauskas is offline Click Here to See the Profile for Andrius Kulikauskas Visit Andrius Kulikauskas's homepage! Edit/Delete Message Reply w/Quote
Andrius Kulikauskas
Minciu Sodas
Lithuania

Registered: Nov 2005
Posts: 34

Related research?

I'm looking for related research...

A Survey on Cellular Automata by Niloy Ganguly, Biplab K Sikdar, Andreas Deutsch, Geo rey Canright, P Pal Chaudhuri in Germany, India, Norway.
http://www.cs.unibo.it/bison/publications/CAsurvey.pdf

Behaviors of Single Attractor Cellular Automata over Galois Field GF(2p)
by Sung-Jin Cho, Un-Sook Choi, Yoon-Hee Hwang, Han-Doo Kim and Hyang-Hee Choi
http://www.springerlink.com/content/15262364x3n663pr/

Random Sequence Generation by Cellular Automata by Stephen Wolfram http://www.stephenwolfram.com/publi...om/10/text.html

A Categorical Representation of the State Transition Graph of Finite Cellular Automata by
Jung-Hee, Hyen-Yeal, Lee in South Korea
http://journal-ci.csse.monash.edu.a.../park/park.html


Discrete baker transformation for binary valued cylindrical cellular automata by Burton Voorhees in Canada in Cellular automata : ( 7th international conference on cellular automata for research and industry, ACRI 2006, Perpignan, France, September 20-23, 2006 ) ( proceedings )
http://cat.inist.fr/?aModele=afficheN&cpsidt=19910581

Tables of Cellular Automaton Properties by Stephen Wolfram 1986

Drawdown Automata, Part 3: Pattern Sequences by Ralph E. Griswold in Arizona
http://www.cs.arizona.edu/patterns/...cs/gre_dda3.pdf

__________________
Minciu Sodas http://www.ms.lt laboratory for serving and organizing independent thinkers.

Last edited by Andrius Kulikauskas on 09-19-2008 at 01:33 AM

Report this post to a moderator | IP: Logged

Old Post 09-19-2008 01:19 AM
Andrius Kulikauskas is offline Click Here to See the Profile for Andrius Kulikauskas Visit Andrius Kulikauskas's homepage! Edit/Delete Message Reply w/Quote
Post New Thread    Post A Reply
  Last Thread   Next Thread
Show Printable Version | Email this Page | Subscribe to this Thread


 

wolframscience.com  |  wolfram atlas  |  NKS online  |  Wolfram|Alpha  |  Wolfram Science Summer School  |  web resources  |  contact us

Forum Sponsored by Wolfram Research

© 2004-14 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer | Archives