Registered: May 2006
Posts: 9

I have some questions concerning the automatic classification of 1D Cellular Automata starting from deterministic (just one cell is active; page 55-56 of the NKS book) or random initial conditions (page 232 of the NKS book) , the r=1 update rule and cyclic boundary conditions. With automatic classification I mean, that for a given spatio-temporal pattern, generated by a CA, one has to deside which class the CA has to be assigned.

In the following all questions concern ONLY to CA's defined above.

1. Are there tables available providing these results?

In the NKS book, there are lots of pictures available, however, I could not find a comprehensive summary table allowing easily to access this information.

For example, Universality and Complexity in Cellular Automata (1984), S. Wolfram, suggests to use topological and metric entropy. However, I could not find numerical results in this paper demonstrating that this approach is possible.

Andy Wuensche, Wuensche,A., (1999) "Classifying Cellular Automata Automatically: Finding gliders, filtering, and relating space-time patterns, attractor basins, and the Z parameter", COMPLEXITY, Vol.4/no.3, 47-66, 1999, suggested to use input-entropy, but also did not provide numerical results.

2. Is the classification of a CA rule independent of the initiial condition (see above)?

3. If the classification of a CA rule is independent of the initial condition, what criteria was used to base the decision on?

In this context I consider 'visual inspection' as usable heuristics, however, this question aims again to a mathematical measure.

4. Are there other complexity measures (of spatio-temporal patterns)
that have been applied numerically to the classification of 1D CA?



I would be grateful for any references to the above questions. Also I would like to know, if someone is of the opinion that one of the above questions is not sufficiently answered so far.

Last edited by Frank Emmert-Streib on 05-18-2006 at 08:17 PM

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 167

Frank, I had similar thoughts earlier this year which I posted about here which turned up a couple of older links that I referenced in my follow up post in that thread.

__________________
Tony Smith
Complex Systems Analyst
TransForum developer
Local organiser

Report this post to a moderator | IP: Logged

Registered: May 2006
Posts: 9

Thanks Tony. I read already some of these threads before. Especially [http://forum.wolframscience.com/sho...hp?threadid=429] is interesting. However, form non of these threads an explicite answer for my questions can be derived. Jason Cawley mentioned Andy Wuensche's method (input entropy), however, without reference.

Wuensche,A., (1999) "Classifying Cellular Automata Automatically: Finding gliders, filtering, and relating space-time patterns, attractor basins, and the Z parameter", COMPLEXITY, Vol.4/no.3, 47-66, 1999, introdues only the method and provides some results for half a dozen CA rules but no large scale investigation.

I would add one item to the classification list Lawrence J. Thaden posted:
Defining the Classes of Elementary Cellular Automata

According to some philosophers there are three kinds of definitions:

1. Nominal,
2. Descriptive, and
3. Explanatory.

I would add:

4. Automatic

With a definition based on a modified version of the nominal classification.

A spatio-temporal pattern genrated by a CA is used as input for a classifier and the output of the classifier corresponds with the class index one would assign after visual inspection.

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

Wolfram looked at some of this back in the 80s, and there was a significant amount of work done on it in the late 80s to early 90s by Chris Langton, David Epstein, Howard Gutowitz, Andy Wuensche, and certainly others - those are just the ones that come to mind right away.

There is still useful stuff to do, however. Specifically, cluster analysis might be tried, to find the best ways of cutting up empirical measures into the most natural blobs with little in between, and the like.

As an example, here is one formalization Gutowitz used of the Wolfram classes -

"The Wolfram classification is then expressed as follows:

i) trivial final density (average of the 3 final densities ( 0.05); convergence in 60 time steps,

ii) differing final densities (at least one final density ( 0.05 from average); convergence in (60 time steps,

iii) final densities agree within tolerance (0.05) with average, and are non-trivial,

iv) differing final densities, convergence in > 300 time steps, or no convergence after 2000 time steps.

These cutoffs were suggested by the clustering of the data and examination of the space-time patterns generated by selected rules -the qualitative results are insensitive to the cutoff values. "

