Mark Gritter (markgritter) wrote,
Mark Gritter

Classifying 2-D Cellular Automata

David Eppstein (who is not one of the missing Eppes siblings) announced a new paper on classifying 2-D cellular automata, entitled "Growth and Decay in Life-Like Cellular Automata". (announcement).

This is a subject dear (if not near) to my heart. At Gustavus, I took a seminar on "Complexity" from Nobel laureate Philip Anderson, who was there as a guest for a semester. My seminar project was on characterizing 2-D cellular automata--- specifically, looking at whether the simple lambda metric devised by Christopher Langton was a good predictor of behavior. (Lambda measures what fraction of output states are quiescent, and it appears to be a good fit for 1-D automata.) My conclusion was that it was not, because I found both examples of complex behavior far from the 'critical value' and many examples of chaotic behavior close to the critical value.

(Digression: This was not a project that Dr. Anderson was particularly interested in. He suggested a much more difficult topic that I still have little idea how to tackle--- basically, how to characterize the search space of "realistic" problems. Computational complexity is full of examples that cause search algorithms to produce worst-case behavior. Can we make some sort of interesting statement about which properties of the search space produce "good" behavior? Obviously trivial problems can be solved trivially...)

Eppstein argues that Wolfram's four categories of CA behavior are insufficient because they ask about behavior starting from a random state. But interesting examples of Life behavior are highly nonrandom starting states--- random Life patterns tend to settle into still lifes and oscillators, so why is it not "Category II"? Eppstein proposes a different categorization based on just two axes: does the CA have patterns which grow to escape any finite bounding box, and does it have patterns which "die out" completely? An advantage of these criteria is that we can actually reason about them based on the rule set, instead of making qualitative judgements by observing behavior.

Some of Eppstein's earlier work was on searching for spaceships in semi-totalistic CAs like Life --- it's in More Games of No Chance, which I would strongly encourage math (and game) geeks to pick up should they have the chance. (Volume 3 in the series is out and on my Christmas list...)
Tags: cellular automata, complexity, computers, geek, math
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.