🧠 CA Fundamentals

🎯 What is a Cellular Automaton?

A Cellular Automaton (CA) is a discrete model of computation consisting of a grid of cells, each in one of a finite number of states. At each time step, every cell updates simultaneously based on its own state and the states of its neighbors, according to a fixed rule. Despite their simplicity, CAs can produce astonishingly complex behavior — and some are computationally universal.

Why Cellular Automata Matter

Emergence: Simple rules → complex behavior. Universality: Some CAs are Turing-complete. Parallelism: All cells update simultaneously. Modeling: Physics, biology, chemistry. Visual: Beautiful patterns from simple rules. Foundation: Wolfram's "A New Kind of Science".

📌 Grid of Cells📌 Local Rules📌 Emergence📌 Universality

# Cellular Automata — the big picture
# A CA is a grid of cells that update simultaneously based on local rules.

# CONCEPTUAL OVERVIEW
print("""
=== Cellular Automata ===

A CA consists of:
  1. A grid of cells (1D, 2D, 3D, ...)
  2. A finite set of states per cell
  3. A neighborhood (which cells influence a cell)
  4. A local rule (how states update)

The update is synchronous: all cells update at the same time.

Famous examples:
  - Rule 110 (1D, 2 states, 3 neighbors) — Turing complete!
  - Rule 30 (1D, 2 states, 3 neighbors) — chaotic
  - Game of Life (2D, 2 states, 9 neighbors) — Turing complete
  - Langton's Ant (2D, simple rules) — emergent behavior
""")

# SIMPLE 1D CA IMPLEMENTATION
class ElementaryCA:
    """
    Elementary Cellular Automaton (ECA):
      - 1D grid of cells
      - 2 states: 0 (dead) and 1 (alive)
      - Neighborhood: left, self, right (3 cells)
      - Rule: 8-bit number (0-255)
    """
    def __init__(self, rule_number, width=80, init='single'):
        self.rule = rule_number
        self.width = width
        self.rule_bits = self._parse_rule(rule_number)
        
        if init == 'single':
            self.cells = [0] * width
            self.cells[width // 2] = 1
        elif init == 'random':
            import random
            self.cells = [random.randint(0, 1) for _ in range(width)]
        else:
            self.cells = list(init)
    
    def _parse_rule(self, rule_number):
        """Convert rule number to 8-bit lookup table."""
        bits = []
        for i in range(8):
            bits.append((rule_number >> i) & 1)
        return bits  # Index: 111, 110, 101, 100, 011, 010, 001, 000
    
    def _apply_rule(self, left, center, right):
        """Apply the rule to a 3-cell neighborhood."""
        index = (left << 2) | (center << 1) | right
        return self.rule_bits[index]
    
    def step(self):
        """Advance one time step."""
        new_cells = [0] * self.width
        for i in range(self.width):
            left = self.cells[(i - 1) % self.width]
            center = self.cells[i]
            right = self.cells[(i + 1) % self.width]
            new_cells[i] = self._apply_rule(left, center, right)
        self.cells = new_cells
    
    def run(self, steps):
        """Run for a number of steps, printing each row."""
        for _ in range(steps):
            print(''.join('█' if c else '·' for c in self.cells))
            self.step()
    
    def display(self):
        """Return current state as a string."""
        return ''.join('█' if c else '·' for c in self.cells)


# EXAMPLE: Rule 110 (Turing complete!)
print("=== Rule 110 — The Turing-Complete CA ===")
print("Rule 110 produces complex, Turing-complete behavior.\n")

ca = ElementaryCA(110, width=60, init='single')
ca.run(20)

print("""
Rule 110 is special:
  - It's Turing complete (can simulate any computation)
  - It produces complex, non-repeating patterns
  - It was proved universal by Matthew Cook in 1994
  - It's one of the simplest universal systems known
""")

# KEY PROPERTIES
print("""
=== Key Properties of Cellular Automata ===

1. DISCRETE SPACE
   - Grid of cells (1D, 2D, 3D, ...)
   - Each cell has a finite state

2. DISCRETE TIME
   - Updates happen in discrete steps
   - All cells update simultaneously

3. LOCAL INTERACTION
   - Each cell only sees its neighbors
   - No global communication

4. DETERMINISTIC
   - Rule is fixed and deterministic
   - Same input → same output

5. EMERGENCE
   - Complex behavior from simple rules
   - Global patterns from local interactions

6. UNIVERSALITY
   - Some CAs are Turing complete
   - Rule 110, Game of Life are examples
""")

📐 Formal Definition

🎯 The Formal Model

A cellular automaton is formally defined as a 4-tuple (L, S, N, f) where L is the lattice, S is the state set, N is the neighborhood, and f is the local transition function.

Formal Components

L: Lattice (grid of cells). S: Finite state set. N: Neighborhood (relative offsets). f: Local rule S^|N| → S. Global: F: S^L → S^L. Config: Assignment of states to all cells.

L LatticeS StatesN Neighborhoodf Rule

# Formal definition of Cellular Automata
from dataclasses import dataclass
from typing import Tuple, Callable, List, Set
import itertools

@dataclass
class CellularAutomaton:
    """
    Formal CA: (L, S, N, f)
    
    L: lattice (represented as dimensions)
    S: state set
    N: neighborhood offsets
    f: local transition function
    """
    dimensions: Tuple[int, ...]           # Lattice shape
    states: Set[int]                      # State set S
    neighborhood: List[Tuple[int, ...]]   # N: relative offsets
    rule: Callable                        # f: local rule
    
    def __post_init__(self):
        # Validate neighborhood includes (0,0,...)
        center = tuple(0 for _ in self.dimensions)
        assert center in self.neighborhood, "Neighborhood must include center"
    
    def create_grid(self, init_state=0):
        """Create a grid initialized to init_state."""
        return [[init_state for _ in range(self.dimensions[1])]
                for _ in range(self.dimensions[0])]
    
    def get_neighbors(self, grid, row, col):
        """Get states of neighboring cells."""
        rows, cols = self.dimensions
        neighbors = []
        for dr, dc in self.neighborhood:
            r = (row + dr) % rows  # Toroidal boundary
            c = (col + dc) % cols
            neighbors.append(grid[r][c])
        return neighbors
    
    def step(self, grid):
        """Apply one global update F: S^L → S^L."""
        new_grid = self.create_grid()
        rows, cols = self.dimensions
        for r in range(rows):
            for c in range(cols):
                neighbors = self.get_neighbors(grid, r, c)
                new_grid[r][c] = self.rule(neighbors)
        return new_grid
    
    def run(self, grid, steps):
        """Run for a number of steps."""
        for _ in range(steps):
            grid = self.step(grid)
        return grid


# EXAMPLE: Game of Life as formal CA
print("=== Game of Life (Formal) ===")
print("""
L = 2D grid (infinite or toroidal)
S = {0, 1}  (dead, alive)
N = Moore neighborhood (8 neighbors + self)

Rule f:
  - Live cell with 2 or 3 live neighbors → survives
  - Dead cell with exactly 3 live neighbors → born
  - Otherwise → dies or stays dead
""")

def life_rule(neighbors):
    """Game of Life rule."""
    center = neighbors[4]  # Center is at index 4 in Moore neighborhood
    live_count = sum(neighbors) - center
    if center == 1:
        return 1 if live_count in (2, 3) else 0
    else:
        return 1 if live_count == 3 else 0

# Moore neighborhood offsets
moore = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,0),(0,1),(1,-1),(1,0),(1,1)]

life = CellularAutomaton(
    dimensions=(10, 10),
    states={0, 1},
    neighborhood=moore,
    rule=life_rule
)

# Glider pattern
glider = life.create_grid(0)
glider[0][1] = 1
glider[1][2] = 1
glider[2][0] = 1
glider[2][1] = 1
glider[2][2] = 1

print("Initial state:")
for row in glider:
    print(''.join('█' if c else '·' for c in row))

# Run 4 steps
for step in range(4):
    glider = life.step(glider)

print("\nAfter 4 steps (glider moved):")
for row in glider:
    print(''.join('█' if c else '·' for c in row))


# FORMAL PROPERTIES
print("""
=== Formal Properties ===

1. GLOBAL FUNCTION
   F: S^L → S^L
   F(c)(x) = f(c(x + n_1), ..., c(x + n_k))
   
   where N = {n_1, ..., n_k}

2. CONFIGURATION
   c: L → S
   A configuration assigns a state to each cell.

3. HOMOGENEITY
   Same rule applies everywhere.
   No cell is special.

4. LOCALITY
   f depends only on neighborhood.
   No action at a distance.

5. SYNCHRONICITY
   All cells update simultaneously.
   No update order ambiguity.

6. DETERMINISM
   f is a function (not a relation).
   Same input → same output.
""")