He used modest samples of random initials for this, often quite wide - thus effectively sampling a number in parallel on the same array etc. He later explored alternate (and generally, much finer grained) classifications based on how well or how poorly Markov random field models reproduce the CA data, and looked at that for longer ranges and higher numbers of colors.

The motivation was slightly different, and will vary for each of the above. Gutowitz was looking for parameters that would give some analog of continuity of eventual behavior as they gradually changed. Wuensche especially wanted signatures of 4s to aid searches, and stats on changing portions in each class as colors etc increased. You will get different points of emphasis from each.

Look for papers by any of those above, and any they cite themselves to discover more of the literature tree. It remains a fine problem and more can be done on it.

Report this post to a moderator | IP: Logged

Registered: May 2006
Posts: 9

Thanks Jason! Could you please send me the references to the papers of Gutowitz in which these methods are described you mentioned in your reply?

Remark to Wuensche:
Wuensche,A., (1999) "Classifying Cellular Automata Automatically: Finding gliders, filtering, and relating space-time patterns, attractor basins, and the Z parameter", COMPLEXITY, Vol.4/no.3, 47-66, 1999, introdues only the method (input entropy) and provides some results for half a dozen CA rules but no large scale investigation.

If you know of any other paper this method is applied explicitly, please let me know.

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

My quote is from his 1989 paper Mean Field Theory vs. Wolfram Classification of Cellular Automata. It is available on the web through his home page at the SFI -

http://www.santafe.edu/~hag/mfw/node1.html

The section I cited is the one entitled "Monte Carlo Analysis of Mean Field Behavior".

I hope this helps.

Report this post to a moderator | IP: Logged

Registered: Jul 2006
Posts: 3

You might be interested in my new paper of mine entitled "Compression-based investigation of the dynamical properties of cellular automata and other systems" available in the Complex Systems journal website: http://www.complex-systems.com/abst...19_i01_a01.html

It advances an experiment studying qualitative properties of CA (and Turing machines) based on the approximation of their Program-size complexity using a general lossless compression algorithm. It is shown that the compression-based approach classifies cellular automata (CA) into clusters according to their heuristic behavior, with these clusters showing a correspondence with Wolfram's classes of CA behavior. A Gray code-based numbering scheme for initial conditions and a compression based method to estimate a characteristic exponent to detect phase transitions and measure the resiliency or sensitivity of a system to its initial conditions is proposed, constituting a compression-based framework for investigating the dynamical properties of cellular automata and other systems.

An interesting question about Wolfram's classification concerns its dependence on the initial conditions, an evolution of a CA depends, however, on its initial condition. In general, the question is undecidable.

The paper on compression-based investigations shows that Wolfram's heuristic classification can actually be quantified by a measure which is clearly dependent on the initial conditions while also being capable of detecting sensitivity to initial configurations and hence of replacing the visual inspection or other statistical techniques.

__________________
Hector Zenil

Report this post to a moderator | IP: Logged

Registered: Oct 2010
Posts: 5

First post today but I have been fascinated by cellular automata since I read NKS during my PhD (made biochemistry look positively dull by comparison).

I've been playing around with the evolvability of cellular automata for a while now but had to find a simple way of quantifying their complexity. I came to this outlook based on my experience of modelling protein folding, looking for stable conformations etc.

In the end I came up with the following system:

1. Assign each of the 16 possible combinations of a 2x2 square a value from 0 to 15 (just binary addition across the squares).

2. Convert the pattern of a cellular automata into a table of numbers from 0 to 15 using the method in step 1.

3. Count the incidence of each number in this array.

4. Arrange the count list from highest to lowest value (ie let go of which count belongs to which pattern)

5. Fit a line through the resulting ordered list and read the gradient.

The system seems to give reliable gradient values for each class of automata (more reliable than I was expecting). For the simplest like rule 0 only one type of cell is counted, so the gradient goes as close to vertical as possible. This defines the lowest level of complexity possible.

