THE SIGNAL POINT OF VIEW: FROM CELLULAR AUTOMATA TO SIGNAL MACHINES

Jérôme Durand-Lose

Description

Niveau: Supérieur, Doctorat, Bac+8
THE SIGNAL POINT OF VIEW: FROM CELLULAR AUTOMATA TO SIGNAL MACHINES Jerome DURAND-LOSE 1 1 Laboratoire d'Informatique Fondamentale d'Orleans, Universite d'Orleans, B.P. 6759, F-45067 ORLEANS Cedex 2. URL: E-mail address: Abstract. After emphasizing on the use of discrete signals in the literature on cellular automata, we show how these signals have been considered on their own. We then present their continuous counterpart: abstract geometrical computation and signal machines. Fi- nally we relate them to other models of computation, classical and analog. Key-words. abstract geometrical computation, analog/continuous computation, black hole model, cellular automata, computability and signal machines. 1. Introduction Cellular automata (CA) were introduced in the 1950's and have been used as a model for self-replication, computation, hardware, physics, economics. . . They are composed of identical automata, called cells displayed on a regular lattice and communicating only with neighbors. The dynamics, defined by the transition function of a cell, is parallel and syn- chronous. Different points of view are commonly used: considering a single cell or an entire configuration or the whole space-time diagram. In the past decades, a new point of view has emerged: the cells are just a substrata on which information travels.

• design special purpose


• continuous counterpart


• signals can


• time diagrams


• space-time diagram


• usual both


• increasing downward


• move only

Informations

• Publié par: profil-zyak-2012
• Nombre de lectures: 15
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

