Archive for June, 2013

New paper solves and addresses some of Wolfram’s Open Problems in Cellular Automata

Posted in General on June 19th, 2013 by Hector Zenil – Be the first to comment

In a new paper entitled Asymptotic Behaviour and Ratios of Complexity in Cellular Automata Rule Spaces to be published soon by IJBC and available online here, at least 3 open problems in Cellular Automata are solved/addressed. These are related to:

  1. The development of a formal classification of behaviours of cellular automaton
  2. The development of automated ways to find “interesting” cellular automata and
  3. Find ways to estimate the frequencies of different types of cellular automaton behaviour among rule spaces

In Wolfram’s open problems document it reads:

“If one looks at all possible cellular automaton rules, can one make a quantitative estimate of what fraction will show repetitive, nested, etc. behavior? Is there a definite limiting fraction of rules that, say, show nested behavior.”

In the aforementioned paper, a string arguments and numerical answer is given: the fraction of complex cellular automata for increasingly larger rule spaces grows asymptotically to 1. Otherwise said, picking a longer computer program at random has greater chances to produce complex (algorithmic random) behaviour. When the program space is large enough the probability is arbitrarely close to 1. Notice the converse is not true, small program spaces do not necessarely have small fraction of complex behaviour. We show that defining a concept of asymptotic behaviour, complex behaviour dominates among n possible stable behaviours of a single program.

In this paper, we studied the asymptotic behaviour of symbolic computing systems, notably one-dimensional cellular automata (CA), in order to ascertain whether and at what rate the number of complex versus simple rules dominate the rule space for increasing neighbourhood range and number of symbols (or colours), and how different behaviour is distributed in the spaces of different cellular automata formalisms (as applied to elementary and totallistic CA rules). In doing so we defined an enumeration of initial conditions and automatic methods for interesting rules discovery. Using two different measures, Shannon’s block entropy and Kolmogorov complexity, the latter approximated by two different methods (lossless compressibility and block decomposition based on algorithmic probability), we arrive at the same trend of larger complex behavioural fractions. We also advance a notion of asymptotic and limit behaviour for individual rules, both over initial conditions and runtimes, and we provide a formalisation of Wolfram’s classification as a limit function in terms of Kolmogorov complexity.

Among the results, we confirmed preliminary findings reporting a preponderance of complex classes 3 and 4 as the number of symbols (colours) and neighbourhood ranges of these systems increase. We have shown that behaviour is for the most part stable for a given initial condition but that complexity increases in terms of the number of initial configurations and rules space sizes. The rate at which it does so is fast before asymptotically slowing down when approaching compressibility ratio 1 (uncompressibility). Similar results were obtained by using two different measures. One was a block entropy measure normalised and applied to CA space-time diagrams and the other 2 different approximations of Kolmogorov complexity (lossless compression and algorithmic probability). Following this latter, we found at least 2 ECA rule candidates for Class III or IV behaviour that were believed to belong to Class I or II (if you wonder which specific rules, have a look at the paper!).

While the entropy result may be less surprising because the number of possible configurations with more symbols and larger neighbourhood ranges suggests an increase in entropy, the fact that the 3 approaches used to measure complexity in rule spaces (including estimations of a universal and objective measure such as Kolmogorov complexity) yielded the same results provides a robust answer to the question regarding the change of fractions of behaviour and the rate of this change in computer programs for increasing resources where complexity is clearly seen to dominate asymptotically.

To know more about this: