Fundamental properties ofcellular automata andcomputation ability
Katsunobu Imai
Hiroshima University

IEC laboratory
2009年6月21日日曜日

Quasi periodic tile and language theory (Kyoto) Jun. 8-10 2009

Remark:Prof. Akiyama asked me to make a survey
presentation of cellular automata.
But impossible for me!
Today, I just focus on universality of cellularautomata.

2009年6月21日日曜日

Automata
A computing
model withfinite memory
cf. Turing machine
•••

•••

infinite tapefinite control• finite state machine

2009年6月21日日曜日

Cellular Automata (CA)A massively parallel
computing model
systolic arraysconnection machines

A physical model
car traffics
fluids

I have no idea.
universe??? Just ask to Fredkin orWolfram.
cf. subshifts in symbolic dynamics
2009年6月21日日曜日

The game of “Life”
The most famous cellular automaton
Conway 1970

Moore neighborhood

Survive
http://mathworld.wolfram.com/CellularAutomaton.html

2 or 3 alive cells aroundBirth
3 alive cells around

Birth range [3,3]Survive range [3,4]2009年6月21日日曜日

Deathotherwise

Universality in Cellular Automata
von Neumann 1950’s
computation-universality
You can ‘compute anything’ by a machine.

construction-universality
You can ‘construct anything’ by a machine.
(including the computing machine itself)

2009年6月21日日曜日

The stages of self-reproducing
models by von Neumannkinematic model
cellular model(-1948)⇐ Ulam(-1953)

excitation-threshold-fatigue model
continuous modelby differential equation

probabilistic model

mutationcrystal growth < ・・・ < biological self-reproduction
2009年6月21日日曜日

A self-reproducing celluar
automaton by von Neumann
A 29 state cellular automaton
Constructor C

Universal
Copier B

von Neumann 1950-

UniversalConstructor

A

Whole descriptions

L(A+B+C)

DaughterMachine(cf. Watson, Crick 1953)

Computation andconstruction universal

Construction ArmMotherMachinevon Neumann (Burks ed.)1966
2009年6月21日日曜日

(Nobili-Pesavento 1996)

2009年6月21日日曜日

Definition
A deterministic cellular automaton A = (d, Q, N, f )dimension: d finite set of states: Q (quiescent state:N)q∈
Q,f(q,q,q)=0
local function: f : Q → Q
dconfiguration: Conf(Q) = {α|α : Z → Q}
neighborhood: N = {ν1 , · · · , νn }global function:
F : Conf(Q) → Conf(Q)∀z ∈ Zd ,F (α)(z) = f (α(z + ν1 ), α(z + ν2 ), · · · , α(z + νn ))2009年6月21日日曜日

Neighborhoods
choose one as you likeone dimensional caseradius 1/2, one-way
radius 1mn

•••

•••

•••

two dimensional casevon Neumann

radius 2 Moore

three or more dimensional case...
2009年6月21日日曜日

