Fundamental properties ofcellular automata andcomputation ability 2
Katsunobu Imai
Hiroshima University

IEC laboratory
2009年6月21日日曜日

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

How to Play with CellularProgramming?
Signal based algorithm
Composition of various signals are frequently used.

Reducing the number of used states is alwayswanted. (It needs craftsmanship training.)
Programming of rules and programming of Initialconfigurations
In some case, rules and the number of state are givenand programming is just the problem of giving aproper initial configuration. (cf. the game of Life)2009年6月21日日曜日

Signals on Cellular Automata(Example)rules(s, s, s) → s

Speed 1 signal:
timessss R s s ss s R s ss s s R sssssssssssss

Speed 1/3 signal:time

2009年6月21日日曜日

sssssss A ss B ss C ss s As s Bs s Cssssssssssssssssssssssssssssssssssss(s, s, R) → s(s, R, s) → s(R, s, s) → R(s, s, A) → s(s, s, B) → s(s, s, C) → s(s, A, s) → B(s, B, s) → C(s, C, s) → s(A, s, s) → s(B, s, s) → s(C, s, s) → A(s, s, s) → s

Firing Squad Synchronization
Problem (FSSP) Moore 1964
To construct an one-dimensional radius 1 CA ofarbitrary finite length such that one of the end cell(general) makes all the other cells (soldiers) be in aparticular state (firing state) at a certain time.
t=0x=1g2s3snst = tfffff

g: general, s: soldier, f: firing state
2009年6月21日日曜日

1964〜 Minsky & McCathy 3n time1966 Goto, optimal time1967 Balzar 8-state, optimal time1967 Mazoyer 6-state, optimal time
4-state is known to be impossible.
5-state is still remained.

Firing Squad Synchronization
Problem (FSSP)

7-state 3n-time solution

12
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2425
2009年6月21日日曜日

divide and conquer
algorithm

Yunes 1997

Optimization of Firing Time
Recursive application of divide and conquer algorithm
nna

115n/ 715n/ 8

1/3

1/3

7n/ 37n/ 4

1b1/7

1/7
1/15a00

2009年6月21日日曜日

c0d1

d0a01

a10

a11

Outline of Signals in Optimal
Time Solution
Limit of recursive applicationof divide and conquer
algorithm attains optimal
2n-2 time solution.

2009年6月21日日曜日

Designing Reversible Cellular
Automata
Signals and Reversibility
You can’t generate or annihilate signals.
deletion of signals
ﬁnite time
generation of signals

Generation and annihilation of signals must be coupled.
2009年6月21日日曜日

8-state Logically-Universal
Reversible CA
Imai, Morita 1998

2009年6月21日日曜日

Realization of a Switch Gate

2009年6月21日日曜日

Figure 19: A configuration of F-gate

Realization of a Fredkin Gate

2009年6月21日日曜日

How about reversible selfreproduction?
Self-reproducing CA were intensively studied bymany researchers of Artificial Life.
Reversible and non-dissipative self-reproducing
organism has a flavor of paradox and the setting
seemed to be fun for us.
Low power self-reproducing organism!
Is it possible to find any application to mesoscopic systems?
2009年6月21日日曜日

Langton’s self-reproducing loop
An 8-state von Neumann neighbor cellular automaton“genetic information is handled interpreted and uninterpreted
Langton 1984
The condition ofcomputation andconstruction
universality is too
excess for themodel of biologicalself-reproduction.
2009年6月21日日曜日

Langton’s self-reproducing loop
An 8-state von Neumann neighbor cellular automaton“genetic information is handled interpreted and uninterpreted
Langton 1984
The condition ofcomputation andconstruction
universality is too
excess for themodel of biologicalself-reproduction.
2009年6月21日日曜日

Self-inspection: another way ofself-reproduction
1979 Laing

Without genetic
description
Self-inspection is a verysimple framework.
On the fly compositionof the blueprint of itself.
2009年6月21日日曜日

A Reversible Self-reproducing
Cellular Automaton“Worms” and “Loops” can be self-reproduce in RCA.
(Morita, Imai 1996)