🔧 Components

🎯 The Building Blocks

Every cellular automaton has four essential components: the lattice, the state set, the neighborhood, and the local rule. Understanding each is key to designing and analyzing CAs.

Component Details

Lattice: 1D, 2D, 3D, or nD grid. States: Binary, ternary, or more. Neighborhood: Von Neumann, Moore, or custom. Rule: Lookup table or function. Boundary: Finite, periodic, or infinite. Initial: Single cell, random, or pattern.

🔲 Lattice🎨 States🏘️ Neighborhood📏 Rule

# Components of Cellular Automata
print("=== 1. LATTICE (L) ===")
print("""
The lattice is the grid of cells:

1D: line of cells
    □ □ □ □ □ □ □ □ □

2D: square grid
    □ □ □ □ □
    □ □ □ □ □
    □ □ □ □ □

3D: cubic grid
    (layers of 2D grids)

Other: hexagonal, triangular, irregular

Boundary conditions:
  - Finite: edges are fixed
  - Periodic: wrap around (toroidal)
  - Infinite: theoretical ideal
""")

print("\n=== 2. STATE SET (S) ===")
print("""
Each cell has a state from a finite set:

Binary: S = {0, 1}
  - Simplest
  - Rule 110, Game of Life

Ternary: S = {0, 1, 2}
  - More complex behavior

n-ary: S = {0, 1, ..., n-1}
  - More states = more complexity

Continuous: S = [0, 1]
  - Continuous CA (e.g., Lenia)

The state set determines:
  - Number of possible configurations
  - Complexity of the rule
  - Richness of behavior
""")

print("\n=== 3. NEIGHBORHOOD (N) ===")
print("""
Which cells influence a given cell:

Von Neumann (4 neighbors in 2D):
    □
  □ ■ □
    □

Moore (8 neighbors in 2D):
  □ □ □
  □ ■ □
  □ □ □

Extended: radius > 1
  □ □ □ □ □
  □ □ □ □ □
  □ □ ■ □ □
  □ □ □ □ □
  □ □ □ □ □

1D: radius 1 = {left, self, right}
    □ ■ □

Custom: any set of offsets
""")

print("\n=== 4. LOCAL RULE (f) ===")
print("""
The rule maps neighborhood states to new state:

f: S^|N| → S

For binary 1D CA with radius 1:
  |N| = 3, so 2^3 = 8 possible neighborhoods
  Rule is a lookup table with 8 entries
  Total possible rules: 2^8 = 256

For Game of Life:
  |N| = 9 (Moore + center)
  But rule is based on count, not exact configuration
  Much simpler than 2^9 = 512 entries

Rule representations:
  - Lookup table (explicit)
  - Formula (compact)
  - Count-based (Game of Life)
""")

# IMPLEMENTATION
print("\n=== Implementation: Components ===")

class CAComponents:
    """Demonstrate CA components."""
    def __init__(self, lattice_type, states, neighborhood, rule):
        self.lattice_type = lattice_type
        self.states = states
        self.neighborhood = neighborhood
        self.rule = rule
    
    def describe(self):
        return f"""
CA Components:
  Lattice: {self.lattice_type}
  States: {self.states}
  Neighborhood: {self.neighborhood}
  Rule: {self.rule}
"""

# Example: Rule 110 components
rule110 = CAComponents(
    lattice_type="1D, infinite",
    states="{0, 1}",
    neighborhood="{-1, 0, +1} (radius 1)",
    rule="Lookup table (8 entries)"
)
print(rule110.describe())

# Example: Game of Life components
life = CAComponents(
    lattice_type="2D, infinite",
    states="{0, 1}",
    neighborhood="Moore (8 neighbors + self)",
    rule="Count-based (2-3 survive, 3 born)"
)
print(life.describe())

# VISUALIZATION
print("=== Visual Comparison ===")
print("""
1D CA (Rule 110):
  Time →
  □ ■ □ □ □ □ □ □   t=0
  ■ ■ ■ □ □ □ □ □   t=1
  ■ ■ ■ ■ □ □ □ □   t=2
  ■ □ □ ■ ■ □ □ □   t=3
  ...

2D CA (Game of Life):
  □ □ □ □ □ □ □ □
  □ □ ■ □ □ □ □ □
  □ □ □ ■ □ □ □ □
  □ ■ ■ ■ □ □ □ □
  □ □ □ □ □ □ □ □
  (glider moving diagonally)
""")

🏘️ Neighborhoods

🎯 Who Influences Whom

The neighborhood determines which cells affect a given cell's next state. Common neighborhoods include Von Neumann (4-neighbor), Moore (8-neighbor), and extended radius versions.

Neighborhood Types

Von Neumann: 4 neighbors (N,S,E,W). Moore: 8 neighbors (all surrounding). Extended: Radius > 1. Custom: Arbitrary offsets. 1D: Left, self, right. Hexagonal: 6 neighbors.

🔲 Von Neumann🔳 Moore🔘 Extended⚙️ Custom

# Neighborhoods in Cellular Automata
print("=== 1D Neighborhoods ===")
print("""
Radius 1: {left, self, right}
  □ ■ □

Radius 2: {left2, left1, self, right1, right2}
  □ □ ■ □ □Radius r: 2r+1 cells
""")

print("\n=== 2D Neighborhoods ===")
print("""
Von Neumann (4 neighbors):
    □
  □ ■ □
    □

Moore (8 neighbors):
  □ □ □
  □ ■ □
  □ □ □

Extended Von Neumann (radius 2):
      □
      □
  □ □ ■ □ □
      □
      □

Extended Moore (radius 2):
  □ □ □ □ □
  □ □ □ □ □
  □ □ ■ □ □
  □ □ □ □ □
  □ □ □ □ □
""")

print("\n=== 3D Neighborhoods ===")
print("""
3D Von Neumann (6 neighbors):
  ±x, ±y, ±z

3D Moore (26 neighbors):
  All surrounding cells

3D Extended:
  Larger radius
""")

# NEIGHBORHOOD IMPLEMENTATIONS
def von_neumann_2d(radius=1):
    """Generate Von Neumann neighborhood offsets."""
    offsets = []
    for dr in range(-radius, radius + 1):
        for dc in range(-radius, radius + 1):
            if abs(dr) + abs(dc) <= radius:
                offsets.append((dr, dc))
    return offsets

def moore_2d(radius=1):
    """Generate Moore neighborhood offsets."""
    offsets = []
    for dr in range(-radius, radius + 1):
        for dc in range(-radius, radius + 1):
            offsets.append((dr, dc))
    return offsets

print("=== Neighborhood Sizes ===")
for r in [1, 2, 3]:
    vn = von_neumann_2d(r)
    moore = moore_2d(r)
    print(f"Radius {r}: Von Neumann = {len(vn)}, Moore = {len(moore)}")

# VISUALIZATION FUNCTION
def visualize_neighborhood(offsets, size=5):
    """Visualize a neighborhood as ASCII grid."""
    grid = [['·' for _ in range(size)] for _ in range(size)]
    center = size // 2
    for dr, dc in offsets:
        r, c = center + dr, center + dc
        if 0 <= r < size and 0 <= c < size:
            if dr == 0 and dc == 0:
                grid[r][c] = '■'
            else:
                grid[r][c] = '□'
    return '\n'.join(''.join(row) for row in grid)

print("\n=== Von Neumann (radius 1) ===")
print(visualize_neighborhood(von_neumann_2d(1)))

print("\n=== Moore (radius 1) ===")
print(visualize_neighborhood(moore_2d(1)))

print("\n=== Extended Moore (radius 2) ===")
print(visualize_neighborhood(moore_2d(2)))

# EFFECTS OF NEIGHBORHOOD SIZE
print("\n=== Effect of Neighborhood Size ===")
print("""
Larger neighborhood:
  + More information available
  + Can produce more complex behavior
  - Larger rule table (exponential)
  - Slower simulation

For binary CA:
  |N| = k → rule table size = 2^(2^k)

  k=3 (1D radius 1): 2^8 = 256 rules
  k=5 (1D radius 2): 2^32 ≈ 4 billion rules
  k=9 (2D Moore): 2^512 rules (impossible to enumerate)
  
So 2D CA rules are usually formula-based, not table-based.
""")

