Cellular Automata Basics

Cellular Automata

• Cellular automata (CA) are infinite sets of finite automata with spatial organization.
• Proposed in approximately 1950 by von Neumann and Ulam to model biological reproduction.
• A CA is a state machine with a transition function.
• The space is divided into identical elements (cells) with a geometry, defining a neighbourhood.
• Each cell has a finite automaton.
• Input: States of neighboring automata.
• Output: Automaton state.
• Temporal evolution of CA displays successive states of all cells.

Terminology

• Finite automaton → transition function

• State machine

• Spatial organization → space division in identical elements with a geometry

• Neighbourhood → the spatial element and finite automaton = one cell

• Input → states of neighboring automata

• Output → automaton state

• Temporal evolution of CA → successive states of all cells

Properties and Applications

• CAs are capable of universal computation.
• Interesting for modeling spatial collective phenomena: fluid dynamics, diffusion and equilibrium, and forest fires.
• Useful for direct visual observation

A Theory of Reproduction

• If X is an automaton, and φ(X) its description: An automaton A is needed to interpret the description and build a new X.
• But... to ensure autonomy, A would need φ(A) and to interpret its own description.
• Paradox: The entity to make copies of descriptions is still needed.
• The complete self-replicating system comprises three automata (A, B, C)
• A creates automata from their descriptions.
• B copies descriptions.
• C maintains descriptions and supplies them to B and A, along with a joint description φ(A, B, C).

How it Works

• C supplies the description to B.
• B copies the description three times, destroying the original.
• C supplies one copy to A, which creates a new automaton, consuming the description.
• C supplies another copy to the new automaton and keeps the third for further reproduction.

Reproduction System - Integrating Evolution

• Suppose a new automaton D in the system does not affect normal reproduction (A, B, C).
• If there’s a mutation in D (D → D’), the system becomes (A, B, C, D) + φ(A, B, C, D’).
• Offspring becomes (A, B, C, D’) + φ(A, B, C, D’).
• Only mutations on the description affect offspring.

Self-Reproducing System

• Von Neumann with 29 states and ~10^5 cells.
• Codd with 8 states and ~3x10^8 cells.
• Langton with 8 states and 86 cells (not universal).

Main Parameters

• Dimension (d): 1D, 2D, 3D
• Geometry: Quadrangular, hexagonal, triangular
• Number of states (k) in each automaton
• Updating procedure: Synchronous and asynchronous (sequential, fixed/random, or timed).

Neighbourhood Geometry and Radius

• Von Neumann
• Moore
• Margolus

Important Features

• Locality: finite neighbourhood no instantaneous propagation at a distance, excludes synchronous updating
• Reversibility: Each configuration has a unique leading configuration, so the CA can run backwards.
• Uniformity: All cells have the same automaton.
• Commonly found in CA: locality and uniformity

1D Cellular Automata

• Simplest case: two states (k = 2)
• Neighbourhood radius one (r = 1)
• The binary state of each cell depends on its own state and the states of its two neighbors (3 bits).
• Transition function: defines the next cell state based on the current state and its neighbors.
• Possible neighborhood values (0, 0, 0) to (1, 1, 1) and their corresponding output states (0 to 7).

1D Cellular Automata Rules

• 2^8 = 256 possible transition functions.
• Each function is represented by 8 bits (rule).
• Each bit determines the next state of the corresponding neighborhood.
• The neighborhood is the binary configuration corresponding to bit position (0 to 7).

Example Rule (Rule 30)

• rule= 2^1 + 2^2 + 2^3 + 2^4 = 30

Other Example Rule (Rule 22)

• 22 in binary: 00010110
• Next state is 1 for neighborhoods {001, 010, 100}.
• In all other configurations, the next state is 0.

Wolfram Classification

• Empiric classification: by visual observation.
• Evaluates CA dynamics in time and space without external input (initial state defined).
• Classes: Homogeneous/Fixed Point (Class I), Heterogeneous/Periodic (Class II), Chaotic (Class III), Complex (Class IV).

Life Game - Description

• Proposed by John Conway in approximately 1970.
• 2D, square geometry, Moore neighborhood.
• Rule: Survival: A cell survives if it has 2 or 3 alive neighbors.
• Birth: A cell is born if it has exactly 3 alive neighbors.
• Death: A cell dies by overcrowding (4+ neighbors), or isolation (0 or 1 neighbors).

Life Properties

• Totalizing rule: outcome depends only on the number of active neighbors, not their position.
• Very rich behavior, universal computational power (Turing machine).
• Many variants (less interesting).
• "Life" is alive in CAs.

Disclaimer

• 1D CA and Life images shown are not self-organization.
• Updating discipline is synchronous, resulting in instantaneous propagation at a distance (synchronization signal).

Asynchronism

• Mild forms are more realistic.
• Asynchronous cell update: Updated with probability α in each iteration (α ∈ [0, 1]).
• Smooth transition from synchronism (α = 1).
• Small decrease in α significantly changes CA behavior (most become type 1 or random - type 3).
• Other forms of synchronism: sequential (less realistic — fixed, random, fair, unfair); randomized (e.g. N (μ, σ)).