Laboratoire Bordelais de Recherche en Informatique

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

Sujets

• Laboratoire bordelais de recherche en informatique
• University of Bordeaux
• Cellular automaton

Informations

• Publié par: profil-nechor-2012
• Nombre de lectures: 23
• Langue: English

Extrait

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