Skip to Main Content
Think Complexity
book

Think Complexity

by Allen B. Downey
March 2012
Beginner content levelBeginner
160 pages
4h 6m
English
O'Reilly Media, Inc.
Content preview from Think Complexity

Chapter 6. Cellular Automata

A cellular automaton is a model of a world with very simple physics. “Cellular” means that the space is divided into discrete chunks, called cells. An “automaton” is a machine that performs computations—it could be a real machine, but more often the “machine” is a mathematical abstraction or a computer simulation.

Automata are governed by rules that determine how the system evolves in time. Time is divided into discrete steps, and the rules specify how to compute the state of the world during the next time step based on the current state.

As a trivial example, consider a cellular automaton (CA) with a single cell. The state of the cell is an integer represented by the variable xi, where the subscript i indicates that xi is the state of the system during time step i. As an initial condition, .

Now all we need is a rule. Arbitrarily, I’ll pick , which says that after each time step, the state of the CA gets incremented by 1. So far, we have a simple CA that performs a simple calculation: it counts.

But this CA is atypical; normally the number of possible states is finite. To bring it into line, I’ll choose the smallest interesting number of states, two, and another simple rule, , where is the remainder (or modulus) operator.

This CA performs a simple calculation: ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Unikernels

Unikernels

Russell Pavlicek
Elemental Design Patterns

Elemental Design Patterns

Jason McColm Smith
LEGO® with Dad

LEGO® with Dad

Warren Nash

Publisher Resources

ISBN: 9781449331672Errata