# PRACTICAL EXAMPLE
print("\n=== Practical Example: Game of Life Neighborhood ===")
print("""
Game of Life uses Moore neighborhood (8 neighbors + self):

  For each cell, count live neighbors:
    live_count = sum of 8 neighbors (excluding self)

  Rule:
    If alive and live_count in {2, 3}: stay alive
    If dead and live_count == 3: become alive
    Otherwise: dead

This simple count-based rule produces:
  - Gliders (moving patterns)
  - Oscillators (periodic patterns)
  - Still lifes (stable patterns)
  - Turing-complete computation!
""")

📏 Rule Tables

🎯 The Heart of a CA

The rule determines how a cell's state changes based on its neighborhood. For elementary CAs, the rule is an 8-bit number (0-255). For complex CAs, rules are formulas or count-based functions.

Rule Representations

Lookup table: Explicit mapping. Rule number: 8-bit integer. Formula: Mathematical expression. Count-based: Based on neighbor count. Totalistic: Depends on sum only. Outer-totalistic: Sum + center state.

📋 Lookup🔢 Rule Number📐 Formula🔢 Count-based

# Rule tables in Cellular Automata
print("=== Elementary CA Rules (1D, binary, radius 1) ===")
print("""
There are 2^8 = 256 possible elementary rules.

Each rule is defined by 8 outputs for the 8 possible neighborhoods:

  Neighborhood:  111  110  101  100  011  010  001  000
  Output:         ?    ?    ?    ?    ?    ?    ?    ?

Rule number = binary number formed by outputs
Example: Rule 110
  01101110 in binary = 110 in decimal

  Neighborhood:  111  110  101  100  011  010  001  000
  Output:         0    1    1    0    1    1    1    0
""")

# RULE TABLE IMPLEMENTATION
class RuleTable:
    """Elementary CA rule table."""
    def __init__(self, rule_number):
        self.rule_number = rule_number
        self.table = {}
        for i in range(8):
            neighborhood = format(i, '03b')
            output = (rule_number >> i) & 1
            self.table[neighborhood] = output
    
    def apply(self, left, center, right):
        key = f"{left}{center}{right}"
        return self.table[key]
    
    def display(self):
        print(f"Rule {self.rule_number}:")
        print("  Neighborhood | Output")
        print("  -------------|-------")
        for i in range(7, -1, -1):
            neighborhood = format(i, '03b')
            print(f"  {neighborhood}        | {self.table[neighborhood]}")


print("\n=== Rule 110 Table ===")
rule110 = RuleTable(110)
rule110.display()

print("\n=== Rule 30 Table ===")
rule30 = RuleTable(30)
rule30.display()

print("\n=== Rule 90 Table ===")
rule90 = RuleTable(90)
rule90.display()

# TOTALISTIC RULES
print("\n=== Totalistic Rules ===")
print("""
Totalistic rules depend only on the SUM of neighborhood states,
not their positions.

For 2D CA with Moore neighborhood:
  Sum ranges from 0 to 8 (9 possible values)

Rule is defined by 9 outputs:
  Sum:   0  1  2  3  4  5  6  7  8
  Out:   ?  ?  ?  ?  ?  ?  ?  ?  ?

Example: Game of Life is outer-totalistic:
  Depends on sum AND center state.

Game of Life rule table:
  Center=0 (dead):
    Sum=3 → 1 (born)
    Other → 0 (stay dead)
  Center=1 (alive):
    Sum=2 or 3 → 1 (survive)
    Other → 0 (die)
""")

# GAME OF LIFE RULE TABLE
print("\n=== Game of Life Rule Table ===")
print("  Center | Sum | Next")
print("  -------|-----|-----")
for center in [0, 1]:
    for s in range(9):
        if center == 0:
            next_state = 1 if s == 3 else 0
        else:
            next_state = 1 if s in (2, 3) else 0
        print(f"    {center}    |  {s}  |  {next_state}")

# RULE SPACE
print("\n=== Rule Space ===")
print("""
Number of possible rules:

1D binary, radius 1:
  2^(2^3) = 2^8 = 256

1D binary, radius 2:
  2^(2^5) = 2^32 ≈ 4.3 billion

2D binary, Moore:
  2^(2^9) = 2^512 ≈ 10^154

2D binary, Von Neumann:
  2^(2^5) = 2^32 ≈ 4.3 billion

3D binary, Moore:
  2^(2^27) = 2^134 million — astronomical

So most interesting 2D/3D CAs use formulas or totalistic rules.
""")

# RULE EXPLORATION
print("\n=== Exploring Elementary Rules ===")
print("""
Wolfram classified 256 elementary rules into 4 classes:

Class 1: Homogeneous (uniform)
  Rule 0, 8, 32, 128, 136, 160, 168, 200, 224, 232, 240
  → All cells become same state

Class 2: Stable/periodic
  Rule 4, 108, 184, ...
  → Simple repeating patterns

Class 3: Chaotic
  Rule 30, 45, 60, 75, 86, 89, 101, 105, 135, 149, 153, 165, 180, 195
  → Random-looking, aperiodic

Class 4: Complex (edge of chaos)
  Rule 110, 124, 137, 193, ...
  → Complex structures, computation
""")

# DEMONSTRATION
print("\n=== Demonstration: Different Rules ===")

def demo_rule(rule_num, width=40, steps=8):
    """Demonstrate an elementary CA rule."""
    print(f"\nRule {rule_num}:")
    ca = ElementaryCA(rule_num, width=width, init='single')
    ca.run(steps)

# Show a few interesting rules
for rule in [30, 90, 110]:
    demo_rule(rule, width=40, steps=8)
    print()

1️⃣ Elementary CA (Rule 110)

🎯 The Simplest Universal CA

Rule 110 is an elementary cellular automaton that is Turing complete — it can perform any computation. It was proved universal by Matthew Cook in 1994, making it one of the simplest known universal systems.

Rule 110 Properties

1D: One-dimensional grid. Binary: Two states (0, 1). Radius 1: Three-cell neighborhood. Rule 110: 01101110 in binary. Universal: Turing complete. Gliders: Moving structures.

1️⃣ 1D🔢 Binary🏘️ Radius 1💻 Universal

