Cellular Automata Metrics

Cellular Automata Metrics

Eleonora Bilotta (University of Calabria, Italy) and Pietro Pantano (University of Calabria, Italy)
DOI: 10.4018/978-1-61520-787-9.ch005

Abstract

There have been many attempts to understand complexity and to represent it in terms of computable quantities. To date, however, these attempts have had little success. Although we find complexity in a broad range of scientific domains, precise definitions escape our grasp (Bak, 1996; Morin, 2001; Prigogine & Stengers, 1984). One of the key models in complexity science is the Cellular Automaton (CA), a class of system in which small changes in the initial conditions or in local rules can provoke unpredictable behavior (Wolfram, 1984; Wolfram, 2002; Langton, 1986; 1990). The key issue, here as in other kinds of complex system, is to discover the rules governing the emergence of complex phenomena. If such rules were known we could use them to model and predict the behavior of complex physical and biological systems. Taking it for granted that complex behavior is the result of interactions among multiple components of a larger system; we can ask a number of fundamental questions.
Chapter Preview
Top

Introduction

There have been many attempts to understand complexity and to represent it in terms of computable quantities. To date, however, these attempts have had little success. Although we find complexity in a broad range of scientific domains, precise definitions escape our grasp (Bak, 1996; Morin, 2001; Prigogine & Stengers, 1984).

One of the key models in complexity science is the Cellular Automaton (CA), a class of system in which small changes in the initial conditions or in local rules can provoke unpredictable behavior (Wolfram, 1984; Wolfram, 2002; Langton, 1986; 1990). The key issue, here as in other kinds of complex system, is to discover the rules governing the emergence of complex phenomena. If such rules were known we could use them to model and predict the behavior of complex physical and biological systems.

Taking it for granted that complex behavior is the result of interactions among multiple components of a larger system; we can ask a number of fundamental questions.

What are the necessary, qualitative and quantitative conditions that have to be met if a system is to produce complex behavior?

Is it possible to measure complex phenomena?

What are the laws of complexity?

The first attempt to classify CAs on the basis of their behavior goes back to Wolfram (1984) whose quadripartite classification is still widely used today. The main limitation of his system is that it is based on phenomenological data (the development of the space-time diagram for the CA) and makes no attempt to identify the rules determining observed behavior. Since Wolfram, several authors have tried to overcome these limitations, offering more precise definitions.

Langton (1986 ) introduces a metric for measuring the complexity of a CA. Unlike Wolfram, who based his classification on CA phenotypes, Langton worked on their genotypes, introducing a metric for CA complexity, based not on pattern but on the rules generating patterns. According to Langton, complexity emerges on the edge of chaos, and requires complex rules to process, store and transmit information during the development of the CA. Metaphorically speaking, it is a fascinating idea. Unfortunately, however, there is little experimental evidence to back it up (Mitchell et al., 1993; 1994). Mitchell and Crutchfield have shown that there exist not one but many edges of chaos. The organization of CA parameter space (the ideal space in which we represent CA rules) is highly complex, and depends closely on the dimensionality of the system and its parameters. It has been shown, furthermore, that this is true not only for discrete dynamic systems (Bilotta et al., 2003) but also for continuous systems (Bilotta et al., 2007a, 2007b, 2007c, 2007d, 2007e, 2007f).

Complete Chapter List

Search this Book:
Reset