As the distribution of different 2x2 cell patterns approaches a random spread, the counts will become equal and the gradient across them will become flat and approach zero. Class 4 automata get to about 5% gradient relative to the blank patterns.

Intermediate classes with some level of repetition on the 2x2 scale give reliable bands of gradients, so you can simply scan a list of gradients and pick out your classes without visual inspection.

I also tested the sensitivity of each rule to input density (ranging from 100% white to 100% black in several increments, randomised in between). The results showed the gradients for each rule were highly insensitive to input, only deviating near the extreme all black or all white inputs.

Presumably the 2x2 sampling system is arbitrary- I havent gone back to try 3x3 etc since it seemed to work so well.

If you are interested I will post later on my study on the evolvability of the classic 3>1 wolfram CA systems. I basically looked at every rule, then every adjacent rule (formed by changing only one of the 8 subrules) then mapped the steepest gradient from simple toward complex.

The whole array of 256 rules separates into about five local minima (rules with no neighboring rules with greater complexity). A proportion of rules seem to be on the borderline of different minima wells depending on the initial input, but most of the network of rules is stable.

I am working toward the idea of how you could best navigate around more complex rule spaces (eg a 4>1 system) in order to find the most complex rule, or a rule that meets a specific criteria (eg contains a specific pattern signature). I am hoping that as the rule set becomes more complex the nearest neighbor rule landscape will become smoother and more connected, reducing the chance of ending up in local minima and missing the best solutions.

Any ideas? Should I post some graphs of my findings so far?

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 167

Rhetorical question. Shane, your approach is so obviously going to work that I'm amazed some derivative of it isn't already standard practice.

I for one would be interested in seeing more of your results before trying any variants for myself.

As we share the same continent there might be some value in making direct contact. I can't imagine advertising ts@meme.com.au one more time in this nowadays too quiet corner will significantly challenge my spam filtering.

__________________
Tony Smith
Complex Systems Analyst
TransForum developer
Local organiser

Report this post to a moderator | IP: Logged

Registered: Oct 2010
Posts: 5

Thanks for the encouragement Tony. It did seem rather obvious to me as an outsider to the field, and you always hesitate to ask what seem like obvious questions when odds are people are either already doing it, or tried it decades ago and found it didn't work.

Here are a couple of graphs of the results of the method I described. I am sorry to admit I am using plain old open office calc as a platform to do the manipulations. Perhaps it is my background as a lab chemist that makes me so happy to do so much repetitive heavy lifting by hand (though I do like the flexibility involved of building everything up from scratch myself).

The two graphs show the gradient (as described above) for each of the 256 CA rules, first with a 50% black/white random initial condition, and next as an average over a range of initial conditions from all black to all white with random distribution. I used a 40 cell wide space with connected edges.

One big difficulty I had was finding a defininitive list of class classifications for each rule. In the end I scanned over the versions presented on the wolfram website, going over the patterns from random initial conditions. Doing this brings up a fair number that are difficult to pin down to a single class. At any rate there is a reasonably good fit between nominal class and the calculated gradient.

This approach definitely makes it easy to hone in on the most random rules and ignore the empty ones. The most beautiful ones seem to be at the class 2 to 3 boundary.

I also have put up a lovely graph of gradient vs initial condition density (next post) that is a great visual summary of how sensitive the gradient system is to initial conditions. It shows how the gradient is usually quite stable for a wide range of initial densities (number of black squares out of 40). The rules with the most potential for complexity are unsurprisingly the most sensitive to initial conditions, but this might just be an artefact from the large chunks of blank space that persist for a while when the rule starts from a single square of a different colour. Shifting the region that is analysed to give the gradient to further down the evolution would avoid this pitfall.

Ill start a new post on CA evolvability elsewhere to put up my results about the shape of the elementary CA rule landscape.

Id be very interested to see what people think about this approach- surely we need semi-automated tools in order to start navigating higher order rule sets where there are millions of arrangements on offer?

Shane Simonsen has attached this image:

Report this post to a moderator | IP: Logged

Registered: Oct 2010
Posts: 5

