User:InverseHypercube/Sandbox2

Classification

Wolfram classes

Stephan Wolfram, in A New Kind of Science and in several papers dating from the mid-1980s, defined four classes into which cellular automata and several other simple computational models can be divided depending on their behavior. While earlier studies in cellular automata tended to try to identify type of patterns for specific rules, Wolfram's classification was the first attempt to classify the rules themselves. In order of complexity the classes are:

• Class 1: Nearly all initial patterns evolve quickly into a stable, homogeneous state. Any randomness in the initial pattern disappears.
• Class 2: Nearly all initial patterns evolve quickly into stable or oscillating structures. Some of the randomness in the initial pattern may filter out, but some remains. Local changes to the initial pattern tend to remain local.
• Class 3: Nearly all initial patterns evolve in a pseudo-random or chaotic manner. Any stable structures that appear are quickly destroyed by the surrounding noise. Local changes to the initial pattern tend to spread indefinitely.
• Class 4: Nearly all initial patterns evolve into structures that interact in complex and interesting ways. Class 2 type stable or oscillating structures may be the eventual outcome, but the number of steps required to reach this state may be very large, even when the initial pattern is relatively simple. Local changes to the initial pattern may spread indefinitely. Wolfram has conjectured that many, if not all class 4 cellular automata are capable of universal computation. This has been proven for Rule 110 and Conway's game of life.

These definitions are qualitative in nature and there is some room for interpretation. According to Wolfram,

...with almost any general classification scheme there are inevitably cases which get assigned to one class by one definition and another class by another definition. And so it is with cellular automata: there are occasionally rules...that show some features of one class and some of another.

Quantitative methods

Sources: http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V12-3SNYSPG-6&_user=1022551&_coverDate=11%2F15%2F1997&_rdoc=1&_fmt=high&_orig=gateway&_origin=gateway&_sort=d&_docanchor=&view=c&_searchStrId=1688332025&_rerunOrigin=google&_acct=C000050484&_version=1&_urlVersion=0&_userid=1022551&md5=bc47f9debc9680d82287261b6ee88409&searchtype=a http://www.ccsr.uiuc.edu/web/Techreports/1988-89/CCSR-89-8.pdf Kunkle thesis http://www.wolframscience.com/nksonline/page-948f-text http://demonstrations.wolfram.com/ClassifyingTheComplexityAndInformationOfCellularAutomata/