Laboratoire Bordelais de Recherche en Informatique

Laboratoire Bordelais de Recherche en Informatique

English
14 Pages
Read
Download
Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

Description

Niveau: Supérieur
Laboratoire Bordelais de Recherche en Informatique, ura cnrs 1 304, Université Bordeaux I, 351, cours de la Libération, 33 405 Talence Cedex, France. Rapport de Recherche Numéro 1177-97 Reversible space-time simulation of cellular automata Jérôme O. Durand-Lose 1 LaBRI, ura cnrs 1 304, Université Bordeaux I, 351, cours de la Libération, F-33 405 Talence Cedex, France. We briey recall the denitions of Cellular automata (ca), simulation, re- versibility and Partitioned cellular automata (pca) as dened by Morita. We call the sequence of the iterated congurations of a conguration a space-time diagram. We dene an embedding relation between space-time diagrams and a space-time simulation relation between ca. We built a space-time simulation of any ca by a reversible pca (r-pca). Finally, we state our main result: there are reversible ca able to space-time simulate any ca of the same dimension. Key words: Cellular automata, space-time simulation, intrinsic universality and reversibility. 1 Introduction Reversibility corresponds to the conservation of information and energy. It allows unambigu- ous backtracking. In computer science, reversible is studied in order to design computers which would waste less energy.

  • diagram gener

  • over

  • cellular automata

  • any space-time

  • time simulation

  • local function

  • generates any diagram

  • various ways

  • simulate any


Subjects

Informations

Published by
Reads 23
Language English
Report a problem

La
b
oratoire
of
order
y
B
duction
ordelais
b
de
dimension
R
spaceime
ec
allo
herc
[2]
he
ed
en
and
I
c
nformatique
t
ura
and
cnrs
conserv
1
In
304,
w
Univ
uring
ersit
ersible
Bordeaux
ter
I
ca
351,
v
cours
The
de
es
la
httpeptnfoabri
Lib
er
ation
trinsic
33
.
405
corresp
T
and
alence
ous
Cedex
ersible
France
whic
.
.
Rapp
that
ort
b
de
whic
Rec
Morita
herc
t
he
y
Numo
one
1177-97
massiv
Rev
They
ersible
inite
spaceime
is
sim
the
ulation
Eac
of
from
cellular
A
automata
jdura
Je
Preprin
O
Cellular
Durandose
ulation
1
ersalit
L
ersibilit
aBRI
In
ura
ersibilit
cnrs
to
1
of
304,
.
Universit
unam
Bor
ktrac
de
science
aux
studied
I
design
351,
w
c
less
ours
1973,
de
v
la
y
Lib
hine
?r
sim
ation
another
F
is
405
tly
T
pro
alence
an
Ce
o
dex
can
France
ulated
.
rev
W
automata
e
mo
brie
parallel
recall
ysical
the
ork
deitions
matrices
of
but
Cellular
underlying
automata
d
(
ts
ca
are
),
ls
sim
cell
ulation
v
re
ite
v
S
ersibilit
jdurandabriordeauxr
y
xr
and
.
P
to
artitioned
2
cellular
ds
automata
automata
(
sim
pca
in
)
univ
as
y
deed
rev
b
y
y
1
Morita
tro
W
Rev
e
y
call
onds
the
the
sequence
ation
of
information
the
energy
iterated
It
conurations
ws
of
bigu
a
bac
conuration
king
a
computer
sp
rev
ac
is
eime
in
diagr
to
am
computers
.
h
W
ould
e
aste
dee
energy
an
In
emb
Bennett
e
pro
dding
ed
relation
an
b
T
et
mac
w
can
een
e
spaceime
ulated
diagrams
y
and
one
a
h
sp
rev
ac
Recen
eime
,
simulation
[15]
relation
v
b
that
et
y
w
w
een
coun
ca
automata
.
b
W
sim
e
b
built
a
a
ersible
spaceime
Cellular
sim
(
ulation
)
of
del
an
ely
y
computation
ca
ph
b
phenomena
y
w
a
o
rev
er
ersible
of
pca
size
(
ite
rca
the
).
lattice
Finally
Z
,
.
w
elemen
e
of
state
matrices
our
called
main
el
result
.
there
h
are
tak
rev
a
ersible
alue
ca
a
able
set
to
states
spaceime
.
sim
1
ulate
,
an
bordeau
y

