BioInspired Computing, Lectures 5-6 (Cellular Automata)

CELLULAR AUTOMATA

What are the 4 criteria for biological life?

• Metabolism (Flux of matter and energy)

• Self reproduction

• Organisation

• Adaptation

What is the basic unit of life? (according to F M Howard)

The cell - it represents the simplest level of organisation that manifests all the features of the phenomenon of life

What are the three major classes of macromolecule? (the types of cell components)

• DNA

• RNA

• Protein

What is the central dogma of molecular biology?

DNA makes RNA makes protein

Describe the five steps of information transfer in cells

1) External signal received

2) Signal transferred and processed

3) Genes up/down-regulated

4) Transcription/translation

5) Change in cell behaviour

How can a cell be considered as a computational device?

A cell acts as an input-output device that performs computation - proteins are effectors of computational tasks such as integration, amplification and storage

What gives rise to emergent complex structure and function of tissues?

The coordinated behaviour of large numbers of cells performing computation in parallel (e.g. division, death, protein secretion and degradation)

What is a Cellular Automaton (formal definition)?

An n-dimensional lattice of identical and synchronous finite state machines whose state s is updated following a transition function f that takes into account the state of machines in a neighborhood N

Write the formal CA update equation

si(t+1) = f(sj(t) where j belongs to Ni)

What are the fundamental components of a CA model? (concepts incorporated in a CA model)

Cell and cellular space

Neighbourhood (local interaction)

Cell state

Transition rule

For a 2D CA, what are the two key neighbourhood types?

Von Neumann neighbourhood and Moore neighbourhood

In a 1D binary CA with radius r=1, how many possible rules are there?

256 rules

What are the 7 steps to implement and run a CA model?

1) Assign geometry of CA space

2) Assign geometry of neighbourhood

3) Define set of states

4) Assign transition rule

5) Assign boundary conditions

6) Assign initial conditions

7) Repeatedly update cells until stopping condition

How do you calculate a Wolfram Rule number?

List all possible neighbourhood states in descending order, write the resulting center cell state, interpret as binary number, convert to decimal

What is Wolfram Rule 184 also known as? (and what is it used for?)

The traffic rule (used to model traffic flow in a single lane)

What is the transition rule for Rule 184?

A car advances to the next cell only if the destination cell is free (unoccupied)

In Rule 184 with density ρ=0.3, what emergent behaviour is observed?

Clusters of cars all moving with the same speed and gaps in traffic propagating to the right

In Rule 184 with density ρ=0.7, what emergent behaviour is observed?

Traffic jams propagating to the left

What is the critical density for the phase transition in Rule 184?

ρ = 0.5 (transition between freely flowing and congested traffic)

What are Wolfram's four qualitative behavioural classes for CA?

1) Uniform final state

2) Simple stable or periodic final state

3) Chaotic random nonperiodic patterns

4) Complex localized propagating structures

Which Wolfram class does Rule 18 belong to?

Class 3 - chaotic/random behaviour

Which Wolfram class does Rule 110 belong to?

Class 4 - complex, localized, propagating structures

What is computational universality in CA?

The ability of a CA to emulate any computing machine (e.g. Life and Rule 110 can perform universal computation)

What does it mean that Conway’s Game of Life is computationally irreducible?

There is no shortcut way to predict the result of Life's evolution - you must run it to see what happens

What is excitable media?

A system formed by segments or cells with a well-defined steady state, a threshold for excitation, a refractory period following excitation, and diffusive coupling with near neighbours

What are the three states typically used in excitable media CA?

ON (excited/stimulated)

OFF (excitable/can be stimulated)

REFRACTORY (recovering/temporarily cannot be stimulated)

Give two examples of excitable systems that can be modeled with CA

Forest fires and cardiac electrical propagation in the heart

In a forest fire CA model, what would the REFRACTORY state represent?

Patch of land where trees have burnt and vegetation has yet to regrow

What is the Game of Life neighbourhood type?

Moore neighbourhood (8 surrounding cells)

What are the states in Conway's Game of Life?

Two states: dead or alive

State the birth rule in Game of Life

A dead cell becomes alive if exactly 3 neighbours are alive

State the survival rules in Game of Life

A live cell survives if 2 or 3 neighbours are alive

State the death rules in Game of Life

Death from isolation (0 or 1 neighbours) or overcrowding (more than 3 neighbours)

Name three types of structures that can emerge in Game of Life

1) Static structures (e.g. block, boat)

2) Oscillating structures (e.g. blinker)

3) Dynamic propagating structures (e.g. glider)

What properties of cellular systems inspired computational abstractions?

Simple input-output devices, autonomous (no centralized control), dominated by local communication, massively parallel, robustness, give rise to self-organization and emergent complex behaviour