# Rule 110 — the Turing-complete elementary CA
class Rule110:
    """
    Rule 110: 01101110 in binary = 110
    
    Neighborhood → Output:
      111 → 0
      110 → 1
      101 → 1
      100 → 0
      011 → 1
      010 → 1
      001 → 1
      000 → 0
    """
    def __init__(self, width=100, init='single'):
        self.width = width
        if init == 'single':
            self.cells = [0] * width
            self.cells[width // 2] = 1
        elif init == 'random':
            import random
            self.cells = [random.randint(0, 1) for _ in range(width)]
        else:
            self.cells = list(init)
    
    def step(self):
        new_cells = [0] * self.width
        for i in range(self.width):
            left = self.cells[(i - 1) % self.width]
            center = self.cells[i]
            right = self.cells[(i + 1) % self.width]
            
            # Rule 110 lookup
            pattern = (left << 2) | (center << 1) | right
            # Patterns: 111=7, 110=6, 101=5, 100=4, 011=3, 010=2, 001=1, 000=0
            # Outputs:   0,      1,      1,      0,      1,      1,      1,      0
            outputs = [0, 1, 1, 1, 0, 1, 1, 0]  # index 0 to 7
            new_cells[i] = outputs[pattern]
        
        self.cells = new_cells
    
    def run(self, steps, display=True):
        for _ in range(steps):
            if display:
                print(''.join('█' if c else '·' for c in self.cells))
            self.step()
    
    def display(self):
        return ''.join('█' if c else '·' for c in self.cells)


print("=== Rule 110 from Single Cell ===")
ca = Rule110(width=60)
ca.run(20)

print("""
Rule 110 produces:
  - Triangular patterns (like Rule 90)
  - But also complex, non-repeating structures
  - Gliders that move and interact
  - Turing-complete computation
""")

# GLIDERS IN RULE 110
print("=== Gliders in Rule 110 ===")
print("""
Rule 110 supports several types of gliders:

1. Left-moving glider
2. Right-moving glider
3. Collisions produce new gliders

These gliders are the basis for computation:
  - Glider = signal
  - Collision = logic gate
  - Arrangement = program

This is similar to how Game of Life computes.
""")

# UNIVERSALITY
print("\n=== Universality of Rule 110 ===")
print("""
Matthew Cook (1994) proved Rule 110 is Turing complete.

Proof idea:
  1. Show Rule 110 can simulate a cyclic tag system
  2. Cyclic tag systems are Turing complete
  3. Therefore Rule 110 is Turing complete

Cyclic tag system:
  - A finite list of strings
  - At each step, process the first string
  - Append it to the end if first symbol is 1
  - Delete first symbol
  - Rotate to next string

Rule 110 can emulate this with gliders.

Implications:
  - Rule 110 can compute anything computable
  - It's one of the simplest universal systems
  - Universality can emerge from simple rules
""")

# DEMONSTRATION
print("\n=== Rule 110 Computation Demo ===")
print("""
Setting up a computation in Rule 110:

  Initial:  00000000000000000000000000000000
            00000000000000000000000000000000
            00000000000000000000000000000000
            ...

  Gliders move and interact.
  Collisions implement logic gates.
  The result is the computation output.

This is hard to see in ASCII,
but the principle is the same as Game of Life.
""")

# COMPARISON WITH OTHER RULES
print("\n=== Rule 110 vs Other Rules ===")
print(f"{'Rule':<10} {'Class':<10} {'Behavior':<40}")
print("-" * 60)
print(f"{'0':<10} {'1':<10} {'All cells → 0 (uniform)':<40}")
print(f"{'30':<10} {'3':<10} {'Chaotic, random-looking':<40}")
print(f"{'90':<10} {'2':<10} {'Sierpinski triangle (fractal)':<40}")
print(f"{'110':<10} {'4':<10} {'Complex, Turing complete':<40}")
print(f"{'184':<10} {'2':<10} {'Traffic flow model':<40}")
print(f"{'255':<10} {'1':<10} {'All cells → 1 (uniform)':<40}")

# SIERPINSKI TRIANGLE (RULE 90)
print("\n=== Rule 90 — Sierpinski Triangle ===")
ca90 = ElementaryCA(90, width=60, init='single')
ca90.run(15)

print("""
Rule 90 produces the Sierpinski triangle:
  - Fractal pattern
  - Self-similar at all scales
  - Equivalent to Pascal's triangle mod 2

Rule 90 XOR rule: new = left XOR right
""")

🎮 Game of Life

🎯 The Most Famous 2D CA

Conway's Game of Life is a 2D cellular automaton with binary states and a Moore neighborhood. Despite its simple rules, it is Turing complete and produces incredibly complex behavior including gliders, oscillators, and self-replicating patterns.

Game of Life Rules

Birth: Dead cell with exactly 3 live neighbors → alive. Survival: Live cell with 2 or 3 live neighbors → survives. Death: Otherwise → dead. Neighborhood: Moore (8 neighbors). Universal: Turing complete. Patterns: Gliders, oscillators, guns.

🎮 2D Grid🔢 Binary🏘️ Moore💻 Universal

# Conway's Game of Life — full implementation
import random

class GameOfLife:
    """
    Conway's Game of Life:
      - 2D grid
      - Binary states (0=dead, 1=alive)
      - Moore neighborhood (8 neighbors)
      
    Rules:
      1. Birth: dead cell with exactly 3 live neighbors → alive
      2. Survival: live cell with 2 or 3 live neighbors → survives
      3. Death: otherwise → dead
    """
    def __init__(self, rows=20, cols=40, init='random', density=0.3):
        self.rows = rows
        self.cols = cols
        
        if init == 'random':
            self.grid = [[1 if random.random() < density else 0 
                         for _ in range(cols)] 
                        for _ in range(rows)]
        elif init == 'glider':
            self.grid = self.create_grid(0)
            # Glider at top-left
            self.grid[1][2] = 1
            self.grid[2][3] = 1
            self.grid[3][1] = 1
            self.grid[3][2] = 1
            self.grid[3][3] = 1
        else:
            self.grid = self.create_grid(0)
    
    def create_grid(self, value=0):
        return [[value for _ in range(self.cols)] for _ in range(self.rows)]
    
    def count_neighbors(self, r, c):
        """Count live neighbors (Moore neighborhood)."""
        count = 0
        for dr in [-1, 0, 1]:
            for dc in [-1, 0, 1]:
                if dr == 0 and dc == 0:
                    continue
                nr = (r + dr) % self.rows
                nc = (c + dc) % self.cols
                count += self.grid[nr][nc]
        return count
    
    def step(self):
        """Apply one generation."""
        new_grid = self.create_grid(0)
        for r in range(self.rows):
            for c in range(self.cols):
                neighbors = self.count_neighbors(r, c)
                
                if self.grid[r][c] == 1:
                    # Alive: survive if 2 or 3 neighbors
                    new_grid[r][c] = 1 if neighbors in (2, 3) else 0
                else:
                    # Dead: born if exactly 3 neighbors
                    new_grid[r][c] = 1 if neighbors == 3 else 0
        
        self.grid = new_grid
    
    def display(self):
        """ASCII display."""
        for row in self.grid:
            print(''.join('█' if c else '·' for c in row))
    
    def run(self, steps, delay=0):
        """Run for a number of steps."""
        import time
        for _ in range(steps):
            print('\033[2J\033[H')  # Clear screen
            self.display()
            time.sleep(delay)
            self.step()


# DEMONSTRATION
print("=== Game of Life — Glider ===")
life = GameOfLife(10, 20, init='glider')

for step in range(5):
    print(f"Step {step}:")
    life.display()
    print()
    life.step()

# FAMOUS PATTERNS
print("=== Famous Game of Life Patterns ===")
print("""
1. GLIDER (moves diagonally)
   ·█·
   ··█
   ███
   → Moves 1 cell diagonally every 4 generations

2. BLINKER (period 2 oscillator)
   ···
   ███
   ···
   → Oscillates between horizontal and vertical

3. BLOCK (still life)
   ██
   ██
   → Never changes

4. PULSAR (period 3 oscillator)
   Large, beautiful oscillation

5. GOSPER GLIDER GUN (creates gliders)
   → Period 30, emits gliders indefinitely

6. BREEDER (creates guns)
   → Exponential growth

7. SPACESHIP (moves)
   → Various speeds and directions
""")

# GLIDER GUN
print("\n=== Gosper Glider Gun ===")
print("""
The Gosper Glider Gun creates a stream of gliders:

  ██████████
  ██████████
  ...
  (complex pattern that emits gliders)

This was the first known finite pattern with unbounded growth.
It proves Game of Life can create infinite complexity.
""")

# UNIVERSALITY
print("\n=== Universality of Game of Life ===")
print("""
Game of Life is Turing complete.

Proof:
  1. Gliders can carry signals
  2. Collisions can implement logic gates
  3. Logic gates can build a computer
  4. Therefore, Game of Life can compute anything

Components:
  - Glider = signal
  - Glider collision = logic gate (AND, OR, NOT)
  - Glider gun = clock
  - Memory = stable patterns
  - Program = arrangement of gliders and guns

This was proved by John von Neumann (1960s) and others.
""")

# COMPUTATION IN LIFE
print("\n=== Computation in Game of Life ===")
print("""
People have built:
  - Logic gates (AND, OR, NOT, XOR)
  - Adders, multipliers
  - Memory (RAM)
  - Clocks (glider guns)
  - A working computer (Turing complete)
  - Even a Game of Life simulator inside Game of Life!

This is called "Life in Life" — a meta-circular implementation.

The fact that simple rules can compute anything
is one of the deepest insights in computer science.
""")

# LARGER DEMO
print("\n=== Larger Demo: Glider Gun ===")
print("""
(Note: This requires a larger grid to see properly.)

The Gosper Glider Gun is a pattern that:
  - Has 36 live cells
  - Period 30
  - Emits a glider every 30 generations
  - Creates unbounded growth

It's the simplest known gun.
""")

# IMPLEMENTATION DETAILS
print("\n=== Implementation Details ===")
print("""
Key optimizations:
  1. Sparse representation (set of live cells)
  2. Hashlife algorithm (for large patterns)
  3. GPU acceleration
  4. Parallel processing

Hashlife:
  - Uses quadtrees to represent patterns
  - Exploits self-similarity
  - Can simulate exponentially large patterns
  - Bill Gosper's algorithm (1980s)
""")

📊 Wolfram Classification

🎯 Four Classes of CA Behavior

Stephen Wolfram classified cellular automata into four classes based on their behavior: homogeneous, periodic, chaotic, and complex. This classification helps understand the spectrum from simple to universal behavior.

The Four Classes

Class 1: Homogeneous → uniform. Class 2: Periodic → repeating. Class 3: Chaotic → random. Class 4: Complex → universal. Edge of chaos: Class 4. Computation: Only Class 4.

1️⃣ Homogeneous2️⃣ Periodic3️⃣ Chaotic4️⃣ Complex

# Wolfram's classification of cellular automata
print("=== Wolfram's Four Classes ===")
print("""
Stephen Wolfram (1980s) classified CA behavior into 4 classes:

Class 1: HOMOGENEOUS
  - All cells eventually reach same state
  - Behavior dies out or becomes uniform
  - Example: Rule 0, Rule 255
  
Class 2: PERIODIC
  - Simple repeating patterns
  - Local structures, periodic in time
  - Example: Rule 90 (Sierpinski), Rule 184
  
Class 3: CHAOTIC
  - Random-looking, aperiodic
  - Statistical properties like random noise
  - Example: Rule 30, Rule 45
  
Class 4: COMPLEX
  - Complex structures, long-range interactions
  - Edge of chaos
  - Turing complete!
  - Example: Rule 110, Game of Life
""")

# DEMONSTRATION
def classify_rule(rule_num, width=60, steps=20):
    """Show behavior of a rule and classify it."""
    print(f"\nRule {rule_num}:")
    ca = ElementaryCA(rule_num, width=width, init='random')
    
    # Run and observe
    for _ in range(steps):
        ca.step()
    
    # Simple heuristic classification
    # (In practice, classification is more nuanced)
    diversity = len(set(ca.cells))
    if diversity == 1:
        return "Class 1 (homogeneous)"
    elif diversity <= 3:
        return "Class 2 (periodic)"
    else:
        return "Class 3 or 4 (chaotic/complex)"

# Show examples
print("=== Classification Examples ===")
for rule in [0, 90, 30, 110]:
    ca = ElementaryCA(rule, width=60, init='random')
    for _ in range(15):
        ca.step()
    
    # Analyze
    ones = sum(ca.cells)
    diversity = len(set(ca.cells))
    
    print(f"\nRule {rule}:")
    print(f"  Ones: {ones}/{len(ca.cells)}")
    print(f"  Diversity: {diversity}")
    print(f"  Sample: {ca.display()[:40]}...")

# DETAILED CLASS DESCRIPTIONS
print("\n=== Detailed Class Descriptions ===")
print("""
CLASS 1: HOMOGENEOUS
  - After finite time, all cells same state
  - No interesting behavior
  - Examples: Rule 0, 8, 32, 128, 136, 160, 168, 200, 224, 232, 240
  
  Visual:
    ████████████████  (all 1)
    ████████████████
    ████████████████

CLASS 2: PERIODIC
  - Stable or periodic structures
  - Local changes don't propagate far
  - Examples: Rule 4, 108, 184
  
  Visual:
    ██··██··██··██··
    ··██··██··██··██
    ██··██··██··██··
    ··██··██··██··██

CLASS 3: CHAOTIC
  - Aperiodic, random-looking
  - Sensitive to initial conditions
  - Examples: Rule 30, 45, 60, 75, 86, 89, 101, 105
  
  Visual:
    █·██·█··██··█·██
    ·████·██·███·██·
    ██···████··█··██
    ·██·██···███·██·

CLASS 4: COMPLEX
  - Complex structures, gliders
  - Long-range interactions
  - Turing complete
  - Examples: Rule 110, 124, 137, 193
  
  Visual:
    █··█·██·█··██·█·
    ·███·████·██·██·
    █···█···████··█·
    ·█·███·██···██·█
""")

# WOLFRAM'S INSIGHT
print("\n=== Wolfram's Insight ===")
print("""
From "A New Kind of Science" (2002):

1. SIMPLE RULES → COMPLEX BEHAVIOR
   Even elementary rules can be universal.

2. CLASS 4 IS SPECIAL
   Only Class 4 supports computation.
   It's at the "edge of chaos."

3. UNIVERSALITY IS COMMON
   Many simple systems are universal.
   Rule 110, Game of Life, etc.

4. COMPUTATIONAL EQUIVALENCE
   All universal systems are equivalent.
   They can simulate each other.

5. NATURE USES CA
   Wolfram argues nature computes with CA-like rules.
   Physics, biology, etc.
""")

# CLASS 4 AND COMPUTATION
print("\n=== Class 4 and Computation ===")
print("""
Why is Class 4 special?

1. INFORMATION PRESERVATION
   Class 3 destroys information (chaos).
   Class 1, 2 lose information (uniform/periodic).
   Class 4 preserves and transmits information.

2. GLIDERS
   Class 4 supports gliders (moving structures).
   Gliders carry information.
   Collisions process information.

3. UNIVERSALITY
   Class 4 systems are Turing complete.
   They can compute anything computable.

4. EDGE OF CHAOS
   Class 4 is between order (Class 2) and chaos (Class 3).
   This is where computation happens.

Quote from Wolfram:
  "Class 4 behavior is the most sophisticated.
   It's what we see in systems that can compute."
""")

# VISUALIZATION
print("\n=== Visual Classification ===")
print("""
Class 1:    ████████████  (uniform)
            ████████████
            ████████████

Class 2:    ██··██··██··  (periodic)
            ··██··██··██
            ██··██··██··
            ··██··██··██

Class 3:    █·██·█··██··  (chaotic)
            ·████·██·███
            ██···████··█
            ·██·██···███

Class 4:    █··█·██·█··█  (complex)
            ·███·████·██
            █···█···████
            ·█·███·██···
""")

💻 Computation Universality

🎯 When CAs Can Compute Anything

Some cellular automata are Turing complete — they can simulate any Turing machine and thus compute any computable function. Rule 110 and Game of Life are the most famous examples.

Universal Computation

Turing complete: Can simulate any TM. Rule 110: Universal (Cook 1994). Game of Life: Universal (Conway 1970s). Gliders: Signals. Collisions: Logic gates. Arrangements: Programs.

💻 Turing Complete🏃 Gliders🔗 Collisions📝 Programs

# Computation universality in Cellular Automata
print("=== What is Universality? ===")
print("""
A system is Turing complete if it can:
  1. Simulate any Turing machine
  2. Compute any computable function

For CA, this means:
  - The CA can encode a TM
  - The CA can simulate the TM's computation
  - The result is readable from the CA state

Famous universal CAs:
  - Rule 110 (1D, 2 states)
  - Game of Life (2D, 2 states)
  - Von Neumann's self-replicating CA (2D, 29 states)
""")

# UNIVERSALITY IN RULE 110
print("\n=== Universality in Rule 110 ===")
print("""
Matthew Cook's proof (1994):

1. Rule 110 supports gliders
   - Left-moving gliders
   - Right-moving gliders
   - Collisions produce logic gates

2. Gliders can encode a cyclic tag system
   - Cyclic tag systems are Turing complete
   - Rule 110 can simulate any cyclic tag system

3. Therefore, Rule 110 is Turing complete

Details:
  - Glider = symbol in tag system
  - Collision = processing step
  - Arrangement = program

This was a major result:
  - One of the simplest universal systems
  - Only 2 states, 3-cell neighborhood
  - Proves universality can be very simple
""")

# UNIVERSALITY IN GAME OF LIFE
print("\n=== Universality in Game of Life ===")
print("""
Game of Life is Turing complete.

Components:
  1. Glider = signal (1 bit)
  2. Glider collision = logic gate
  3. Glider gun = clock
  4. Stable patterns = memory
  5. Arrangement = program

Logic gates:
  - AND gate: two gliders collide → one output
  - OR gate: gliders merge
  - NOT gate: glider blocked
  - XOR gate: gliders interact

Building a computer:
  1. Build logic gates from gliders
  2. Build adders, registers
  3. Build CPU
  4. Build RAM
  5. Write program

People have literally built:
  - Working computers in Game of Life
  - A Game of Life simulator in Game of Life
""")

# VON NEUMANN'S SELF-REPLICATING CA
print("\n=== Von Neumann's Self-Replicating CA ===")
print("""
John von Neumann (1940s-50s) designed a CA that can:
  - Self-replicate
  - Universal computation
  - Evolve complexity

Specifications:
  - 2D grid
  - 29 states
  - Complex but universal

Significance:
  - Proved self-replication is possible
  - Foundation of artificial life
  - Inspired later work (Langton's Loops)

Later simplifications:
  - Codd's CA (8 states)
  - Langton's Loops (8 states)
  - Banks' CA (2 states, but more complex rules)
""")

# COMPUTATION IN CA
print("\n=== How Computation Works in CA ===")
print("""
1. ENCODING INPUT
   - Represent input as initial pattern
   - Gliders, blocks, etc.

2. PROCESSING
   - CA evolves according to rules
   - Local interactions compute

3. READING OUTPUT
   - Final pattern encodes result
   - Gliders, stable structures, etc.

Example: Adding two numbers in Game of Life
  1. Encode numbers as glider streams
  2. Build an adder from glider collisions
  3. Let it run
  4. Read result from output gliders

This is slow but proves the principle.
""")

# PRACTICAL COMPUTATION
print("\n=== Practical Computation in CA ===")
print("""
While universal, CAs are not practical for computation:

Speed:
  - Game of Life: ~1 operation per second (in real time)
  - Modern CPU: ~10^9 operations per second

Size:
  - A simple adder: thousands of cells
  - A CPU: millions of cells

Why study then?
  1. Theoretical insight
  2. Understand computation limits
  3. Model natural systems
  4. Artificial life
  5. Parallel computation
""")

# UNIVERSALITY THRESHOLD
print("\n=== Universality Threshold ===")
print("""
How simple can a universal CA be?

1D, 2 states:
  - Rule 110 is universal (radius 1)
  - Only 8 possible neighborhoods
  - 256 rules total

2D, 2 states:
  - Game of Life is universal (Moore neighborhood)
  - Count-based rule (not full table)

Can we go simpler?
  - 1D, 2 states, radius 1: Rule 110 is minimal
  - Any simpler is probably not universal

This suggests:
  - Universality requires a minimum complexity
  - But that minimum is very low
  - Simple rules can compute anything
""")

🔄 Reversible CA

🎯 Time-Reversible Computation

A reversible cellular automaton is one where every state has a unique predecessor. The evolution can be run backwards — no information is lost. This connects to fundamental physics and reversible computing.

Reversibility

Definition: Every state has unique predecessor. Bijective: Global function is one-to-one. Physics: Fundamental laws are reversible. Computing: Reversible logic. Examples: Rule 90, Critters. Importance: Thermodynamics, quantum.

🔄 Reversible🔙 Backwards⚛️ Physics💻 Computing

# Reversible Cellular Automata
print("=== What is Reversibility? ===")
print("""
A CA is reversible if:
  - The global update function F is bijective
  - Every configuration has exactly one predecessor
  - You can run time backwards

Mathematically:
  F: S^L → S^L is a bijection
  F⁻¹ exists

Properties:
  - No information loss
  - Entropy preserved
  - Time-symmetric
""")

# EXAMPLE: RULE 90 IS REVERSIBLE
print("\n=== Rule 90 — Reversible ===")
print("""
Rule 90: new = left XOR right

This is reversible:
  - Given new state, can recover old state
  - Actually, Rule 90 is its own inverse!
  - Apply Rule 90 twice → original state

Proof:
  Let a_i(t) be state of cell i at time t.
  a_i(t+1) = a_{i-1}(t) XOR a_{i+1}(t)
  
  Apply again:
  a_i(t+2) = a_{i-1}(t+1) XOR a_{i+1}(t+1)
           = (a_{i-2}(t) XOR a_i(t)) XOR (a_i(t) XOR a_{i+2}(t))
           = a_{i-2}(t) XOR a_{i+2}(t)
  
  Not exactly original, but still reversible.
  Actually, Rule 90 is reversible with a shift.
""")

# REVERSIBLE CA EXAMPLES
print("\n=== Reversible CA Examples ===")
print("""
1. RULE 90 (1D, binary)
   - XOR rule
   - Reversible
   - Produces Sierpinski triangle

2. CRITTERS (2D, binary)
   - Complex reversible CA
   - Supports gliders
   - Turing complete?

3. BILLIARD BALL MODEL (2D)
   - Particles moving and colliding
   - Reversible
   - Models computation

4. LATTICE GAS (2D/3D)
   - Particles on lattice
   - Reversible collisions
   - Models fluid dynamics

5. SECOND-ORDER CA
   - State depends on previous two states
   - Can be reversible
   - Example: Rule 90 with memory
""")

# REVERSIBLE COMPUTING
print("\n=== Reversible Computing ===")
print("""
Why reversible computing matters:

1. THERMODYNAMICS
   - Landauer's principle: erasing 1 bit costs kT ln 2 energy
   - Reversible computing avoids erasure
   - Potential for zero-energy computing

2. QUANTUM COMPUTING
   - Quantum gates are reversible
   - Unitary transformations
   - Essential for quantum algorithms

3. PHYSICS
   - Fundamental laws are time-reversible
   - CAs can model reversible physics
   - Quantum CA

4. COMPUTATION THEORY
   - Reversible Turing machines
   - Same computational power
   - But different resource requirements
""")

# IMPLEMENTATION
print("\n=== Implementation: Reversible CA ===")

class ReversibleCA:
    """
    Reversible CA using second-order rule:
      a_i(t+1) = f(neighbors) XOR a_i(t-1)
    
    This is always reversible!
    """
    def __init__(self, rule, width=60):
        self.rule = rule
        self.width = width
        self.history = []
    
    def initialize(self, init='single'):
        if init == 'single':
            cells = [0] * self.width
            cells[self.width // 2] = 1
        else:
            cells = list(init)
        self.history = [cells, cells]  # t-1, t
    
    def step(self):
        prev = self.history[-2]
        curr = self.history[-1]
        new = [0] * self.width
        
        for i in range(self.width):
            left = curr[(i - 1) % self.width]
            center = curr[i]
            right = curr[(i + 1) % self.width]
            
            # Second-order rule
            new[i] = self.rule(left, center, right) ^ prev[i]
        
        self.history.append(new)
    
    def display(self):
        for cells in self.history:
            print(''.join('█' if c else '·' for c in cells))

# Example: Second-order Rule 90
def rule90(l, c, r):
    return l ^ r

print("=== Second-Order Rule 90 ===")
rca = ReversibleCA(rule90, width=40)
rca.initialize('single')

for _ in range(10):
    rca.step()

rca.display()

# REVERSIBILITY PROOF
print("\n=== Proof of Reversibility ===")
print("""
Second-order CA:
  a(t+1) = F(a(t)) XOR a(t-1)

Given a(t) and a(t+1), we can recover a(t-1):
  a(t-1) = F(a(t)) XOR a(t+1)

So the evolution is reversible!

This works for any function F.
It's a general technique for reversible CA.
""")

# APPLICATIONS
print("\n=== Applications of Reversible CA ===")
print("""
1. PHYSICS SIMULATION
   - Quantum mechanics
   - Fluid dynamics
   - Particle physics

2. LOW-POWER COMPUTING
   - Adiabatic circuits
   - Reversible logic

3. QUANTUM COMPUTING
   - Quantum gates
   - Error correction

4. CRYPTOGRAPHY
   - Reversible transformations
   - Block ciphers

5. ARTIFICIAL LIFE
   - Self-replication
   - Evolution
""")

🌊 Continuous CA

🎯 When States Are Continuous

Continuous cellular automata allow cells to have continuous states (real numbers) instead of discrete ones. This bridges cellular automata and differential equations, enabling smoother, more natural patterns.

Continuous CA

States: Real numbers [0,1]. Rule: Continuous function. Examples: Lenia, SmoothLife. Physics: Reaction-diffusion. Graphics: Procedural textures. Biology: Morphogenesis.

🌊 Continuous States📐 Real Numbers🎨 Smooth Patterns🧬 Morphogenesis

# Continuous Cellular Automata
print("=== From Discrete to Continuous ===")
print("""
Standard CA:
  - States: finite set (e.g., {0, 1})
  - Rule: lookup table

Continuous CA:
  - States: real numbers (e.g., [0, 1])
  - Rule: continuous function

Examples:
  1. Reaction-Diffusion (Turing patterns)
  2. Lenia (continuous Game of Life)
  3. SmoothLife (smooth Game of Life)
  4. Excitable media
""")

# REACTION-DIFFUSION
print("\n=== Reaction-Diffusion ===")
print("""
Alan Turing (1952) proposed reaction-diffusion
as a model for morphogenesis (biological pattern formation).

Two chemicals:
  - Activator (A): activates itself and inhibitor
  - Inhibitor (I): inhibits activator

Equations:
  ∂A/∂t = f(A, I) + D_A ∇²A
  ∂I/∂t = g(A, I) + D_I ∇²I

Where:
  - f, g: reaction kinetics
  - D_A, D_I: diffusion coefficients
  - ∇²: Laplacian (diffusion)

This produces:
  - Spots (leopard)
  - Stripes (zebra)
  - Spirals
  - Complex patterns
""")

# LENIA
print("\n=== Lenia — Continuous Game of Life ===")
print("""
Lenia (Bert Chan, 2019):
  - Continuous states [0, 1]
  - Continuous space (or fine grid)
  - Smooth neighborhood kernel
  - Growth function

Update rule:
  A(t+1) = A(t) + dt * G(K * A(t))

Where:
  - K: convolution kernel (smooth)
  - G: growth function
  - dt: time step

Produces:
  - Gliders
  - Oscillators
  - Self-replicating patterns
  - Much more "natural" looking than Game of Life
""")

# SMOOTHLIFE
print("\n=== SmoothLife ===")
print("""
SmoothLife (Rafler, 2011):
  - Continuous version of Game of Life
  - Uses smooth transitions
  - Avoids grid artifacts

States: [0, 1]
Neighborhood: weighted average

Rule:
  - Similar to Game of Life
  - But with continuous values
  - Produces smoother patterns

Advantages:
  - No grid anisotropy
  - Natural-looking patterns
  - Can be simulated at any resolution
""")

# IMPLEMENTATION
print("\n=== Implementation: Continuous CA ===")

def continuous_ca_step(grid, rule, diffusion=0.1):
    """
    Simple continuous CA step.
    """
    rows, cols = len(grid), len(grid[0])
    new_grid = [[0.0 for _ in range(cols)] for _ in range(rows)]
    
    for r in range(rows):
        for c in range(cols):
            # Get neighborhood average
            neighbors = []
            for dr in [-1, 0, 1]:
                for dc in [-1, 0, 1]:
                    nr = (r + dr) % rows
                    nc = (c + dc) % cols
                    neighbors.append(grid[nr][nc])
            
            avg = sum(neighbors) / len(neighbors)
            new_grid[r][c] = rule(grid[r][c], avg)
    
    return new_grid

# Example: Simple growth rule
def growth_rule(center, avg):
    """Rule: grow towards average."""
    return center + 0.1 * (avg - center)

print("=== Continuous CA Demo ===")
print("""
This is a conceptual demo.
Real continuous CA use partial differential equations
and are simulated with numerical methods.
""")

# APPLICATIONS
print("\n=== Applications of Continuous CA ===")
print("""
1. BIOLOGY
   - Morphogenesis (Turing patterns)
   - Animal coat patterns
   - Cell differentiation

2. PHYSICS
   - Reaction-diffusion systems
   - Excitable media
   - Cardiac dynamics

3. COMPUTER GRAPHICS
   - Procedural textures
   - Natural pattern generation
   - Fluid simulation

4. CHEMISTRY
   - Belousov-Zhabotinsky reaction
   - Oscillating reactions

5. NEUROSCIENCE
   - Neural field models
   - Cortical dynamics

6. MATERIALS SCIENCE
   - Crystal growth
   - Phase separation
""")

# COMPARISON
print("\n=== Discrete vs Continuous CA ===")
print(f"{'Aspect':<25} {'Discrete CA':<25} {'Continuous CA':<25}")
print("-" * 75)
print(f"{'States':<25} {'Finite set':<25} {'Real numbers':<25}")
print(f"{'Rule':<25} {'Lookup table':<25} {'Function':<25}")
print(f"{'Behavior':<25} {'Digital':<25} {'Analog':<25}")
print(f"{'Computation':<25} {'Turing complete':<25} {'Depends':<25}")
print(f"{'Patterns':<25} {'Crisp, pixelated':<25} {'Smooth, natural':<25}")
print(f"{'Simulation':<25} {'Exact':<25} {'Numerical':<25}")

💼 Applications

🎯 Real-World Impact

Cellular automata are used in physics, biology, computer science, and art. From modeling traffic flow to generating textures, CAs provide a powerful framework for understanding complex systems.

Application Areas

Physics: Lattice gas, Ising model. Biology: Morphogenesis, epidemiology. CS: VLSI, cryptography. Art: Procedural textures. Urban: Traffic models. AI: Neural CA.

⚛️ Physics🧬 Biology💻 CS🎨 Art

# Applications of Cellular Automata
print("=== 1. Physics ===")
print("""
Lattice Gas Automata:
  - Model fluid dynamics
  - Particles on lattice
  - Reversible collisions
  - Alternative to Navier-Stokes

Ising Model:
  - Ferromagnetism
  - Phase transitions
  - Spin states on lattice

Quantum CA:
  - Quantum walks
  - Quantum computation
  - Digital physics

Lattice QCD:
  - Quantum chromodynamics
  - Strong force
  - Supercomputer simulations
""")

print("\n=== 2. Biology ===")
print("""
Morphogenesis:
  - Turing patterns (1952)
  - Animal coat patterns
  - Cell differentiation

Epidemiology:
  - SIR models on grids
  - Disease spread
  - COVID-19 modeling

Ecosystems:
  - Predator-prey dynamics
  - Forest fire models
  - Population dynamics

Neuroscience:
  - Neural field models
  - Cortical dynamics
  - Epilepsy modeling
""")

print("\n=== 3. Computer Science ===")
print("""
VLSI Design:
  - Cellular automata for test pattern generation
  - Fault simulation
  - Hardware verification

Cryptography:
  - CA-based ciphers
  - Pseudorandom number generation
  - Hash functions

Image Processing:
  - Noise removal
  - Edge detection
  - Morphological operations

Parallel Computing:
  - CA are inherently parallel
  - GPU implementations
  - Distributed simulation
""")

print("\n=== 4. Art and Design ===")
print("""
Procedural Textures:
  - Game of Life patterns
  - Rule 30 random textures
  - Reaction-diffusion patterns

Architecture:
  - Generative design
  - Facade patterns
  - Urban planning

Music:
  - CA-generated music
  - Algorithmic composition
  - Rhythmic patterns

Generative Art:
  - CA as art medium
  - Interactive installations
  - Digital art
""")

print("\n=== 5. Urban and Traffic ===")
print("""
Traffic Flow:
  - Rule 184 (Nagel-Schreckenberg)
  - Highway traffic modeling
  - Congestion prediction

Pedestrian Dynamics:
  - Crowd simulation
  - Evacuation planning
  - Social distancing

Urban Growth:
  - City expansion models
  - Land use change
  - Sustainability
""")

print("\n=== 6. AI and Machine Learning ===")
print("""
Neural Cellular Automata:
  - Differentiable CA
  - Trainable rules
  - Image generation

Morphological Computation:
  - Robot control
  - Soft robotics
  - Embodied AI

Generative Models:
  - CA-based GANs
  - Texture synthesis
  - Pattern generation
""")

# PRACTICAL EXAMPLE
print("\n=== Practical Example: Forest Fire Model ===")
print("""
A simple CA for forest fires:

States:
  0 = empty
  1 = tree
  2 = burning

Rules:
  - Empty → tree with probability p
  - Tree → burning if any neighbor burning
  - Burning → empty

This models:
  - Fire spread
  - Forest dynamics
  - Critical phenomena
""")

import random

def forest_fire_step(grid, p=0.01):
    """One step of forest fire CA."""
    rows, cols = len(grid), len(grid[0])
    new_grid = [[0 for _ in range(cols)] for _ in range(rows)]
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 0:  # empty
                new_grid[r][c] = 1 if random.random() < p else 0
            elif grid[r][c] == 1:  # tree
                # Check neighbors for fire
                burning = False
                for dr in [-1, 0, 1]:
                    for dc in [-1, 0, 1]:
                        if dr == 0 and dc == 0:
                            continue
                        nr = (r + dr) % rows
                        nc = (c + dc) % cols
                        if grid[nr][nc] == 2:
                            burning = True
                            break
                    if burning:
                        break
                new_grid[r][c] = 2 if burning else 1
            else:  # burning
                new_grid[r][c] = 0
    
    return new_grid

# Demo
print("\n=== Forest Fire Simulation ===")
grid = [[1 if random.random() < 0.7 else 0 for _ in range(20)] for _ in range(10)]
# Start a fire
grid[5][10] = 2

for step in range(5):
    print(f"Step {step}:")
    for row in grid:
        print(''.join('·' if c == 0 else '🌲' if c == 1 else '🔥' for c in row))
    print()
    grid = forest_fire_step(grid)

print("""
This simple model shows:
  - Fire spreading
  - Regrowth
  - Critical behavior
  - Self-organized criticality
""")

🔬 Research Frontier

🎯 Current Research Directions

Cellular automata research is active in many areas: artificial life, physics, computation theory, and machine learning. New discoveries continue to surprise us.

Research Areas

Artificial life: Self-replication, evolution. Physics: Quantum CA, digital physics. Computation: Universality, complexity. ML: Neural CA, differentiable CA. Mathematics: Classification, invariants. Applications: New domains.

🧬 Artificial Life⚛️ Physics💻 Computation🤖 ML

# Research frontier in Cellular Automata
print("=== 1. Artificial Life ===")
print("""
Self-Replication:
  - Von Neumann's universal constructor
  - Langton's Loops
  - Evoloops (evolvable loops)

Open Problems:
  - Minimal self-replicating CA?
  - Open-ended evolution?
  - Emergence of complexity?

Recent Work:
  - Lenia (life-like continuous CA)
  - Flow-Lenia (with physics)
  - Particle Lenia (as particles)
""")

print("\n=== 2. Physics and Digital Physics ===")
print("""
Quantum CA:
  - Discrete quantum mechanics
  - Quantum walks
  - Quantum computation

Digital Physics:
  - Is the universe a CA?
  - Wheeler's "It from Bit"
  - Wolfram's "A New Kind of Science"

Lattice Models:
  - Lattice QCD
  - Lattice gas
  - Ising model

Open Problems:
  - Can CA model all of physics?
  - Quantum gravity as CA?
  - Emergence of spacetime?
""")

print("\n=== 3. Computation Theory ===")
print("""
Universality:
  - Minimal universal CA?
  - Rule 110 is minimal for 1D binary
  - What about other dimensions?

Complexity:
  - Predictability of CA
  - Computational complexity of CA problems
  - Decidability questions

Classification:
  - Wolfram's classes
  - Formal classification
  - Machine learning classification

Open Problems:
  - Is there a general classification algorithm?
  - What is the complexity of CA prediction?
  - Are all Class 4 CA universal?
""")

print("\n=== 4. Machine Learning ===")
print("""
Neural Cellular Automata:
  - Differentiable CA
  - Trainable rules
  - Image generation
  - Texture synthesis

Morphological Computation:
  - Robot control
  - Soft robotics
  - Embodied intelligence

Generative Models:
  - CA-GANs
  - CA-VAEs
  - Diffusion models with CA

Open Problems:
  - Can neural CA learn any rule?
  - Interpretability of learned rules
  - Scaling to complex tasks
""")

print("\n=== 5. Mathematics ===")
print("""
Classification:
  - Formal classification of CA
  - Invariants
  - Algebraic properties

Dynamics:
  - Attractors
  - Chaos
  - Lyapunov exponents

Open Problems:
  - Is there a general theory of CA?
  - Predictability vs. chaos
  - Emergence of order
""")

print("\n=== 6. New Frontiers ===")
print("""
Continuous CA:
  - Lenia, SmoothLife
  - Reaction-diffusion
  - PDE-based CA

Asynchronous CA:
  - Non-simultaneous updates
  - More realistic
  - Different behavior

Stochastic CA:
  - Probabilistic rules
  - Noise
  - Statistical mechanics

Open Problems:
  - Universality in continuous CA?
  - Asynchronous CA universality?
  - Stochastic CA computation?
""")

print("\n=== Current Research Groups ===")
print("""
1. Wolfram Research
   - Fundamental physics
   - CA and complexity

2. MIT, Stanford, Berkeley
   - Artificial life
   - Neural CA

3. European Groups
   - Complex systems
   - Physics

4. Japanese Groups
   - CA theory
   - Applications

5. Online Communities
   - Conway Life forums
   - Reddit r/cellular_automata
   - Discord servers
""")

print("\n=== How to Contribute ===")
print("""
1. EXPLORE
   - Write CA simulators
   - Try new rules
   - Look for patterns

2. RESEARCH
   - Read papers
   - Formulate hypotheses
   - Test with experiments

3. PUBLISH
   - Share findings
   - Open source code
   - Write blog posts

4. COLLABORATE
   - Join communities
   - Attend conferences
   - Work with others
""")

🚀 Future: CA in Modern Computing

🎯 Where Cellular Automata Are Going

Cellular automata are finding new life in modern computing — from neural networks to quantum simulation. Their parallel nature and emergent behavior make them ideal for next-generation computing paradigms.

Future Directions

Neural CA: Trainable CAs. Quantum: Quantum CA. Hardware: CA processors. AI: Generative models. Physics: Digital physics. Art: Generative art.

🧠 Neural CA⚛️ Quantum🖥️ Hardware🎨 Art

# Future of Cellular Automata
print("=== 1. Neural Cellular Automata ===")
print("""
Trainable CA:
  - Rules are neural networks
  - Differentiable
  - Learn from data

Applications:
  - Image generation
  - Texture synthesis
  - Morphogenesis
  - Robot control

Example: Growing Neural CA
  - Start from single cell
  - Grow into target image
  - Self-repairing
  - Robust to damage

Future:
  - More complex tasks
  - 3D neural CA
  - Integration with LLMs
""")

print("\n=== 2. Quantum Cellular Automata ===")
print("""
Quantum CA:
  - Quantum states
  - Unitary evolution
  - Quantum computation

Applications:
  - Quantum simulation
  - Quantum walks
  - Quantum algorithms

Advantages:
  - Exponential state space
  - Quantum parallelism
  - Potential speedups

Challenges:
  - Decoherence
  - Error correction
  - Implementation

Future:
  - Quantum CA on quantum computers
  - Simulating quantum physics
  - New quantum algorithms
""")

print("\n=== 3. Hardware Acceleration ===")
print("""
CA Processors:
  - Dedicated hardware for CA
  - Massively parallel
  - Low power

Technologies:
  - FPGA implementations
  - GPU acceleration
  - ASIC designs

Applications:
  - Real-time simulation
  - Embedded systems
  - IoT devices

Future:
  - CA coprocessors
  - CA-based sensors
  - CA for edge computing
""")

print("\n=== 4. AI and Generative Models ===")
print("""
CA in AI:
  - Neural CA for generation
  - CA-based GANs
  - Diffusion models with CA

Advantages:
  - Local computation
  - Scalable
  - Interpretable

Applications:
  - Image generation
  - Video generation
  - 3D content creation

Future:
  - CA as generative prior
  - CA for world models
  - CA in reinforcement learning
""")

print("\n=== 5. Digital Physics ===")
print("""
Physics as CA:
  - Universe as cellular automaton
  - Spacetime as lattice
  - Particles as patterns

Theories:
  - Wolfram's hypergraph
  - Causal sets
  - Loop quantum gravity

Open Questions:
  - Is the universe a CA?
  - What is the rule?
  - How does quantum mechanics emerge?

Future:
  - Testable predictions
  - Simulating physics
  - Understanding reality
""")

print("\n=== 6. Art and Entertainment ===")
print("""
Generative Art:
  - CA as art medium
  - Interactive installations
  - Digital art

Games:
  - Game of Life in games
  - CA-based puzzles
  - Procedural generation

Music:
  - CA-generated music
  - Algorithmic composition

Future:
  - AI-generated art with CA
  - Interactive CA experiences
  - CA in virtual reality
""")

print("\n=== 7. New Frontiers ===")
print("""
Continuous CA:
  - Lenia, SmoothLife
  - Reaction-diffusion
  - PDE-based

Asynchronous CA:
  - Non-simultaneous updates
  - More realistic
  - Different behavior

Stochastic CA:
  - Probabilistic rules
  - Noise
  - Statistical mechanics

Open Problems:
  - Universality in continuous CA?
  - Asynchronous CA universality?
  - Stochastic CA computation?
""")

print("\n=== Timeline ===")
print("""
Past:
  1940s: Von Neumann's self-replicating CA
  1950s: Cellular automata formalized
  1970: Conway's Game of Life
  1980s: Wolfram's classification
  1994: Rule 110 proved universal
  2002: "A New Kind of Science"

Present:
  2010s: Neural CA
  2019: Lenia
  2020s: AI integration
  2025: Active research

Future:
  2030s: Quantum CA?
  2040s: CA-based AI?
  2050s: Digital physics?
  Beyond: Unknown
""")

print("\n=== Final Thoughts ===")
print("""
Cellular automata are:

  - Simple to define
  - Rich in behavior
  - Universally computational
  - Deeply connected to physics
  - A source of endless wonder

They show us:
  - Simple rules → complex behavior
  - Emergence is everywhere
  - Computation is fundamental
  - Nature computes

Whether we simulate physics, create art,
or build new computers, CA will be there.

"The universe is a cellular automaton."
  — Fredkin, Wolfram, and others

Keep exploring. Keep computing.
""")