Here is that graph I promised of gradient versus initial conditions density (number of black squares out of 40).

Attachment: gradientvinput.pdf
This has been downloaded 408 time(s).

Report this post to a moderator | IP: Logged

Registered: Mar 2007
Posts: 4

Belated reply to comments about my paper ...

Wuensche,A., (1999) "Classifying Cellular Automata Automatically: Finding gliders, filtering, and relating space-time patterns, attractor basins, and the Z parameter", COMPLEXITY, Vol.4/no.3, 47-66, 1999.

"is the classification of a CA rule independent of the initial condition?"

Specific initial condition may give untypical results, so the results are averaged over a sample of initial conditions. Another variable is the number of time-steps before measures start to allow the system to settle into typical behaviour. These and many other issues are described in the paper and other refs.

"suggested to use input-entropy, but also did not provide numerical results."

"Remark to Wuensche: introduces only the method (input entropy) and provides some results for half a dozen CA rules but no largescale investigation."

The paper actually includes results for 1000s of rules, which can be automatically sorted by various criteria. Figures 18 and 19 show sample classifications for 1D binary (v2) CA with different size neighbourhoods (k). The sample sizes are (k5) 17000+, (k6) 15000+, (k7) 14000+. The method relies on entropy-variability, here taken a standard deviation. These and other samples are provided as files for DDLab (www.ddlab.org) which can be loaded and the rules examined and run, by clicking on the scatter plot.

In Wuensche,A., (2011), "Exploring Discrete Dynamics; The DDLab Manual", Luniver Press, UK, 2011 (http://www.sussex.ac.uk/Users/andyw/EDDreviews.html) chapter 33 "Classifying rule space" describes how the method is applied in DDLab, so anyone can create their own unique classified, sorted sample. The chapter gives examples consisting of samples of up to 230000 rules, classifying different types of totalistic rule (also provided as files for DDLab).

Note that input variability is here taken a min-max measure (the maximum up-slope found so far) -- a more effective measure. A sample can also be biased according to the lambda parameter -- an uneven distribution of values in the rule-table is more likely to result in complex dynamics than an unbiased rule-table. Samples of the size mentioned an be created in a few hours -- or leave your laptop running overnight.

"If you know of any other paper this method is applied explicitly, please let me know."

Wuensche,A., (2005), "Glider dynamics in 3-value hexagonal cellular automata: the beehive rule"
Int. Journ. of Unconventional Computing, Vol.1, No.4, 2005, 375-398 -- where the CA automatic classification method is applied to 2D v3 totalistic rules.

The method was originally described in
Wuensche,A., (1997) “Attractor Basins of Discrete Networks; Implications on self-organisation
and memory”, Cognitive Science Research Paper 461, Univ. of Sussex, D.Phil thesis.

All refs. are available in pdf at http://www.sussex.ac.uk/Users/andywu/publications.html


regards
Andy Wuensche
Discrete Dynamics Lab

Andy Wuensche has attached this image:

Report this post to a moderator | IP: Logged

Registered: Oct 2012
Posts: 6

Dear Andy,

My name is Adel Sadeq and I have Mphil from University of Sussex in EE (1987). Few years back I came up with an idea which I called “QUANTUM STATISTICAL AUTOMATA” which directly lead to Quantum Mechanics, QFT and maybe even gravity. This system is based on automata which are based on random lines and the rules are automatically generated by allowing you only certain ones based on the inherent characteristic of lines which are only length comparison. In the process each points on 1D axis picks up information about all the other point interpreted as probabilities( which turn out to be Born's rule). Then I interpret the line lengths for each run as energy after normalizing to numbers of random throws. The system produces astonishing results directly connected to QM.

Since these lines are nothing but the end of two points, I am wondering if that connects my system to regular CA or some variant.

Please, I appreciate it if you look at my system and skim the website and give me your thoughts. Thank you very much. The website is in the first post of this thread,

http://forum.wolframscience.com/sho...p?threadid=1932

__________________
“Reality is nothing but a
mathematical structure, literally”

Report this post to a moderator | IP: Logged