A+ AAA++AA
A+ AA
A+A+
AA +AA +A+* +AA +AA+AA +AA +*headtail(encodes its shape) (interprets commands to advance an arm)
Advance & Branch commands
Self-reproducing commands DB,DC
CommandOperationFirst
signalSecondsignalA

Advance the head forward

AB

Advance the head leftward

AC

Advance the head rightward

BABranch the wire in three ways

BB

Branch the wire in two ways (leftward)BC

Branch the wire in two ways (rightward)A

2009年6月21日日曜日

CommandOperation

FirstsignalSecondsignal

B

Create an arm

BC

Encode the shape of the Loop

DA+ AA
A++A
AA+ AA
A+A+
BD +AA +A

The DB command advances an arm

An Example:

2009年6月21日日曜日

A Three Dimensional Reversible
Self-reproducing Model
Three-ribbon worm... +AA+AA+AA+AA+AA+AA+AA...
= = = = = = =...+ ===+ == =+ == =+ == =+== =+ == =+== = ...
= = = = = = = ...
... +AA+AA+AA+AA+AA+AA+AA

wires
a glue wire

Commands
t=0signals

t=4t=4straight AA

turn AC left ward AB right ward ACAB rotation AB rotation AC

t=4t=4branch BC

branch BA

AA(2way) BB
2009年6月21日日曜日(3 way) BA

t=12

t=12

Imai, Hori, Morita 2002

Exapmle: a simple worm

2009年6月21日日曜日

Positioning commands andshape commands
The shape of a daughter Loop can be changed.

AA24
Original Positioning commands: AA24

Positioning commands of this example:
AA5 ABAA6 AA3 ABAAABAA6
AA5 ACAA6 AA3 ACAAACAA6The complete description of its commands:(AA5 ABAA6 AA3 ABAAABAA6 )AA5 ABAA5 ABAA5 ABAA656345556(AA ACAA AA ACAAACAA ) AA ACAA ACAA ACAA

2009年6月21日日曜日!

"#positioning signals$!

"#shape signals$

Positioning commands andshape commands
The shape of a daughter Loop can be changed.

AA24
Original Positioning commands: AA24

Positioning commands of this example:
AA5 ABAA6 AA3 ABAAABAA6AA5 ACAA6 AA3 ACAAACAA6The complete description of its commands:(AA5 ABAA6 AA3 ABAAABAA6 )AA5 ABAA5 ABAA5 ABAA656345556(AA ACAA AA ACAAACAA ) AA ACAA ACAA ACAA

2009年6月21日日曜日!

"#positioning signals$!

"#shape signals$

Example: a chain

2009年6月21日日曜日

Exapmle: speeding up

2009年6月21日日曜日

To self-reproduce, eat
something anyway!

A Number-Conserving Loop
based on the Langton’s loop
A = (Z, N395 , f, 235)

(Imai, Fujita, Iwamoto, and Morita 2001)(the value of blank cells is 235)
2009年6月21日日曜日

The Hyperbolic Plane
Poincaré Model for the Hyperbolic Plane
half-plane model versus disk modeliiwz11

2009年6月21日日曜日

Hyperbolic Cellular Automata
Margenstern, Morita 2001
Pentagrid
Hexagrid
Heptagrid...

Pentagrids are bit confusing for me!
How about von Neuman neighbor hyperbolic CA?
unfortunately no square tiling...
2009年6月21日日曜日

Quadrangles on the Hyperbolic
Plane
There exists infinite diﬀerent kinds of quadrangles
such that all edges are the same length.
(not rectangle)

There are infinite kinds of tiling with such quadrangles.

2009年6月21日日曜日

Tilings by Quadrangles
Quadrangles with angle = 2π/n (n >4) can tile thehyperbolic plane.

degree 5 (angle = 2π/5)

degree 6 (angle = 2π/6)
2009年6月21日日曜日

degree 10 (angle = 2π/10)

An example: Fredkin (Parity)
CA
EuclidianHyperbolic

Both rules are the same. (von Neumann neighborhood)
2009年6月21日日曜日

Let’s build a glider onHyperbolic CA...

2009年6月21日日曜日