THE SIGNAL POINT OF VIEW:
FROM CELLULAR AUTOMATA TO SIGNAL MACHINES
1J´erˆome DURAND-LOSE
1 Laboratoire d’Informatique Fondamentale d’Orl´eans, Universit´e d’Orl´eans, B.P. 6759, F-45067
´ORLEANS Cedex 2.
URL: http://www.univ-orleans.fr/lifo/Members/Jerome.Durand-Lose
E-mail address: [e-mail]
Abstract. After emphasizing on the use of discrete signals in the literature on cellular
automata, we show how these signals have been considered on their own. We then present
their continuous counterpart: abstract geometrical computation and signal machines. Fi-
nally we relate them to other models of computation, classical and analog.
Key-words. abstract geometrical computation, analog/continuous computation, black
hole model, cellular automata, computability and signal machines.
1. Introduction
Cellular automata (CA) were introduced in the 1950’s and have been used as a model
for self-replication, computation, hardware, physics, economics... They are composed of
identical automata, called cells displayed on a regular lattice and communicating only with
neighbors. The dynamics, defined by the transition function of a cell, is parallel and syn-
chronous. Different points of view are commonly used: considering a single cell or an entire
configuration or the whole space-time diagram.
In the past decades, a new point of view has emerged: the cells are just a substrata on
which information travels. The atomic pieces of information are signals: patterns that keep
repeating regularly. The dynamics can then be understood as well as conceived in terms of
signals.
In this paper, we show that this signal approach is quite usual both for describing CA
generated from modeling and for designing special purpose CA. Then we recall some con-
structionsondiscretesignalsandpresentsignalsinacontinuoussetting, abstract geometrical
computation before stating some of their computing capabilities.
Signals are embedded inside a discrete structure: both space and time are discrete. On
space-time diagrams they correspond more or less to discrete lines. On the one side, the
granularity of space is often exploited to get a natural scale and to get a halting condition
(for example to finish a Firing squad synchronization). On the other side it imposes a quite
cumbersome setting: discrete geometry; for example halfway between two cells is either on
a cell or between two cells.
Submitted to JAC (Symposium on Cellular Automata Journ´ees Automates Cellulaires)
12 J. DURAND-LOSE
To generate special purposed CA, usually an Euclidean setting is used for conception
and then brute force and technical skills are used to discretize. The other way round, to
explain dynamics, one often forgets about the discreteness and moves on to a continuous
setting for an easier explanation. Both approaches rely on scaling invariance: if the gran-
ularity is thinner or thicker, the same phenomenon happens so that it does not depend on
the number of cells.
These observations led us to consider the continuous case on its own. On the one hand,
there is no problem with finding the middle; all positions are available. On the other hand,
there is no granularity on which to rely for an absolute scale or to ensure a correct stop.
The discrete and continuous cases have similarities; for example, both can compute (in
the classical sense) and thus have numerous related undecidability problems. Nevertheless,
the continuous model is quite different and addresses different topics. For example, the
signal approach have been very fruitful to solve the Firing squad synchronisation problem
but the constructions lead to “monsters” on the continuous side (like accumulations on a
Cantor set).
Signal machines can compute anything in the classical understanding as well as CA. In
the continuous setting, Zeno effect (infinitely many steps in a finite duration) can appear
and be used efficiently to decide semi-decidable problems, whereas in CA it is impossible.
In another direction, since it works in a continuous setting it can handle real numbers with
exact precision and be related to other analog models of computation like the Blum, Shub
and Smale one.
The paper is articulated as follows. Section2 briefly recalls what cellular automata,
space-timediagramsanddiscretesignalsare. Section3providesexamplesfromtheliterature
where signals are used a mean of explanation. Section4 presents the approach and results
on discrete signals, whereas Sect.5 presents its continuous counterpart and some results on
its computing capabilities. Conclusion and perspectives are gathered in Sect.6.
2. Cellular automata
Thissection groundsthenotations. OnlyCAwith onedimensionare addressed,almost
everything naturally extends to higher dimensions.
Definition 2.1. A cellular automaton (CA) is defined by (Q,r,f) where Q is a finite set
of states, the radius, r, is a positive integer, and the local function, f, is a function from
2r+1 Z Z ZQ to Q. A configuration is an element of Q . The global function,G : Q → Q , is
defined by:
G(c) = f(c ,c ...c ...c ,c ) .i i−r i−r+1 i i−r−1 i−r
Definition 2.2. A space-time diagram, D, is the orbit of a configuration, c . It is an0
Z×N telement of Q ,D(.,0) is c andD(i,t) isG (c) .0 i
Unless noted otherwise, space-time diagrams are represented with time increasing up-
ward. Each configuration is set right above the previous one.
The following definition is empirical. It may vary according to articles and is more
conceptual that formal.
Definition 2.3. A background is a state pattern that may legally tile a whole space-time
diagram. A signal is a pattern that is periodically repeating over a background. Its speed
is defined as the spacial shift divided by the number of iterations to repeat.THE SIGNAL POINT OF VIEW: FROM CELLULAR AUTOMATA TO SIGNAL MACHINES 3
For example, if 0 is a quiescent state (i.e. f(0,...,0) = 0) then a configuration filled
with 0 is mapped onto itself and the resulting space-time diagram is filled with 0, so that 0
is a background. If the dynamics is such that a configuration with only 0’s except for 1 on
three consecutive cells, is regenerated every other iteration shifted by one cell on the right,
then 111 is a signal and its speed is 1/2.
Thespeedsareboundedbytheradius. Thisis aspeed-of-light-like limitation. Inspace-
time diagrams, the more a signal is vertical, the more it is slow. Signals have a width: the
length of the pattern. The generated ones are generally 1-cell thin, but the ones observed
are frequently not that thin.
3. Informal use of signals
Signals are information conveyors. Thedynamics is driven by the information received,
proceeded and sent.
3.1. Analysing the dynamics
3.1.1. Particles and solitons. Signals can be thought of as moving objects. This leads to
the vocabulary of “particles”. The term “soliton” is also used, but it implies that they can
cross one another unaffected, like waves. Figure1 shows some examples from the literature.
This approach is important in physical modeling to ensure that studied objects could exist.
(b) [HSC01, Fig. 7]
(a) [BNR91, Fig. 7]
(c) [Siw01, Fig. 5]
(Time is increasing downward.)
Figure 1: Examples of particles and solitons.
3.1.2. Computing capability. In computer science, before computing better (whatever it
means), one is interested in being able to compute. In [LN90] (Fig.2), signals are found so
as to provide states and tape to simulate Turing machines.
InthequestforminimalTuring-universalandintrinsicallyuniversalcellularautomata[Oll02,
Coo04, Ric06], finding signals have often been the key to success.4 J. DURAND-LOSE
(Time is increasing downward.)
Figure 2: Signals to build an universal Turing machine [LN90, Fig. 3 and 4].
3.2. Generating particular CA
The other way round, signals have also been used to design special purpose CA.
3.2.1. Prime number generation. One application is to generate the prime numbers as the
iteration numbers with no signal on cell 0 (i.e. on the leftmost vertical line) as done on
Fig.3(a) [Fis65]. Other sets of natural numbers can be enumerated this way [MT99].
(a) [Fis65, Fig. 2] (b) Goto’s solution to FSS [Got66, Fig. 3+6]
(Time is increasing downward.)
Figure 3: Geometric algorithms.
3.2.2. Firing squad synchronization (FSS). This is a typical synchronisation problem from
distributed computing. The aim is to have all processors do something special for the first
time simultaneously. They have no way to broadcast, nor a common clock to refer to. This
is thought of as a line of soldiers that must shoot synchronously but are not aware of their
number and have very poor means of communication: each one can only communicate withTHE SIGNAL POINT OF VIEW: FROM CELLULAR AUTOMATA TO SIGNAL MACHINES 5
the closest soldier on each side. Two soldiers are particularised: the first is a general that
will start the process and the last who knows that he is the last. In CA modeling, the cells
represent the soldiers.
Most solutions work on a divide and conquer scheme. For example, Goto’s algorithm
(Fig.3(b)) cuts the line