m{x 1,1 x 1,2x 1,nx m, 1x m, 2x m,nx 2,1 x 2,2x 2,n{

Moore

Margolusn...

Local function
local functionc’f (0, 0, 0, 0, 0) = 0...

1 0 1 1 1 0 1 1
1 1 0 0 1 0 1 00 1 1 0 1 1 0 0
0 1 1 1 1 0 0 0

t+1 . . .

0 0 1 0 1 0 0 0
0 0 0 0 0 0 1 1
0 0 0 0 0 0 1 0
0 0 0 0 0 1 1 1t

f (0, 0, 0, 0, 1) = 1

f (c, u, r, d, l) = c..
..
f (1, 1, 1, 1, 0) = 0
f (1, 1, 1, 1, 1) = 0

2009年6月21日日曜日...

... ...

!

...

ul c rd...

Frequently used symmetricconditions

The number of distinct rules is too large for the daily use...
It depends on the chosen shape of neighborhood.

rotation-symmetryreflection-symmetry
totalistic, permutation-symmetry...

ul c rdf (c, u, r, d, l) is independent of the order ofu, r, d, l
The rule can be written as the sumof states in the case of Q = {0, 1}

2009年6月21日日曜日

Finite and infinite configuration
It is reasonable to introduce infinite cellular space.
Finite (initial) configuration:
the number of non-quiescent cells is finite
i.e., the “mass” of the cellular space is finite

Infinite (initial) configuration
periodic (with a given constant period)
combination of infinite periodic background and a finite pattern

random (with a given distribution)...
2009年6月21日日曜日‘fair’ setting for computation
cf. rule 110

Basic properties of globalfunction
Defs.
CA is injective: its global function isinjective.
CA is surjective: its global function issurjective.
CA is reversible: there is a CA that reverts it.

2009年6月21日日曜日

Garden of Eden
A configuration with no predecessor
Banks 1971

CA is surjective

CA has no Garden of Eden

CA is injective

CA is surjective

Global function restricted to finite configuration isinjective
CA is surjective
Moore 1962, Myhill 1963
2009年6月21日日曜日

Reversible cellular automata
CA is reversible

CA is injective

Hedlund 1969, Richardson 1972

Reversibility (surjectivity) is decidable
in one-dimensional caseAmoroso, Patt 1972

Reversibility (surjectivity) is undecidable
in two (or more)-dimensional caseKari 1990, 1994
2009年6月21日日曜日

Number (Momentum)Conserving Cellular Automatat •••t +1 • • ••••!

"#$•••

f(0,0,0)=0f(0,0,1)=0f(0,1,0)=0f(0,1,1)=1f(1,0,0)=1f(1,0,1)=1f(1,1,0)=0f(1,1,1)=1

A simple car traffic rule(Nagel, Schreckenberg 1992)

cf. lattice gases (Margolus neighborhood)
2009年6月21日日曜日

Number (Momentum)Conserving Cellular Automata
1991 Hattri, Takesue: additive conserved
quantities in 1D CA
2000 Boccara, Fuks: 1D NCCA is characterizedby motion representation
2001 Durand, Formenti, Roka: numberconservation is decidable in any dimension
2005 Bernardi et, al.: number-decreasing property
is decidable in one-dimension but undecidable intwo ore more dimension
2009年6月21日日曜日

Turing Universality
Let the cellular automaton simulate one of thewell known universal models of computation.

Turing machine, 2-register (counter) machine,
Chomsky type-0 grammar, 2-TAG system,
cyclic TAG system, ...
2009年6月21日日曜日

m-TAG System(m, A, P )Post 1943

m: deletion number (positive integer)
A: finite set of alphabet (including a haling alphabet)
P: production ruleex. 2-tag system
A={a,b,c,H}
P: a --> ccbaHb --> ccac --> cc

Initial word: baaacca
caccbaH
ccbaHccbaHcccc
Hcccccca (halt).

1-TAG is decidable, 2-TAG is Turing-universal.

Wang 1963, Cocke, Minsky 1964

Turing-universal even under a kind of context-freeness2009年6月21日日曜日

Cyclic TAG System (CTAG)
Alphabet is limited to 0,1

Cook 2004

Production rules are applied sequentially (do notneed random access table-lookup mechanism)
CTAG C1 = ( 3, { Y, N }, ( ε, YN, YY ))

NYY
YY
YYN
YNYYNYY
2009年6月21日日曜日

Y → ε (0)Y → YN (1)Y → YY (2)applied rule01
2
no halting state0
cf. CTAG with halting state
1Morita 2006

Logical Universality
limited to t wo or more dimensional caseA cellular automaton is logically universal:
A set of universal logical elements and theirwiring scheme are embedded to the cellularautomaton.
e.g. {NAND, unit delay}, {AND, OR, NOT, unit delay}
Any combinatorial circuit can be constructible.
2009年6月21日日曜日

Universal logic element set
suitable for embedding in a CA

(Banks 1970)2009年6月21日日曜日

Universal with Finite/Infinite
Configuration
Universal simulation can start with finite initialconfiguration
e.g. counter machine simulation by the game of Life

Universal simulation can start with infinite but
periodic initial configuration and a finite patterne.g. rule 110

2009年6月21日日曜日

Intrinsic universality
A universal Turing machine which simulates any otherTuring machine.
A cellular automaton which simulates any other cellularautomaton.
cellular automata simulated by cellular automata
in a shift invariant, time invariant way.

2009年6月21日日曜日

Roughly speaking...
logically universal CAs require infinite configurations
In two or more dimensional case, logically universal
intrinsic universal.
logically universal

Turing-universal

construction-universal (in von Neumann’s sense)
Computations can start with a finite configuration but theCA can construct the pattern of a Turing machine
including an infinite periodic tape-structure.
2009年6月21日日曜日

2D von Neumann neighborhood
Universal CA
1966 von Neumann 29-state, construction-universal
1968 Codd 8-state
construction-universal
proof of non-universality of 2-state finite-configuration

1970 Banks
4-state construction-universal
3-state finite configuration
2-state infinite configuration

1983 Serizawa 3-state construction-universal
2009年6月21日日曜日

2D Moore neighborhood
universal CA
1970 Berlekamp, Conway, Guy: 2-state, totalistic,construction-universal(1987 Silverman: Wireworld 4-state, logicallyuniversal)

A realization of XOR gate
in Wireworld (Wikipedia)
2009年6月21日日曜日

Direct embedding of Turingmachine to the game of Life(Rendell 2002)2009年6月21日日曜日

1D universal CA (radius 1)
1971 Smith III: 18-state (simulation of TM)
1990 Lindgren, Nordahl: 7-state (simulation of TM)
2002 Olinger: Intrinsically-universal, 6-state2004 Cook: 2-state (rule 110) CTAG
2008 Richard: Intrinsically-universal, 4-state

2009年6月21日日曜日

One-dimensional Intrinsicuniversal CA Olinger 2002
Each bits of binary encoded state value can be computedby a circuit made by NAND and COPY gates.
1 0 1 110 11t

δ(1,0,1,1) = (0,1)
01t+1L0x●y●

z●t●

L1L0x

●0 1y●z●L2

δ2 (1,0,1,1) = 1t●：variabletx yz t：NAND：COPY

L2
δ1 (x, y, z, t) = x|tδ1 (1,0,1,1) = 0●

L1

2009年6月21日日曜日

δ1

δ2 (x, y, z, t) = y|yt+1x|t y|yOntline of a Cofiguration of
Olinger’s intrinsic-universal CAxyz○ ● ○ ■ ○ ○ ○ ○ ○ ● ○ ■ ○ ○ ○ ○ ○ ● ○ ■ ○○ ● ○ ○ ■ ○ ○ ○ ○ ● ○ ○ ■ ○ ○ ○ ○ ● ○ ○ ■○ ● ○ ○ ○ ■ ○ ○ ○ ● ○ ○ ○ ■ ○ ○ ○ ● ○ ○ ○○ ● ○ ○ ○ ○ ■ ○ ○ ● ○ ○ ○ ○ ■ ○ ○ ● ○ ○ ○○ ● ○ ○ ○ ○ ○ ■ ○ ● ○ ○ ○ ○ ○ ■ ○ ● ○ ○ ○■ ● ○ ○ ○ ○ ○ ○ ■ ● ○ ○ ○ ○ ○ ○ ■ ● ○ ○ ○time■ ■ ○ ○ ○ ○ ○ ○ ■ ■ ○ ○ ○ ○ ○ ○ ■ ■ ○ ○ ○■ ○ ■ ○ ○ ○ ○ ○ ■ ○ ■ ○ ○ ○ ○ ○ ■ ○ ■ ○ ○○ ● ○ ■ ○ ○ ○ ○ ○ ● ○ ■ ○ ○ ○ ○ ○ ● ○ ■ ○○ ● ○ ○ ■ ○ ○ ○ ○ ● ○ ○ ■ ○ ○ ○ ○ ● ○ ○ ■○ ● ○ ○ ○ ■ ○ ○ ○ ● ○ ○ ○ ■ ○ ○ ○ ● ○ ○ ○○ ● ○ ○ ○ ○ ■ ○ ○ ● ○ ○ ○ ○ ■ ○ ○ ● ○ ○ ○○ ● ○ ○ ○ ○ ○ ■ ○ ● ○ ○ ○ ○ ○ ■ ○ ● ○ ○ ○2009年6月21日日曜日■ Sig● Val○ Op

Universality of Rule 110
0 0 0

0 0 1

0 1 0

0 1 10

11

1

1 0 0

1 0 1

1 1 0

1 1 101

10time2009年6月21日日曜日

Cook 2004
Simulation of CTAG

Outline of space time diagram ofCTAG simulation by Rule 110
Cook 2004 cf. Martinez 2006

2009年6月21日日曜日

Universal Reversible CA
1977 Toffoli: Turing-universality of 2D reversible CA
1984 Margolus: 16-state, 2D, billiard ball model CA,logically-universal
1989 Morita, Harao: 1D, simulation of reversible TM
1997 Durand-Lose: 1D, a weak sense of intrinsic-universal
2000 Imai, Morita: 8-state, 2D triangular neighborhood
2000 Morita, Ogiro.: 81-state, 2D von Neuman, finiteconfiguration
2008 Morita: 24-state, 1D radius 1, reversible CTAG
2006 Morita: 98-state, 1D, radius 1, finite configuration,reversible CTAG with halting state
2009年6月21日日曜日

Reversible system can belogically-universal
Fredkin, Toffoli 1982

2009年6月21日日曜日

The BBM Cellular Automaton
Reversible and logically-universal
Margolus 1984

Margolus neighborhood

2009年6月21日日曜日

t=0

t=1

t=2

t=3

t=4

t=5

Reversible Partitioned CA
Morita, Ueno 1989, Morita, Harao 1989

Each cell is partitioned into the equal number ofparts to the neighborhood size
A partitioned CA is reversible iff its local function
is one-to-one
PCA is a subclass of ‘normal’ CA
2009年6月21日日曜日

81-state 2 dimensional universal
reversible partitioned CA
Simulation of two-counter machine
Morita, Ogiro 200034 − state

2009年6月21日日曜日

cf. 44 − stateUniversal Number-Conserving
Cellular Automata
2002 Imai et, al. 26-state 2D, von Neumann2003 Moreira: 1D, 2q+2-state, 2n-neighborhood
NCCA can simulate q-state, n-neighborhood CA
2007: Tanimoto et, al.: 14-state, 2D, vonNeumann

2009年6月21日日曜日

Motion representation
Any transition of number-conserving CA can becharacterized by a set of movement of particles.
tt+10 1 1 1 1 1 10 0 1 1 1 1 1...
...

1 1 1 0 0 0
1 1 1 1 0 01

1{10, 11}f(0,0,0)=0
f(0,0,1)=0f(0,1,0)=0f(0,1,1)=0f(1,0,0)=1f(1,0,1)=1f(1,1,0)=1f(1,1,1)=1(cf. Fuks 2000, Pivato 2002)
2D case? (cf. Kari, Taati 2008)2009年6月21日日曜日

Tomorrow

How to play with cellular automata with various
kind of neighborhoods in two and threedimension, hyperbolic plane...

2009年6月21日日曜日

References
Kari, J.: Theory of cellular automata: A survey, TCS
334 (2005) 3-33.
Ollinger, N: Universalities in cellular automata: A
short survey, JAC 2008, pp.102-118.

2009年6月21日日曜日