Serizawa's 3-state Universal
Euclidean CA
3-state, von Neumann neighborhood
A signal is represented by
a “glider”.

(Serizawa 1986)

t=0

t=1

t=2
2009年6月21日日曜日

Basic Actions in Serizawa'sUniversal Euclidean CA
1. duplicatora spaceship2. eater

3. collision of two gliders

2009年6月21日日曜日

change direction glider generator

Logical universality of Serizawa's
Universal Euclidean CA
For example: AND gate can be constructed by duplicators,eaters, and collisions.
xx and yyLet’s embed such a model in a hyperbolic CA!
2009年6月21日日曜日

A glider on 4-state Hyperbolic
CA
t=0

t=2

t=1

t=3

2009年6月21日日曜日(Imai, Ogawa 2000)

H1: 5-state Quadrangular
Hyperbolic CA (degree 6)(Imai, Ogawa 2000)･ degree 6 quadrangle

1. duplicator･ 5-state, 5-neighbora spaceship･ H1 can perform three

2. eaterbasic actions.
3. collision of two glider

2009年6月21日日曜日

A Duplicator on H1a spaceship3 spaceships

2009年6月21日日曜日

A Duplicator on H1

2009年6月21日日曜日

Collision of two spacehips

2009年6月21日日曜日

Collision of two spacehips

2009年6月21日日曜日

Can H1 Perform Universal
Computation?
Maybe no.
It is impossible to realize feedback
signals.
treechanging direction

2009年6月21日日曜日

‘Sharp Turns’ are Inevitable in
the Hyperbolic Plane
Euclidean:RRRR
RSRSRSRS(both turn to the same cell)

2009年6月21日日曜日

Hyperbolic:
RRRRRRRSRSRSRSRSRS(impossible to turn back)How to Embed a Logical
Circuit?
Laying out a “mesh” on the hyperbolic space.
EuclideanEdges (length 1)

HyperbolicPaths (should be zigzag paths)(actually zigzig? paths...)

2009年6月21日日曜日

Length of Each Path is Diﬃcult
to Control
Exponentially long sharply turning zigzag path....
It is diﬃcult to embed synchronous circuits.
How about asynchronous circuits?
Delay insensitive (DI) circuits

2009年6月21日日曜日(Keller 1974)

Serial Modules
Def. A module is called serial if its specificationprohibits concurrent inputs or outputs, i.e., eachoutput event has exactly one unique input eventthat causes it.
AND

2009年6月21日日曜日

Serial Universality(Keller 1974)

Def. A set of primitive modules is serial
universal, if any arbitrary serial module isrealizable by a network of modules in theset.

b/{ }
c/{a}
a/{c}

Ib
O1

q0

I /{O1,O2}

O2

a/{b}
b/{c}

IOM

q0a
2009年6月21日日曜日

q0qbccFORK I
O2bc}

O1S-JOINac/{q0a/{}

a/{c}
b/{c}

bqaa}
b/{ {b}a/MERGEacb/ /{b}{c}A serial universal element set (Lee et, al. 2004)qc

E1: A 5-state Serial Universal
Euclidean CA
It simulates FORK, MERGE, S-JOIN, IOM, andcrossing modules.
FORKIOM
A wire and a signal

A crossing element

2009年6月21日日曜日

MERGE

S-JOINH2: 5-state Universal
Hyperbolic CA
Based on the CA E1 and added several
hyperbolic specific rules
Hyperbolic von Neumann-neighborhood
Degree-independent of quadrangles
Euclidean case (degree 4) is included

2009年6月21日日曜日

A Crossing Module

2009年6月21日日曜日

What’s next?
Cellular Automata on Penrose Tilings
Hill, Stepney, Wan 2005, Owens, Stepney 2008
Investigation of their behaviors in the case of random
initial configurations.

2009年6月21日日曜日

Generalized von Neumannneighborhoods
kite and dartrhomb
Owens, Stepney 20082009年6月21日日曜日

Generalized Moore
neighborhoods
rhomb

2009年6月21日日曜日

Owens, Stepney 2008

Thank you

2009年6月21日日曜日