What computational abstractions were inspired by the nervous system?

Neural networks (inspired by electrical communication in neurons)

What computational abstractions were inspired by the immune system?

Artificial Immune Systems

What computational abstractions were inspired by cellular systems?

Cellular Automata

What is a probabilistic CA?

A CA where transition rules depend on some external randomness rather than being deterministic

What was von Neumann's question about self-reproducing machines?

Can we prove formally that there exist machines which can produce more complex machines than themselves?

What are the four components of von Neumann's self-reproducing automaton?

1) Universal constructor (factory that can read the tape and build a new automaton)

2) Tape (instructions for building a new automaton)

3) Tape copier (copies tape to new automaton)

4) Controller (controls the process: tells the constructor to build, tells the tape copier to copy, activates the controller of the new machine)

What is the biological analogy for von Neumann's tape?

DNA (genetic instructions)

What is the biological analogy for von Neumann's tape copier?

mRNA (messenger RNA) (copies genetic info)

What is the biological analogy for von Neumann's universal constructor?

Ribosomes (protein factories)

How many cells and states did von Neumann's automaton require?

200,000 cells and 29 states

Why is the refractory period important in excitable media?

It prevents immediate re-excitation, allowing a wave or signal to propagate in one direction (directional information flow)

How does a cardiac CA model work? (4 steps)

1. Signal starts at the SA (sinoatrial) node

2. Propagates around the heart

3. Refractory period

4. Repeat

What is a limitation of the simple Rule 184 traffic model?

Real traffic is more complex - it doesn't account for multiple lanes, junctions, different speeds, reaction times etc.

What does a phase transition mean in the context of Rule 184?

A qualitative change in system behaviour at a critical parameter value (density ρ = 0.5 separates freely flowing from congested regimes)

What is an advantage of using CA for modeling compared to differential equations?

CA are naturally parallel, can handle discrete entities easily, are computationally efficient, and can generate emergent behaviour from simple local rules

What is model evaluation in the context of CA simulation?

Assessing what aspects of the real system the model represents, what behaviour it predicts, and what insight this provides into the real system

What is model critique in the context of CA simulation?

Identifying what features of the real system the model does not represent, what behaviour is inconsistent with reality, and how the model could be improved

What does it mean that CA exhibit emergence?

Complex global patterns and behaviours arise from simple local rules and interactions, without central coordination

What is the difference between synthesis and analysis in CA applications?

Analysis - using CA to explore complexity and artificial life

Synthesis - using CA as a method of carrying out simulations of real systems

What is embryogenesis an example of?

Self-organization and emergent behaviour - a single cell (zygote) develops into a complex organism with ~10^13 cells arranged in tissues and organs, with no central control

What does the phantom traffic jam demonstrate?

That traffic jams can occur without any apparent cause (like an accident) - they emerge from the dynamics of the traffic flow itself

What is meant by "diffusive coupling" in excitable media?

Each cell's state can influence and be influenced by neighbouring cells through local interactions (like heat or signal propagation)

What is a quiescent state in CA?

A special rest state (often denoted s0) where a cell remains unchanged unless stimulated.

What’s the difference between a quiescent state and a refractory state in CA

Quiescent state is a neutral background state, the ‘canvas’ on which things happen. e.g. the ‘dead’ space in GoL or an unburned forest area in wildfire. State only changes if its neighbours are excited.

Refractory state is ‘resting’ - it does not change even if its neighbours are excited. e.g. ‘burnt’ in wildfire

What is the relationship between CA and parallel computation?

CA are inherently parallel - all cells update simultaneously based on local information, making them naturally suited for parallel computing architectures

What makes CA "cellular" systems?

They are composed of discrete cells arranged in a lattice, each following the same simple rules, similar to how biological tissues are composed of many cells

Why are CA considered "automata"?

Each cell is an autonomous finite state machine that updates its state automatically according to fixed rules

What is synchronous updating in CA?

All cells update their states simultaneously at each time step (as opposed to asynchronous updating where cells update at different times)

What does it mean for CA to be homogeneous?

All cells follow the same transition rules and have the same neighbourhood geometry

Why might forest fire models use hexagonal grids instead of square grids?

Hexagonal grids have uniform distance to all six neighbours, avoiding the diagonal distance problem in square grids

Are CA top-down or bottom-up systems?

CA are bottom-up systems - complex global behaviour emerges from local rules rather than being imposed from above (top-down)

Why is CA modeling relevant for bio-inspired computing?

CA capture key properties of biological systems: local interactions, parallel processing, emergence, robustness, and self-organization

What is the connection between CA and dynamical systems?

CA are discrete dynamical systems that evolve in discrete time steps according to deterministic or stochastic rules