ca
nd
of
Preprin
the
submitted
same
Elsevier
dimension
t
Key
Octob
wor
1997conuration
is
a
v
)
in
yb
aluation
wn
of
sim
a
class
whole
an
matrix
o
A
restrictiv
ca
one
up
another
dates
more
a
sim
conuration
dimension
b
the
y
h
sync
is
hronously
some
c
an
hanging
a
the
computation
state
class
of
sim
eac
to
h
v
cell
dimension
according
time
to
of
the
ulate
states
pro
of
h
the
b
cells
strict
around
set
it
Generally
and
an
a
for
lo
hine
cal
Generally
function
enco
f
of
.
ulation
All
In
cells
sim
use
generally
the
the
same
rca
lo
y
cal
the
function
are
This
ra
is
),
a
or
parallel
b
sync
[4]
hronous
et
lo
p
cal
with
and
1995
uniform
it
pro
conurations
cess
some
A
a
ca
whic
is
Finite
rev
e
ersible
b
when
is
its
ysicians
global
means
function
result
G
initial
is
On
a
one
bijection
the
and
totally
its
sim
in
not
v
migh
erse
er
G
n
1
In
is
ab
itelf
hineutomatonewriting
the
alence
global
ersalit
function
the
of
mac
some
a
ca
induction
.
it
Researc
computation
h
the
on
are
rev
ulate
ersible
(
ca
In
(
[3]
ra
that
)
able
b
an
egun
the
in
than
the
v
60
conuration
's:
in
Mo
result
ore
extended
[12]
in
and
the
Myhill
.
[16]
is
pro
it
v
to
ed
y
that
ra
if
dimension
G
Morita
is
ed
oneone
p
then
er
it
conurations
is
there
a
q
bijection
there
Hedlund
n
[6]
of
and
are
Ric
q
hardson
form
[17]
of
pro
whic
v
far
ed
the
that
conurations
an
to
y
for
function
mathematici
o
to
v
up
er
ding
S
onds
Z
p
d
of
whic
mac
h
e
comm
purp
utes
an
with
iteration
an
ulated
y
b
shift
ded
and
of
whic
mac
h
it
is
considered
con
ulated
tin
b
uous
o
for
arious
the
an
pro
b
duct
ulating
top
theory
ology
sp
is
the
the
a
global
b
function
dees
of
programming
some
uni
ca
inside
.
deed
As
y
a
an
consequence
of
for
action
an
hine
y
b
ca
mac
it
another
is
es
enough
steps
to
h
b
just
e
result
oneone
)
to
able
b
sim
e
an
rev
ca
ersible
ra
In
[4].
1972
1995
,
author
Amoroso
pro
and
ed
P
there
att
ra
[1]
to
pro
ulate
v
y
ed
of
that
same
ca
reater
rev
2
ersibilit
o
y
er
is
y
decidable
nite
in
not
dimension
linear
1
This
.
has
In
een
1990
to
,
1
Kari
1997
[9]
with
pro
use
v
pca
ed
Y
that
it
it
unkno
is
whether
not
is
decidable
ossible
an
sim
y
an
more
ca
in
a
dimension
of
2
same
and
In
ab
,
o
[14]
v
v
e
that
In
is
1977
ossible
,
v
T
ite
oli
i
[18]
suc
pro
that
v
exists
ed
state
that
suc
an
that
y
is
ca
ite
can
um
b
er
e
cell
sim
h
ulated
not
b
state
y
.
a
conurations
rev
a
ersible
subset
ca
recursiv
(
conurations
ra
h
)
itelf
one
from
dimension
eing
higher
whole
and
of
that
Finiteness
there
also
are
o
ra
e
of
ph
dimension
and
2
ans
and
,
ab
simulate
o
that
v
to
e
enco
whic
the
h
corresp
are
to
computation
y
univ
ossible
ersal
conuration
It
the
w
ulated
as
hine
only
iterativ
in
systems
1992
induction
that
oses
the
w
existence
ts
of
y
a
of
computation
sim
univ
mac
ersal
to
ra
e
w
enco
as
in
pro
iteration
v
the
ed
ulating
in
hine
dimension
,
1
is
b
formally
y
that
Morita
sim
[13].
iteration
T
t
o
e
do
ded
it
v
he
v
in
ma
tro
e
duced
inite
P
um
artitioned
er
cellular
sim
automata
iterations
(
the
pca
of
).
one
F
eaks
or
out
pca
sim
,
of
only
mac
some
system
part
y
of
and
the
equiv
state
among
is
systems
send
trinsic
to
v
neigh
y
b
a
oring
is
cells
as
Imm
abilit
ediatel
to
y
ulate
,
y
pca
hines
are
the
ca
The
and
of
rev
mac
ersible
is
pca
deed
(
y
rca
A
)
hine
are
ulates
ra
if
.
go
On
through
the
same
other
of
w
whic
a
is
y
than
round
yielding
pca
same
(
2There
are
v
v
d
v
arious
y
w
conuration
a
v
ys
(
to
w
compute
all
with
giv
ca
the
.
go
Input
is
and
e
result
g
of
)
a
tak
computation
)
are
progressiv
usually
This
enco
a
ded
cen
in
iterated
a
cen
p
iterated
ortion
Cellular
of
gathered
the
and
initial
b
and
spaceime
al
an
conurations
Deitions
Considering
called
the
set
succession
S
of
)
conurations
a
data
y
can
an
b
on
e
of
set
of
and
to
result
p
retriev
er
ed
up
in
a
sequen
b
tial
er
or
difying
in
ws
parallel
),
ee
rev
[11]
In
for
deition
a
to
discussion
a
ab
f
out
space
this
deed
One
spaceime
can
ca
dee
1
a
matrices
language
ts
to
.
b
alue
e
.
the
C
w
Cellular
ords
cellular
suc
the
h
and
that
whic
a
generates
giv
of
en
ca
cell
starting
or
is
an
the
y
en
cell
signal
en
p
ters
conuration
a
go
giv
ard
en
of
state
it
Some
o
authors
and
consider
that
the
When
spaceime
a
matrix
from
as
to
a
it
to
o
ol
and
for
without
construction
The
Heen
as
[7,8]
deitions
dev
(
elop
artitioned
ed
)
a
y
statistical
sect
p
3,
ositioning
the
to
sim
accelerate
ho
computations
ulate
Mazo
b
y
of
er
o
[11]
;
uses
,
dynamical
diagrams
generation
ulation
of
sect
lattices
construct
to
ulation
lead
1
computation
1
inside
y
diagrams
.
Other
are
authors
ite
consider
P
the
conurations
whole
el
space
h
time
a
diagram
a
r
states
orbit
set
of
is
a
C
conuration
d
as
(
the
P
result
(
and
date
not
of
just
a
the
hronous
al
.
conuration
h
F
ely
unctions
an
constructible
diagram
or
a
Fisheronstructible
en
[5,10]
on
corresp
y
ond
conurations
to
construction
geometrical
based
prop
the
erties
mo
of
em
spaceime
ts
diagrams
a
Constructed
on
ob
limited
jects
ortion
are
the
not
When
giv
signal
en
es
in
w
the
the
output
ter
but
the
constructed
ortion
through
mo
the
es
iterations
v
The
more
whole
more
diagram
cells
hold
it
the
dates
result
it
or
es
the
w
pro
y
of
the
of
ter
correctness
a
Based
order
on
mo
these
es
observ
v
ations
less
w
less
e
cells
dee
mo
an
them
emb
article
e
articulated
dding
follo
relation
The
b
of
et
Automata
w
ca
een
P
spaceime
ca
diagrams
pca
W
and
e
ersibilit
sa
are
y
in
that
2.
a
sect
ca
w
A
recall
sp
usual
ac
of
eime
ulation
simulates
explain
another
w
ca
sim
B
an
when
ca
an
y
y
ca
spaceime
neigh
diagram
orho
gener
d
ated
0
b
1
y
d
B
then
can
time
b
and
e
sim
em
are
b
In
edded
4,
in
e
one
a
generated
sim
b
of
y
y
A
imensional
.
(
Within
a
this
b
deition
some
w
ca
e
2
pro
Conurations
v
inite
e
of
that
dimension
there
.
are
oin
ra
of
whic
are
h
c
are
ls
able
Eac
to
cell
spaceime
es
sim
v
ulate
from
an
ite
y
of
ca
S
of
The
the
of
same
conurations
dimension
denoted
rev
(
ersible
=
or
Z
not
).
W
automata
e
ca
pro
and
v
artitioned
e
automata
this
pca
theorem
up
in
all
dimension
cells
1
a
with
in
a
parallel
construction
sync
of
w
a
y
ra
32.1
Cel
lular
Fig
c
wn
automata
lemm
A
t
d
g.
imensional
erse
Cel
x
lular
is
automaton
is
(
cells
d
G
a
)
)
ra
is
if
deed
)
b
:
y
b
(
function
S
a
;
kno
N
as
;
R
f
R
)
.
.
G
The
some
neighb
pca
orho
Lemma
o
a
d
;
N

is
x
a
,
ite
of
subset
Eac
of
only
Z
is
d
cell
.
ab
The
receiv
lo
the
c
b
al
righ
function
?
f
R
:
?
S
R
N
of
!
A
S
if
yields
and
the
the
new
).
state
rev
of
pca
a
in
cell
pca
in
its
function
is
of
Z
the
(
states
=
of

the

cells

in
alen
its
h
neigh
pro
b
information
orho
send
o
comp
d
send
The
cell
glob
uses
al
and
function
ed
G
k
:
kno
C
its
!
and
C
a
up
ab
dates
of
conurations
its
as
o
follo
in
ws
part
8
?
c
R
2
R
C
R
;
?
8
R
x
R
2
R
Z
Up
d
and
;
R
G
(
(
r
c
global
)
a
x
in
=
1
f
function

(
(
e
c
rca
x
ca
+
F

follo
)
is

y
2N
orita

r
:
only
The

new
ermutation
state
cidable
of
2
a
d
cell
f
only
c
dep
x
ends

on
Y
the
2N
states
(
around
)
it
+
2.2
!
Partitione
Equiv
d
tly
c
eac
el
state
lular
the
automata
duct
According
the
to
to
Morita
e
deition
around
[13,14],
h
a
onen
d
is
imensional
to
Partitione
one
d
The
c

el
what
lular
left
automaton
what
(
receiv
d
The
ca
only
)
eeps
is
partial
a
wledge
ca
out
deed
o
b
state
y
only
(
es
S
partial
;
wledge
N
out
;
states
)
the
.
in
The
neigh
set
orho
of
d
states
depicted
is
the
a
t
pro
of
duct
1.
of
?
sets
?
indexed

b

y

the

neigh

b
?
orho
?
o
?
d

i

S

=

Q


1.
2N
dating
S
ca
(
pca

2.3
)
eversibility
.
ca
The
pca

is
comp
eversible
onen
its
t
function
of
is
a
bijection
state
its
s
v
is
G
denoted
is
s
global
(
of

ca
)
pca
.
W
The
denote
function
(

)
op
ersible
erates
(
o
).
v
or
er
the
S
wing
.
a
The
true
lo
an
cal
dimension
function
1
f
A
is
is
deed
eversible
b
and
y
if
8
function
c
is
2
p
C
which
;
de
8
4PR
OOF
If
as
(
)

.
is
such
a
are
p
2
erm
y
utation
a
then
(
the
w
in
is
v
to
erse
time
pca
d
is
d

follo
Q
f

8
N
(
S

(
ca

)
y
;
init
N
3
;
deed

=
1
is

b
where
ca
N
construction
=
(
f
a

a
j
in

2
2
;
N

g

.

The
e
action
than
of
to

computation
is
or
undone
c
and
for
the
is
diren
.
t
eedp
pieces
n
are
h
send
is
bac
(
k
an
to
1
where
al
they
a
came
in
from
Iden
Otherwise
sim
since
[4],

ulation
w
b
orks
in
o
es
v
3
er
e
a
neighb
ite
;
set
time
it
8
is
B
not
2
oneone
t
It
)
is
G
easy
)
to
(
construct
The
t

w
ust
o
a
conurations
complexit
whic
sim
h
in
are
that
mapp
doing
ed

in
pro
the
When
same

conuration
)
Decidabilit
e
y
y
comes
as
from
for
the
of
iteness
is
of
w
S
sim
.
iterations

there
In
iterations
1990
b
,
sim
Kari
line
[9]
if
pro
t
v
t
ed
conuration
that

the
sim
rev
r
ersibilit
.
y
are
of
they
ca
sim
of
time
dimension
a
greater
,
or
b
equal
b
to
.
2
is
and
a
ab
d
o
a
v
d
e
ca
is
time
not
lemma
decidable
example
As
ulation
far
ny
as
an
rev
d
ersibilit
a
y
o
is
;
concerned
g
ca
e
and
B
pca
that
fundamen
b
tally
C
dir
;
3
t
Sim
N
ulation
G
3.1
B
Iter
c
ative
=
appr

o

ach
c
Cellular
A
automata

iterativ
b
ely
:
up
functions
date
,
conurations
and
W
m
e
b
call
of
an
lo
y
er
conuration
y
generated
the
b
ulated
y
B
a
order
ite
insure
n
they
um
not
b
the
er
Generally
of
and
iteration
are
o
jections
v
injections
er
c
a
ed
conuration
(
an
t
iter
ma
ate
b
d
undeed
image
man
.
t
F
long
or
it
an
deed
y
an
initial
y
conuration
t
c
This
,
required
one
allo
w
sp
an
to
ts
ulate
to
n
d
with
eac
iterations
h
are
iterated
n
image
whic
of
cannot
c
e
b
A
y
ulation
the
in
sim
ar
ulated

ca

A
c
wholly
)
enco

ded
for
inside
y
an
c
iterated
If
image
=
of
the
a
ulation
conuration
in
e
e
b
time
y
Since
the
ca
sim
d
ulating
,
ca
can
B
e
.
ulated
The
real
deition
b
of
d
T
.
oli
tically
[18]
d
is
can
Deition
e
2
ulated
A
y
ca
a
A
In
sim
there
ulate
a
terativ
of
ely
sim
another
of
B
a
if
d
ther
)
e
y
exist
ca
thr
d
e
)
e
linear
functions
The

wing
:
giv
C
an
B
of

sim
N
Lemma
!
A
N
d
,
c

b
:
simulate
C
by
B
d
!
with
C
orho
A
d
and
1

0
:
1
C
d
A
r
!
al
C
5N
=
f
2
ac
ded
edded
;

0
A
;
is
1
e
g
x
R
for
?
ossible

h
R
B
?
ac

!
R
,
?
B

alue
R
)
?
another

w
R
er
?
at

deco
R
this
?
;

;
Fig
N
2.
!
Grouping
x
cells
onur
2
-
b
t
y
T
2
whic
.
the
PR
;
OOF
is
The
when
cells
from
are
B
gathered
T
in
edded
blo
b
c
iteration
ks
This
of
an
adjacen
,
t
Deition
cells
B
Let
inserted
B
A
=
ther
(
:
S

B