# An outer totalistic weakly universal cellular automaton in the dodecagrid
with four states

Maurice Margenstern

###### Abstract

In this paper, we prove that there is an outer totalistic weakly universal
cellular automaton in the dodecagrid, the tessellation $\\{5,3,4\\}$ of the
hyperbolic $3D$ space, with four states. It is the first result in such a
context.

##  1 Introduction

In many papers, the author studied the possibility to construct universal
cellular automata in tilings of the hyperbolic plane, a few ones in the
hyperbolic $3D$ space. Most often, the constructed cellular automaton was
weakly universal. By weakly universal, we mean that the automaton is able to
simulate a universal device starting from an infinite initial configuration.
However, the initial configuration should not be arbitrary. It was the case
that it was periodic outside a large enough circle, in fact it was periodic
outside such a circle in two different directions as far as the simulated
device was a two-registered machine. From a result by Minsky, [13], it is
enough to simulate any Turing machine. In almost all papers, the considered
tiling of the hyperbolic plane was either the pentagrid or the heptagrid, i.e.
the tessellation $\\{5,4\\}$, $\\{7,3\\}$ respectively. Both tessellations
live in the hyperbolic plane only. In the pentagrid, the basic tile is a
regular convex pentagon with right angles. In the heptagrid, it is a regular
convex heptagon with the angle $\displaystyle{{2\pi}\over 3}$ between
consecutive sides. In the present paper, we consider the dodecagrid which we
define and explain in Sub-section 1.1. In Sub-section 1.2, we remind the read
what outer totalistic cellular automata are.

###  1.1 The dodecagrid

In the present paper, we consider the tiling of the hyperbolic $3D$-space
which we call the dodecagrid whose signature is defined as $\\{5,3,4\\}$. In
that signature,

5 is the number of sides of a face, 3 is the number of edges which meet at a
vertex, 4 is the number of dodecahedrons around an edge. In the hyperbolic
$3D$-space, there is another tessellation based on another dodecahedron whose
signature is $\\{5,3,5\\}$ which means that around an edge, there should be
five dodecahedrons. From now on, we consider the dodecagrid only and its
dodecahedrons are always copies of Poincaré’s dodecahedron we denote by
$\Delta$.

Below, Figure 1 provides us with a representation of the dodecagrid according
to Schlegel representation of the solid. We shall more frequently use another
representation illustrated by Figure 3 which we shall again meet later in
Section 2. That figure makes use of a property we shall see with the
explanations about Figure 1. Before turning to that argumentation, we
presently deal with the Schlegel representation of alone $\Delta$.

Figure 1 is obtained by the projection of the vertices and the edges of a
dodecahedron of the hyperbolic $3D$-space on the plane of one of its faces.

###### Figure 1

The Schlegel representation of the dodecahedron $\Delta$.

As shown on the figure, we number the faces of $\Delta$. Face 0 is the face
whose plane is the one on which the projection is performed. We number the
faces around face 0 by clockwise turning around the face when we look at the
plane from a point which stands over $\Delta$. ’Over’ means that $\Delta$ and
the centre of the projection are on the same half-space defined by the plane
on which the projection is performed. If we consider the face which is opposed
to face 0, we also number the remaining faces of $\Delta$, they are also
clockwise numbered from 6 to 10 with face 6 sharing a side with face 5 and
another one with face 1. The not yet numbered face which is opposite to face 0
is now numbered 11. That numbering will be the basic numbering from which we
derive a numbering of the vertices and of the edges as follows: a vertex or an
edge will be denoted by the numbers of the faces which share that element, two
numbers for an edge, three ones for a vertex.

There is a problem with that representation of which the reader should be
aware. Put a dodecahedron $\Delta_{i}$ on each face $i$ of $\Delta$. Assume
that we number the faces of $\Delta_{i}$ by numbering with 0 the face of each
dodecahedron $\Delta_{i}$ which lies on the face $i$ of $\Delta$ and denote
those dodecahedrons by ${\Delta_{i}}_{0}$ respectively. Consider $\Delta_{i}$
and $\Delta_{j}$ whose faces 0 are contiguous faces of $\Delta$, which means
that both dodecahedrons share the edge shared by the faces $i$ and $j$ of
$\Delta$ with, of course $i\not=j$. We may assume the numbering of the faces
of those dodecahedrons is such that the faces 1 of $\Delta_{i}$ and
$\Delta_{j}$ also share the side $i$-$j$. We are with three dodecahedrons
around the edge $i$-$j$: $\Delta_{i}$, $\Delta_{j}$ and $\Delta$. If we put a
dodecahedron $\Delta_{ij}$, $\Delta_{ji}$ on the face 1 of $\Delta_{i}$,
$\Delta_{j}$ respectively, then, necessarily, we have
$\Delta_{ij}=\Delta_{ji}$ as far as there must be exactly four dodecahedrons
around the side $i$-$j$.

The cellular automaton we construct in Section 2 evolves in the hyperbolic
$3D$ space but a large part of the construction deals with a single plane
which we shall call the horizontal plane denoted by $\mathcal{H}$. In fact,
both sides of $\mathcal{H}$ will be used by the construction and most tiles of
our construction have a face on $\mathcal{H}$.

We take advantage of that circumstance to define another representation,
possibly more convenient for our purpose.

The trace of the dodecagrid on $\mathcal{H}$ is a tiling of the hyperbolic,
namely the tiling $\\{5,4\\}$ we call the pentagrid. The left-hand side part
of Figure 2 illustrates the tiling and its right-hand side part illustrates a
way to locate the cells of the pentagrid. Let us look closer at the figure
whose pictures live in Poincaré’s disc, a popular representation of the
hyperbolic plane, see [2].

In the left-hand side picture, we can see five tiles which are counter-
clockwise numbered from 1 up to 5, those tiles being the neighbours of a tile
which we call the central tile for convenience. Indeed, there is no central
tile in the pentagrid as there is no central point in the hyperbolic plane. We
can see the disc model as a window over the hyperbolic plane, as if we were
flying over that plane in an abstract spacecraft. The centre of the circle is
the point on which are attention is focused while the circle itself is our
horizon. Accordingly, the central tile is the tile which is central with
respect to the area under our consideration. It is also the reason to number
the central tile by 0.

The right-hand side picture shows us five blocs of tiles we call sectors. Each
sector is defined by a unique tile which shares and edge with the central one.
We number that tile by 1. It is a green tile on the picture. The sector is
delimited by two rays $u$ and $v$ issued from a vertex of tile 1: they
continue two consecutive sides of tile 0. Those rays are supported by straight
lines in the hyperbolic plane and they define a right angle. Tile 1 is called
the head of the sector it defines : the sector is the set of tiles contained
in the angle defined by $u$ and $v$. We also number the sectors from 1 to 5 by
counter-clockwise turning around tile 0. We also say that two tiles are
neighbouring or that they are neighbours of each other if and only if they
have a common side.

###### Figure 2

To left: a representation of the pentagrid in Poincarés disc model of the
hyperbolic plane. To right: a splitting of the hyperbolic plane into five
sectors around a once and for all fixed central tile.

Consider the configuration illustrated by Figure 3. We can see the Schlegel
projection of a dodecahedron on each tile of the picture. A few dodecahedrons
have another light colour and on each of them, some faces are green and a few
ones are red. We call them the elements of a track.

###### Figure 3

A configuration we shall later meet in Section 2. The central tile is, in some
sense, the centre of that configuration. A green, red face means that a green,
red dodecahedron respectively is put on that face.

Tile 0 is the central tile of the picture. Around tile 0, we can see three
elements of track exactly, the other i neighbouring tiles having a uniform
light colour: we call them blank tiles. We number the elements of tracks by
the number of their sectors, here 1, 3 and 5 by counter-clockwise turning
around tile 0. On the picture, tile 3 is just below tile 0. Let us look closer
at tiles 0 and 3 of $\mathcal{H}$. Let $\Delta_{0}$ and $\Delta_{3}$ be the
tiles of the dodecagrid which are put on tiles 0 and 3 of $\mathcal{H}$
respectively. Assume that the face 1 of $\Delta_{0}$ and of $\Delta_{3}$ share
the side which is shared by the tiles 0 and 3 of $\mathcal{H}$. By
construction of the dodecagrid, below $\mathcal{H}$, there are also two
dodecahedrons, one below $\Delta_{0}$, the other below $\Delta_{3}$.
Accordingly, the face 1 of $\Delta_{0}$ and that of $\Delta_{3}$ coincide as
far as four dodecahedrons share the common side of tiles 0 and 3 of
$\mathcal{H}$. Using the numbering of the faces of $\Delta_{0}$ and
$\Delta_{3}$ just above defined, we can see that if we put a dodecahedron on
the faces 6 of $\Delta_{0}$ and $\Delta_{3}$ those dodecahedrons share a face
which is on the same plane as the common face 1 of $\Delta_{0}$ and
$\Delta_{3}$. Consider, for instance, the faces 6 and 7 of $\Delta_{0}$ which
also share a common side of $\Delta_{0}$. Put a dodecahedron $D_{i}$ on the
face $i$ of $\Delta_{0}$. Then $D_{6}$ and $D_{7}$ have no common face: their
common side is shared by a fourth dodecahedron outside $\Delta_{0}$, $D_{6}$
and $D_{7}$ as just indicated. Accordingly, we have to pay attention to
dodecahedrons which are put on the faces of a dodecahedron in the
representation as defined on Figure 3: we call that representation the
$\mathcal{H}$-representation. The rule is simple: two dodecahedrons sharing an
edge $s$ in the $\mathcal{H}$-representation also share their face sharing $s$
if and only if $s$ is also a common side of the tiles of $\mathcal{H}$ on
which those faces are projected.

As mentioned in the caption of Figure 3, a dark blue face of the projection of
a dodecahedron means that, in the dodecagrid, a dark blue dodecahedron is put
in that face. By abus de langage, we also call $\mathcal{H}$ the restriction
of the dodecagrid to those which sit on that plane. When it will be needed to
clarify, we denote by $\mathcal{H}$u, $\mathcal{H}$b the set of dodecahedrons
which are placed upon, below $\mathcal{H}$ respectively.

###  1.2 Outer totalistic cellular automata

Let us remind the reader that cellular automata are a model of massive
parallelism. The base of a cellular automaton is a cell. The set of cells is
supposed to be homogeneous in several aspects: the neighbours of each cell
constitute subsets which have the same structure; the cell changes its state
at each tip of a discrete clock according the states of its neighbours and its
own state. The change is dictated by a finite automaton which is the same for
each cell. A regular tiling is an appropriate space for implementing cellular
automata: a cell is the combination of a tile together with the finite
automaton ruling the change of states. The tile is called the support of the
cell. Let $T$ be a tile and let $N(T)$ be the set of its neighbours. By
regular, we mean that the number of elements of $N(T)$ is the same for any
$T$. The dodecagrid satisfies that requirement. Moreover, there is an
algorithm to locate the tiles which is cubic in time in the size of the code
attached to each tile, see [3] for instance. However, taking benefit of
$\mathcal{H}$, we inherit of the linear algorithm allowing us to locate the
tiles of $\mathcal{H}$. That use is reinforced by the face that our incursions
in the third dimension will not lead us far from $\mathcal{H}$. From now on we
indifferently say tile or cell for a dodecahedron of the dodecagrid, confusing
the cell with its support.

The way the automaton manages the change of states can be defined by a finite
set of rules we shall call the program of the automaton and we shall organise
it in a table we shall display by pieces only. In Section 3, we define the
format of the rules. However we need not enter such details in order to define
outer totalistic cellular automata. The alphabet $\mathbb{A}$ of the automaton
attached to each cell is the set of the possible states taken by the cell.
Define an order on $\mathbb{A}$ so that we can write
${\mathbb{A}}=\\{e_{0},...,e_{n}\\}$, so that $n$+1 is the number of states.
By definition, the index of the state $e_{i}$ is $i$. The cellular automaton
is said to be outer totalistic if the state at time $t$+1 of a cell $\kappa$
exactly depends both on the state at time $t$ of $\kappa$ and on the sum of
the indices of the states at time $t$ of all $\lambda$ for $\lambda\in
N(\kappa)$, we call it the weight of the neighbours. The cellular automaton is
said totalistic if the state at time $t$+1 of $\kappa$ depends on the sum of
weight of the cell at time $t$ and of the state of $\kappa$ at time $t$. The
maximal value for the weight of the neighbours of a cell $\kappa$ is
$n$+1$\times|N(\kappa)|$. Call that sum the maximal weight for a rule.

Now that the global setting is given, we shall proceed as follows: Section 2
indicates the main lines of the implementation which is precisely described in
Subsection 2.2. At last, Section 3 gives us the rules followed by the
automaton. That section also contain a few figures which illustrate the
application of the rules. Those figures were established from pieces of
figures drawn by a computer program which applied the rules of the automaton
to an appropriate window in each of the configurations described in Subsection
2.2. The computer program also computed the sum of states of the neighbour of
a cell.

That allowed us to prove the following property:

###### Theorem 1

There is a weakly universal cellular automaton in the dodecagrid which is
outer totalistic and truly spatial. Its automaton has four states and the
maximal sum of states in the neighbourhood of a cell is $21$, less than the
half of the maximal weight for a rule.

##  2 Main lines of the computation

The first paper about a universal cellular automaton in the pentagrid, the
tessellation $\\{5,4\\}$ of the hyperbolic plane, was [1]. That cellular
automaton was also rotation invariant, at each step of the computation, the
set of non quiescent states had infinitely many cycles: we shall say that it
is a truly planar cellular automaton. That automaton had 22 states. That
result was improved by a cellular automaton with 9 states in [12]. Recently,
it was improved with 5 states, see [7]. A bit later, I proved that in the
heptagrid, the tessellation $\\{7,3\\}$ of the hyperbolic plane, there is a
weakly universal cellular automaton with three states which is rotation
invariant and which is truly planar, [8]. Later, I improved the result down to
two states but the rules are no more rotation invariant, see [9]. Paper [4]
constructs three cellular automata which are strongly universal and rotation
invariant: one in the pentagrid, one in the heptagrid, one in the tessellation
$\\{5,3,4\\}$ of the hyperbolic $3D$-space. By strongly universal we mean that
the initial configuration is finite, i.e. it lies within a large enough
circle.

In the present paper, as we go back to weak universality, we take the general
frame of the quoted papers. For the convenience of the reader, we repeat the
main ideas in Sub-section 2.1 and we focus on the specificity of the present
paper in Sub-subsection 2.2.

###  2.1 The railway model

The simulation is based on the railway model devised in [14] which lives in
the Euclidean plane. It consists of tracks and switches and the configuration
of all switches at time $t$ defines the configuration of the computation at
that time. There are three kinds of switches, illustrated by Figure 4. The
changes of the switch configurations are performed by a locomotive which runs
over the circuit defined by the tracks and their connections organised by the
switches.

A switch gathers three tracks $a$, $b$ and $c$ at a point. In an active
crossing, the locomotive goes from $a$ to either $b$ or $c$. In a passive
crossing, it goes either from $b$ or $c$ to $a$.

###### Figure 4

The switches used in the railway circuit of the model. To left, the fixed
switch, in the middle, the flip-flop switch, to right the memory switch. In
the flip-flop switch, the bullet indicates which track has to be taken.

In the fixed switch, the locomotive goes from $a$ to always the same track:
either $b$ or $c$. The passive crossing of the fixed switch is possible. The
flip-flop switch is always crossed actively only. If the locomotive is sent
from $a$ to $b$, $c$ by the switch, it will be sent to $c$, $b$ respectively
at the next passage. The memory switch can be crossed actively or passively.
Now, the track taken by the locomotive in an active passage is the track taken
by the locomotive in the last passive crossing.

###### Figure 5

The basic element containing one bit of information.

Figure 5 illustrates the circuit which stores a one-bit unit of information.
The locomotive may enter the circuit either through the gate $R$ or through
the gate $W$.

If it enters through the gate $R$ where a memory switch sits, it goes either
through the track marked with 1 or through the track marked with 0. When it
crossed the switch through track 1, 0, it leaves the unit through the gate
$B_{1}$, $B_{0}$ respectively. Note that on both ways, there are fixed switch
sending the locomotive to the appropriate gate $B_{i}$. Note that when the
locomotive leaves the unit, no switch was changed. If the locomotive enters
the unit through the gate $W$, it is sent to the gate $R$, either through
track 0 or track 1 from $W$. Accordingly, the locomotive arrives to $R$ where
it crosses the switch passively, leaving the unit through the gate $E$ thanks
to a fixed switch leading to that latter gate. When the locomotive took track
0, 1 from $W$, the switch after that indicates track 1, 0 respectively and the
locomotive arrives at $R$ through track 1, 0 of $R$. The tracks are numbered
according to the value stored in the unit. Note that when the locomotive
leaves the unit, two switches were changed: the flip-flop at $W$ and the
memory switch at $R$.

By definition, the unit is 0, 1 when both tracks from $W$ and from $R$ are 0,
1 respectively. So that, as seen from that study, the entry through $R$
performs a reading of the unit while the entry through $W$, changes the unit
from 0 to 1 or from 1 to 0: the entry through $W$ should be used when it is
needed to change the content of the unit and only in that case. The structure
works like a memory which can be read or rewritten. It is the reason why call
it the one-bit memory.

We shall see how to combine one-bit memories in the next sub-section as far as
we introduce several changes to the original setting for the reasons we
indicate there.

###  2.2 Tuning the railway model

We first look at the implementation of the tracks in Sub-subsection 2.2.1 and
how it is possible to define the crossing of two tracks. In Sub-subsection
2.2.2 we see how the switches are implemented. Then, in Sub-subsection 2.2.3,
we see how the one-bit memory is implemented in the new context and then, in
Sub-section 2.2.4, how we use it in various places. At last but not the least,
we shall indicate how registers are implemented in Sub-subsection 2.2.5.

####  2.2.1 The tracks

The tracks play a key role in the computation, as important as instructions
and registers: indeed, they convey information without which any computation
is impossible. Moreover, as can be seen in many papers of the author, that one
included, it is not an obvious issue which must always be addressed.

It is not useful to list the similarities and the distinctions between the
present implementation and those of my previous papers. The best is to focus
on the implementation used by this paper. If the reader is interested by the
comparison with previous implementations the references already indicated give
him/her access to the corresponding papers.

The tracks are one-way. It is already needed by the constraint of outer
totalisticity. Indeed, in previous papers, the elements of tracks consist of a
blank cell with a few non-blank neighbours placed at appropriated places. We
indicate those non-blank neighbours as well as their places by the word
decoration. In previous papers, the motion was organised according to the
following scheme:  WWW LWW WLW WWL (1)  Under the constraint of outer
totalisticity, such a scheme cannot work: if all elements of the track are
identical and if the moving state is always the same, the sum of indices of
the non-blank states in the neighbourhood is the same in all the above
patterns so that as far as L occurs in a cell, it is seen by two neighbouring
cells. Accordingly, L will appear in both neighbours of the cell, which is not
what is expected. Accordingly, we replace (1) by the following scheme :
3B234234 34R34234 342G4234 3423B234 3423B234 342342R4 (2)  The motion is
represented by a moving locomotive which successively takes different colours
in consecutive cells which differ by their decorations according to a periodic
pattern. The successive pattern is defined by 234 where 2, 3 and 4 refer to
the number of non-blank cells in the corresponding decorations of the cells as
illustrated by Figure 6.

Now, as soon will be seen, we need a two-way circulation in some portions of
the circuit. It is a point where the third direction comes to help us. In many
portions, the circuit can be implemented on a fixed plane we call
$\mathcal{H}$, already mentioned in the introduction. Roughly speaking, the
traffic in one direction will occur in $\mathcal{H}$u, $\mathcal{H}$b while
the reverse running will be performed in $\mathcal{H}$b, $\mathcal{H}$u
respectively. Occasionally and locally, we shall use a plane $\mathcal{V}$
which is orthogonal to $\mathcal{H}$.

The present organisation of the one-way tracks is very different from all the
implementations described in the previous papers of the author. As already
mentioned, we mark the elements of a track by milestones whose set constitutes
the decoration of the element. But here, the decorations are different and
their succession is performed according to the periodic repetition of the same
pattern, namely 234 ,as already indicated. As in [11], the return motion along
a track in $\mathcal{H}$u, $\mathcal{H}$b is performed along another track
which is placed in $\mathcal{H}$b, $\mathcal{H}$u respectively. But,
contrarily to [11], the elements of the return track does not share its face 0
with that of the direct track. In order to make things more accurate, we say
that a track is a sequence of elements such that its consecutive members can
see each other but it cannot see other elements outside its neighbours in the
sequence. Moreover, we require that each element of the track has a side on a
line of $\mathcal{H}$ which indicates the direction of the track. We say that
the track follows that line. We define a path to be a sequence of tracks which
are linked in some way which will be later explained. Elements in a path are
imposed the same conditions as elements in a track with respect to the
elements they can see. The left-hand side part of Figure 7 illustrates a track
while its right-hand side part illustrates the same track together with its
return track.

###### Figure 6

Three consecutive elements of a track illustrating the pattern 234 .

###### Figure 7

To left, a track, to right its return track. They both follow the same line.

On that latter part of the figure, note that the return track follows the same
line as the direct one, but it lies in the other half-space with respect to
$\mathcal{H}$. As long as it will be possible, the return track will follow
the line followed by the direct one. Also note that the direction of the
motion is defined by the order of the decorations in the patter 234 .It is a
reason why we need a pattern with three elements: with two ones, the
orientation would be ambiguous. Another reason is given by the totalistic
constraint: a two-elemented pattern would also raise ambiguity.

The decorations of the elements in the pattern 234 are defined by (3):  2
$\Rightarrow$ $\Delta_{i}$, $i$ = 7, 8:G , others:W 3 $\Rightarrow$
$\Delta_{i}$, $i$ = 7, 8:G , 11:R , others:W 4 $\Rightarrow$ $\Delta_{i}$, $i$
=7, 8, 10:G , 11:R , others:W (3)

The indices of the neighbours constituting the decoration of an element of the
track in (3) are not at all mandatory. The reason is that the new state of the
cell depends on its current state and on the sum of the current states of its
neighbours. That sum does not depend on which faces the milestones are placed.
That feature gives us some freedom in the place of the milestones. The main
constraint is that the milestones of an element $\eta$ of the track $\tau$
should not be seen by a neighbour of $\eta$ also belonging to $\tau$. Also, it
should not be seen by the elements of the return track of $\tau$. The
constraint given in the definition of the return track entails that an element
of the return track of a track $\tau$ cannot see any element of $\tau$. As we
consider that, most often, the face 0 of an element of the track lies on
$\tau$, we may consider that the milestones belong to the upper crown of the
element and that their place in the crown is most often arbitrary. Of course,
we shall mention the right place when it is needed to fix it.

The freedom which is given by the totalistic condition gives us a large
flexibility in order to connect two consecutive tracks of a path. We postpone
a more precise description to the next sub-subsection, Sub-subsection 2.2.2.

####  2.2.2 The switches

We define a path joining $A$ to $B$, where $A$ and $B$ are two tiles of the
dodecagrid, as a sequence $\\{T_{i}\\}_{i\in\\{0..n-1\\}}$ of tiles such that
$T_{i}$ and $T_{i+1}$ can see each other for $0\leq i<n$-1 but $T_{i}$ and
$T_{j}$ cannot see each other if $|i-j|>1$. We say that $n$ is the length of
the just mentioned path joining $A$ to $B$. We call distance from $A$ to $B$,
denoted by dist$(A,B)$, the shortest length among the lengths of the paths
joining $A$ to $B$. Clearly, dist$(A,B)=0$ if and only if $A=B$. Clearly too,
that distance satisfies the triangular inequality. A circle of radius $r$ in
$\mathcal{H}$ around $T$ in $\mathcal{H}$ is the set of tiles in $\mathcal{H}$
whose distance from $T$ is $r$. Removing the condition to be in $\mathcal{H}$
we get a sphere of radius $r$ around $T$. A ball of radius $r$ around $T$ is
the set of tiles in all spheres of radius $\rho$ around $T$ with $\rho\leq r$.
If $T\in~{}$$\mathcal{H}$, the trace in $\mathcal{H}$ of a ball of radius $r$
around $T$ is a disc of radius $r$ around $T$. In many figures in the
Poincaré’s disc, what we call a window focusing on a tile $T$ is a disc of
radius 3 around $T$.

The section follows the implementation described in [5]. We reproduce it here
for the reader’s convenience. The illustrations of the section show us what we
call an idle configuration. The view given by such pictures is a window
focusing on what we call the centre of the switch. An idle configuration is a
configuration where there is no locomotive within the just defined window.
Figure 8 shows us three windows focusing on the central tile of a passive
fixed switch: according to what we said in Section 2.2, there is no active
fixed switch.

In the three configurations of Figure 8, the left-hand side track is the same.
There is just a change in the place of the G -tiles of the decoration of the
central tile as mentioned in the caption of the figure. In the leftmost
picture, the abutting tracks at the central cell place two 3 -tiles as
neighbours of the central tile.

In the middle picture of the figure, if we continued the right-hand side
track, it would place a 2 -pattern as a neighbour of the central cell instead
of a 3 -one. It is the reason why the right-hand side track is replaced by a
path which consists of the following tiles: (4)-37, (4)-76, (4)-27, (4)-2,
(3)-1. The number inside parentheses refers to the sector, then the second
number is that of the tile in the sector and the possible lower index $i$
refers to the $i$-neighbour of the tile. Note that the just mentioned elements
satisfy the conditions put on elements of a path. Keeping the same notation,
we note that (4)-3 is a 4 -tile, so that implementing the 234 -pattern we get,
starting from (4)-3: 423423 .Accordingly, (3)-1 becomes a 3-tile and it is a
neighbour of the central tile which is a 4-tile, so that the expected pattern
is continued. We can conclude that the motion we defined in Sub-subsection
2.2.1 is possible on that implementation of the passive fixed switch.

###### Figure 8

Idle configurations of a passive fixed switch. Note that in the central tile
of the rightmost picture, the place of the 4 -tiles is not the same as in the
central tile of the other pictures, but the number of those tiles is the same
in the three pictures.

In the rightmost picture of Figure 8, the right-hand side track would abut the
central tile with a 4 -tile, which does not fit the 234  period. We replace
that tile by the following path: (4)-37, (4)-76, (4)-27, (4)-2, (4)-26,
(3)-16, (3)-16,7, (3)-17, 07. In the figure, the tile (3)-16,7 is not
represented but its two neighbours (3)-16 and (3)-17 are represented with a
different colour as the other tiles of that path whose elements observe the
conditions of an element of a path with respect to its neighbours in the path.
Starting from 3 at (4)-3, we get: 3423423423 , so that 07 is a 3 -tile, which
is in agreement as a neighbour of 0, as far as 0 is a 4 -tile.

Accordingly, we have the solution for implementing the passive fixed switch.
We fix the central tile on a tile $T$ of a path provided that it is a 4 -tile.
If the arriving right-hand side branch falls as in the leftmost picture of
Figure 8, there is nothing to do. If it is not the case we are then either in
the situation of the middle picture of that figure or in the situation
described by the right-hand side picture. We shall use that solution in other
situations.

We can now turn to the fork, another structure close to the fixed switch.
Indeed, we can see the fork as a reverse passive fixed switch. The totalistic
condition allows us to keep an element of the track as central tile of the
fork.

We decide that the central tile of the fork is a 2 -tile. Accordingly,
depending on conditions at the other end of the paths leaving the fork, it may
be needed to tune the arrival at the fork. It is illustrated by Figure 9 which
implements the same solutions as in Figure 8 for the passive fixed switch.

###### Figure 9

Idle configuration of a fork

We remain with the implementation of the controller. We postpone its precise
description to Section 3 as far as the controller has a special decoration as
well as the tile which gives access to the controller.

Before turning to the more complex switches, we have to look at the
implementation of crossings. We take advantage of the flexibility given by the
totalistic constraint for that purpose. Figure 10 illustrates the
implementation of a tunnel in order to define a crossing. The figure shows us
two tracks, one following a red line, the other following a blue line. The
left-hand side picture is a projection on $\mathcal{H}$ while the right-hand
side one is a projection on $\mathcal{V}$, a plane which is perpendicular to
$\mathcal{H}$ and which contains the blue line.

In the projection on $\mathcal{V}$, we can see that a path joins a tile in
$\mathcal{H}$u to another one in $\mathcal{H}$u which is on the other side of
the red line. More other, that path does not contain a neighbour of the
central tile, neither by the element themselves nor by the tiles belonging to
the decorations of those elements. We can see that two elements of the path
represented in $\mathcal{V}$ around the central tile are share a vertex only
with the tile which is represented by the central tile in the projection over
$\mathcal{H}$. Not that it could also be possible to organise the crossing as
a bridge over one of the tracks, but that would involve more tiles in the
path.

###### Figure 10

Idle configuration of a tunnel. To left, projection on $\mathcal{H}$. To
right, projection on $\mathcal{V}$.

We are now ready to investigate the flip-flop and the memory switches.

The flip-flop switch and both parts of the memory switch require a much more
involved situation. The global view of an idle configuration of the flip-flop
is illustrated by Figure 11.

###### Figure 11

Scheme of the implementation of a flip-flop switch with, to right, a zoom on
S. In the zoom, note the crossing x of a leaving track by the deviated route
to S.

The locomotive arrives through a segment of a straight line by $C$ where a
fork sits. Accordingly, two locomotives leave $C$, one of them towards $L$,
the other towards $R$. At $L$ a controller sits and, on the figure, it let the
locomotive go further on the segment of straight line. Note that the path from
$C$ to $L$ is also a segment of a straight line on the figure, which is
conformal to the implementation. Now, the structures which are later involved
make the length of that segment to be huge. At $R$ too a controller is sitting
but, on the figure, it kills the locomotive which is thus prevented to go
outside the switch. On the way from $C$ to $R$ the locomotive meets another
fork at $A$. The fork sends one of the new locomotives to $R$ where it is
stopped in the situation illustrated by the figure and the other is sent to
$S$. There a fork is sitting too which sends two locomotives, one of them to
$L$, the other to $R$. When they reach their goal, the locomotives change the
configuration of the controller which is sitting there. The controller which
let the locomotive go will further stop it while the one which stopped it will
further let it go. Accordingly, after the passage of a locomotive and after a
certain time, the configuration of the flip-flop switch is that we described
in Sub-section 2.1.

We have now to clarify the implementation of the controller. It is illustrated
by Figure 12.

Here, the central cell below $\mathcal{H}$ is not an element of the track. Its
decoration consists of five G -tiles which are placed, for instance on the
faces 6, 7, 8, 9 and 10 of the tile. In order to avoid problems with a
neighbour, those milestones should be placed on the upper crown of the tile.

###### Figure 12

The idle configuration of the controller. To left, upon $\mathcal{H}$, the
track; to right, below $\mathcal{H}$, the controller and its access by a
locomotive.

Figure 11 requires the explanation of the zoom: three tracks abut the point S
which is supposed to behave like a fork. However, the configuration of the
tracks abutting the central tile of a fork is different. It is the reason for
which the track arriving to S from A is deviated near S as indicated in the
zoom so that the new configuration is conformal to that of a fork. Note that
the pieces constituting the deviation of the track are segments of straight
line in Poincaré’s disc model. The price to pay is a crossing at x on the
picture illustrating the zoom.

We are now in position to deal with the memory switch, active and passive
parts.

We first deal with the active part. It looks like the flip-flop switch with
this difference that there is no fork $A$ in between the path from the initial
fork $C$ to $R$, one of the controllers. Figure 13 illustrates both parts of
the memory switch: to left, the active part of the switch, to right, its
passive part.

###### Figure 13

To left, the active memory switch, to right, the passive one.

In the active part of the switch, left-hand side picture of Figure 13, the
locomotive arrives to a fork sitting at $C$. From there two locomotives are
sent, one to $L$, the other to $R$ and the working of the switch at this point
is alike that of a flip-flop switch. The difference lies in the fact that the
passage of the locomotive does not trigger the exchange of the roles between
the controllers. That change is triggered by the passage of a locomotive
through the non-selected track of the passive part of the switch. When it is
the case, a locomotive is sent from the passive part to the active one. That
locomotive arrives at the fork which is sitting at $S$. The fork creates two
locomotives which are sent to $L$ and $R$ in order to change the permissive
controller to a blocking one and to change the blocking one into a permissive
one.

Let us look at the working of the passive part. The locomotive arrives to the
switch through $P$ or through $Q$. Assume as it through $P$. A fork sitting at
$P$ sends a locomotive to the fixed switch $F$ which let the locomotive leave
the switch. The other locomotive sent by $P$ goes to $L$. If that side is that
of the selected track, the controller sitting at $L$ blocks the locomotive so
that no change is performed, neither in the passive switch, nor in the active
one. Accordingly,the selected track of the active switch is controlled by a
permissive controller while the corresponding selected track of the passive
switch is controlled by a blocking controller. Presently, assume that the side
of $L$ is not that of the selected track. It means that $L$ let the locomotive
go to $T$ where a fixed switch sends the locomotive to a fork at $U$. That
fork sends a locomotive to the fork $S$ of the active switch and the other
locomotive is sent to $S$ of the passive switch. At that point $S$ in the
passive switch, a fork sends a locomotive to $L$ and another one to $R$ in
order to change the working of both controllers to the opposite task. As a
parallel change occurs in the active switch the selected track is redefined in
both parts of the switch.

That working raises several remarks. First, the role of the controllers in the
active and in the memory switches are opposite. Nevertheless, in both cases,
the same programmable controller is used exactly because it is programmable in
the way we just described. A second remark is that we used one crossing, two
fixed switches, at $F$ and at $T$ and four forks, at $P$, $Q$, $U$ and $S$.
Each structure requires some space, at least a disc whose radius is the length
of four tiles aligned along a straight line. Consequently, the passive memory
switch requires a huge amount of tiles.

####  2.2.3 The one-bit memory

It is now time to implement the one-bit memory. Figure 14 illustrates the
construction.

We can see the active memory switch at $R$ and the passive one at $E$. The
dark lettres which stand by the blue circle indicate gates of the one-bit
memory: W, R, E, b0 and b1. We can easily see that if the locomotive enters
the unit through the gate R, then it leaves the memory through the gate b0 or
through the gate b1 depending on the information stored in the memory: that
information is provided the unit by the positions of the switch at W and those
at R and E. Note that the positions at R and at E are connected by the path
from E to R, see the figure.

###### Figure 14

The idle configuration of the one-bit memory. Note the four crossings in the
implementation. Note that the connection from E to R is realized by three
segments of straight lines.

When the locomotive enters the memory through the gate W where a flip-flop
switch is sitting, it goes to R through one of both tracks leaving the switch.
If it goes through the track marked by 0, 1, it arrives to E by the track
marked with the opposite symbol, 1, 0 respectively. Indeed, when the
locomotive crosses W, the passing makes the selected track to be changed so,
if it went through one track, after the passage, in particular when the
locomotive arrives at E, the new selected track at W is the track through
which the locomotive did not pass. So that the track marked by one symbol at W
should be marked by the opposite one at E.

As the one-bit memory will be used later, we introduce a simplified notation:
in Figure 14, the memory structure is enclosed in a blue circle. At its
circumference the gates are repeated by the same symbols. In the next figures,
when a one-bit memory will be used, we shall indicate it by a light blue disc
with, at its border, the five gates mentioned in Figure 14.

####  2.2.4 From instructions to registers and back

As will be explained in Sub-subsection 2.2.5, the locomotive arrives at a
register at a point which depends on the type of the operation to be
performed. It depends on the type only, whether it is a decrementation or an
incrementation. It does not depend on namely which instruction of the program
required the execution of that operation. Moreover, the return path of the
locomotive once it performed its operation is the same in most cases.
Accordingly, when the locomotive goes back from the register to the program,
it is important to define the point at which it will return. Correspondingly
with what we said, the unique solution is to keep track of that information
before the locomotive enters the register where that information disappears.

To that goal we define a structure ${\mathbb{D}}_{I}$ for each register as
follows. The structure consists of as many units as there are instructions
incrementing that register, say $R$, in the program. Each unit is based on a
one-bit memory and Figure 15 illustrates such a unit. The working of
${\mathbb{D}}_{I}$ is the following. An instruction for incrementing $R$ is
connected through a path to a specific unit of ${\mathbb{D}}_{I}$. The path
goes from the program to the W-gate of that unit. At the initial time, the
configuration of ${\mathbb{D}}_{I}$ is such that all its unit contain the bit
0: the switches of the one-bit memory are in a position which, by definition
defines bit 0. Accordingly, when the locomotive enters the unit, it will
change the flip-flop and the memory switches so that, by definition, the
memory contains the bit 1. The locomotive leaves the memory through the gate E
and it meets a flip-flop switch at $A$ which, in its initial position, sends
the locomotive to $R$. Note that when the locomotive leaves ${\mathbb{D}}_{I}$
a single unit of the structure contains the bit 1 and selects a path to the
program at its flip-flop switch.

Similarly, a structure ${\mathbb{D}}_{D}$ memorises which instruction required
a decrementation of that register. The structure contains as many unit as
there are instructions of the program which decrements that register. But
instead of containing one bit, each unit contains two of them. Those bits are
either both 0 or both 1. Before the arrival of a locomotive to
${\mathbb{D}}_{D}$, both bits of each unit are set to 0. When the locomotive
enters the structure, it arrives at the unit which corresponds to the
instruction which sent it to that register. The locomotive sets both bits of
the unit to 1. When it leaves ${\mathbb{D}}_{D}$, a single unit contains its
both bits set to 1.

But just before entering the register, the locomotive enters a third
structure, ${\mathbb{D}}_{O}$, which memorises which type of instruction
operates on the register. The structure contains two one-bit memories which
are set to 0 in its initial configuration. If the locomotive comes from
${\mathbb{D}}_{I}$ both bits remain 0. When it comes from ${\mathbb{D}}_{D}$,
both bits are set to 1.

Accordingly, when the locomotive goes back from the register, if the bits of
${\mathbb{D}}_{O}$ are set to 0, it goes back to ${\mathbb{D}}_{I}$. There,
the locomotive goes to the unique unit whose bit is set to 1 and the unit
sends the locomotive back to the program at the right instruction by an
appropriate path. If the bits of ${\mathbb{D}}_{O}$ are set to 1, the arrival
to ${\mathbb{D}}_{O}$ depends on whether the decrementation was possible or
not: there are two arriving paths to ${\mathbb{D}}_{O}$. The locomotive reset
both bits to 0 and it leaves the structure through the appropriate path: that
which corresponds to a successful decrementation or that which corresponds to
the case of a register containing 0.

Let us first consider the case of ${\mathbb{D}}_{I}$. The structure of a unit
is illustrated by Figure 15.

When the locomotive completed the incrementation of $R$ it goes back to the
program. In order to find the appropriate way, it visits the units of the
$D_{I}$ attached to $R$ until it finds the single unit whose one-bit memory is
set to 1. Then, the locomotive rewrites the bit, turning it to 0 and again
exits through the gate E. It meets the flip-flop switch at $A$ which sends the
locomotive on its other path which leads it back to the program. That new
visit of the flip-flop switch at $A$ makes the switch again select the track
leading to $R$. Accordingly, when the locomotive leaves ${\mathbb{D}}_{I}$ the
structure recovers its initial configuration.

###### Figure 15

The idle configuration of a unit of the structure which memorises the right
incrementing instruction. Note the three crossings in the implementation. Also
note that the intensive use of sequences of connected segments of straight
lines.

We can check on Figure 15 that the implementation it gives for a unit entails
a working which is conformal to the above scheme.

When the locomotive comes from an incrementing instruction of the program, it
arrives at the corresponding unit of the right ${\mathbb{D}}_{I}$ through the
gate W of that unit. Accordingly, it changes a bit 0 to 1 and leaves the
memory through E. From there it meets $A$ where the flip-flop switch sends it
to $R$: as the unit contained 0, the switch at $A$ selects the path leading to
$R$. When it leaves $A$, the flip-flop now selects the other path, that which
leads back to the program.

When the locomotive comes back from ${\mathbb{D}}_{O}$, it arrives to the
closest unit of ${\mathbb{D}}_{I}$ through its gate R. If the locomotive reads
0, it leaves the unit through b0 and the corresponding path sends the
locomotive to the next unit. Accordingly, the locomotive crosses the units
containing 0 until it arrives to the R-gate of the single unit containing 1.
As far as it reads 1, the locomotive leaves the memory through b1 on a path
which leads it to W again. Accordingly, the locomotive rewrites the content of
the memory which is thus changed from 1 to 0. The locomotive again leaves the
memory through E and meet $A$ where the flip-flop switch presently sends it to
the program. When leaving $A$, the switch is changed and it again selects the
path leading to $R$, so that that ${\mathbb{D}}_{I}$ recovers its initial
configuration. The scheme allows us to correctly simulate the working of the
units of ${\mathbb{D}}_{I}$.

Presently, we examine the structure ${\mathbb{D}}_{D}$ which plays for the
decrementing instruction the role that ${\mathbb{D}}_{I}$ does for the
incrementing ones. The structure is more complex for the following reason. An
incrementing instruction is always performed which is not necessarily the case
for a decrementing instruction. Indeed, if the register contains the value 0,
it cannot be decremented. We say that the register is empty. In that case, the
next instruction to be performed is not the next one in the program. It is the
reason why the case of an empty register requires a particular treatment.
Concretely, it means that the return track of the locomotive depends on
whether the register was empty or not at the arrival of the locomotive.

###### Figure 16

The idle configuration of a unit of the structure which memorises the right
decrementing instruction. As far as the structure is complex, its components
are displayed in three windows. The yellow small discs close to the border of
a circle indicate points of communication between the windows: the track
arriving to a small disc with an italic small lettre is continued by the track
issued from a small disc with the same italic lettre. Note the sketchy
representation of the one-bit memories.

Accordingly we need two one-bit memories instead of one. More over, as far as
the bit 1 locates the unit of ${\mathbb{D}}_{D}$ which will send the
locomotive to the right place in the program, the content of the memories
should be the same: 0, if the locomotive did not visited that unit at its
arrival to ${\mathbb{D}}_{D}$, 1 if it visited the required unit. As there are
two return tracks after decrementation, the $D$-track is used when the
decrementation could be performed, the $Z$-track is used when the decrementing
locomotive found an empty register. We call D-, Z-memory the one-bit memory
visited by $D$-, $Z$-track respectively. The complication entailed by that
organisation makes a representation of a unit in a single window hardly
readable. It is the reason why it was split into three windows as illustrated
by Figure 16.

To left, we have the D-memory. It is represented by the left-hand side picture
of the figure. A locomotive sent by the program for decrementing a register
$R$ arrives at the appropriate unit of the ${\mathbb{D}}_{D}$ attached to $R$
by the track marked by $D$ in the picture. As far as the locomotive enters the
memory through its W-gate, it rewrites its content from 0 to 1. Now, it has to
mark the Z-memory which is represented on the right-hand side picture of the
figure. To that goal, the track leaving the $D$-memory through its gate E,
goes to the point $c$, that italic lettre marking a small yellow disc close to
the border of the window. The track is continued from a small yellow disc
close to the border of the right-hand side window marked with the same lettre
$c$. Other such discs in the figure are marked by other lettres which are
pairwise the same in two different windows. From that second $c$, the track
leads the locomotive to the gate W of the Z-memory whose content, accordingly,
will be changed from 0 to 1. Leaving the Z-memory through its gate E, the
locomotive is lead to a small disc $d$ so that the corresponding track is
continued by the small disc $d$ we find in the middle window of Figure 16.
From there, the locomotive is lead to a flip-flop switch sitting at $F$ which,
in its initial configuration, selects the track leading to $R$. Now, after the
switch is passed by the locomotive, its selection is changed, indicating the
track leading to another switch sitting at $A$.

Consider the case when the locomotive returns from $R$ after a successful
decrementation. It one by one visits the units of ${\mathbb{D}}_{D}$. It
arrives to the gate R of the D-memory of a unit. If it reads 0, the track
issued from b0 of the D-memory leads the locomotive to the R-gate of the
D-memory of the next unit. So that such a motion is repeated until the
locomotive reads 1 in the unique D-memory whose bit is 1. When it is the case,
the locomotive leaves the memory through its b1-gate which leads the
locomotive to a small disc $a$, so that the track is continued from the small
disc $a$ we can see in the middle picture of Figure 16. From there, the
locomotive arrives to $P$, the passive part of the memory switch whose active
part lies at $A$. The locomotive is sent from $P$ to a small disc $e$ whose
track arriving there is continued by the track issued from the small disc $e$
of the left-hand side picture of the figure. That track leads the locomotive
back to the W-gate of the D-memory. Consequently, the content 1 of the memory
is returned to 0 and leaving the memory through its gate E, the locomotive
again arrives to the W-gate of the Z-memory through the small discs $c$. That
visit rewrites the bit of the Z-memory from 0 to 1. Then, the locomotive
leaves the Z-memory through its E-gate which sends the locomotive to the small
disc $d$ which, through the other such disc in the middle window, again
arrives at $A$. As far as it took much more time for the locomotive to rewrite
both memories of the unit than for another locomotive to go from $P$ to $A$ in
order to set the selection of the active switch, the switch a $A$ indicates
the track corresponding to the branch $P$$a$ of the passive switch. That track
leads to the right decrementing instruction in the program.

Presently, consider the case when the locomotive returns from an empty $R$. It
returned through the Z-track and it arrives to the ${\mathbb{D}}_{D}$ attached
to $R$. There it visits the units of the structure reading the content of its
Z-memory through the track leading to the R-gate of that memory in the unit.
So that the locomotive visits the units until the single one whose Z-memory
contains 1. When it is the case, the locomotive leaves the Z-memory through
its b1-gate which sends it to the W-gate of the D-memory through the small
disc $b$. But the continuation happens by $b$ of the middle picture which
leads the locomotive to $P$. The passive switch sends the locomotive to $e$
and from there to the W-gate of the $D$-memory, $P$ remembering that the
locomotive arrived through the $P$$b$-branch of the switch. Accordingly, what
we seen in a visit through a unit thanks to the $D$-track occurs once again.
Accordingly, the locomotive rewrites the contents of both the D\- and the
Z-memories, returning them from 1 to 0. Then, the locomotive leaves the
Z-memory through its E-gate so that, via the disc $d$, it arrives to $F$ where
the flip-flop switch sitting there sends it to the switch sitting at $A$. Now,
during its trip for the E-gate of the Z-memory to the W-gate of the D-memory,
the locomotive arrived to $P$ through the branch $P$$b$ of that passive
switch. Accordingly, the switch selected that track and, in the meanwhile,
sent another locomotive to $A$ in order to select the appropriate track, that
which leads to $Z$ in the program. As the locomotive passed for a second time
through $F$, the switch selects presently the track leading to $R$, its
initial configuration, up to the configuration at $A$ which can be arbitrary
as shown by our discussion. Accordingly, the scheme illustrated by the picture
performs what is expected.

Presently, we arrive to the structure ${\mathbb{D}}_{O}$ which is illustrated
by Figure 17. As mentioned in the caption, the figure very much looks like
Figure 16. Indeed,the middle picture is almost the same in both figures while
the other pictures are a bit simpler in Figure 17. Indeed, in the middle
picture, the paths leaving $A$ go to different places that in Figure 16.

###### Figure 17

The idle configuration of a unit of the structure which memorises the type of
the current instruction. The structure looks like very much a unit of
${\mathbb{D}}_{D}$ as displayed by Figure 15 although it is a bit simpler.

As indicated by the leftmost picture of Figure 17, when the locomotive comes
from an incrementing instruction via a ${\mathbb{D}}_{I}$-structure, it does
not cross the ${\mathbb{D}}_{O}$-structure which remains with both its memory-
units set to 0. It directly goes to the register via a path which is specific
to incrementing instructions for that register. As the one-bit memories will
be distinguished in what follows, we denote them by D and Z respectively as in
a unit of a ${\mathbb{D}}_{D}$-structure. When the locomotive comes from a
decrementing instruction via a ${\mathbb{D}}_{D}$-structure, it enters the
${\mathbb{D}}_{O}$ of the register through the W-gate of its D-memory.
Accordingly, the bit of that unit is set to 1. The locomotive exits from the
D-memory through the gate E and then, through the small circle $c$, it is sent
to the W-gate of the Z-memory, see the small disc $c$ in the rightmost picture
of Figure 17. Accordingly, the bit of the Z-memory is set to 1. Exiting from
the gate E of the Z-memory, the locomotive is sent via the discs $d$ to that
of the middle picture of the figure. From that $d$-disc, the locomotive is
sent to a flip-flop switch sitting at $F$ which sends the locomotive to the
register, through a path which is specific to the decrementing instructions
for that register. After crossing $F$, the switch sitting there now selects
the track leading to the switch at $A$.

Consider the case when the locomotive returns from the register after
executing an instruction. It is the same track if the instruction could be
completely performed. The track arrives at the gate R of the D-memory. It the
locomotive reads 0, the b0-gate sends it to the program, to the instruction
following the incrementing instruction which was executed. The b0-gate sends
the locomotive to the small disc $f_{1}$, so that it directly goes to the disc
$f_{2}$ from which the track leads to the program. If the locomotive reads 1,
the b1-gate sends the locomotive to a disc $a$ which indicates the
continuation through the disc $a$ of the middle picture of the figure. There,
the locomotive is sent to the passive memory switch sitting at $P$.
Accordingly, that switch orders the switch at $A$ to select the path leading
to the ${\mathbb{D}}_{D}$ of the register. After crossing $P$, the locomotive
arrives at the small disc marked by $e$, so that it continues its way through
the small disc $e$ of the leftmost picture of the figure. Then the enters the
D-memory through its W-gate, so that it rewrites the bit from 1 to 0. Leaving
the memory through E, the locomotive is sent through a small discs $c$ to the
W-gate of the Z-memory whose bit is turned from 1 to 0. The locomotive is sent
through the small discs $d$ to the flip-flop switch at $F$. As the
${\mathbb{D}}_{O}$-structure had its memories set to 1, the switch at $F$
indicates the path to $A$. Now, when the locomotive had set the D-memory back
to 0, it arrived to $P$ through $a$ so that the switch at $A$ indicates the
path to ${\mathbb{D}}_{D}$. As far as the flip-flop switch at $F$ was crossed
a second time, it now indicates the path to the register. Accordingly, when
the locomotive leaves the ${\mathbb{D}}_{O}$ of the register, that structure
recovers its initial configuration up to the switch at $A$ whose selection is
arbitrary.

We remain with the case when a decrementing instruction failed to decrement a
register as far as that one was empty. The return track is not the same as
previously. It is a specific track, the $Z$-path, which also visits the
${\mathbb{D}}_{O}$-structure: that structure has its one-bit memories set to
1, they must be returned to 0. Now, the locomotive arrives through the
$Z$-path at the R-gate of the Z-memory. As far as the decrementing instruction
visited ${\mathbb{D}}_{O}$ before arriving at the empty register, the Z-memory
bit contains 1, so that the locomotive leaves that memory through its b1-gate
which sends the locomotive to the small disc $b$. The continuation happens in
the middle picture where the small disc marked with $b$ sends the locomotive
to $P$ where a passive memory switch sits. As far as the locomotive arrives at
$P$ through the branch $Pb$ of the switch, $P$ makes the active switch sitting
at $A$ select the track leading to ${\mathbb{D}}_{D}$ via the $Z$-path. The
locomotive leaves $P$, going to $e$ where the continuation occurs in the
leftmost picture of the figure. There, the locomotive is sent to the W-gate of
the D-memory whose bit is accordingly turned from 1 to 0. As in the case we
have seen f a successful decrementation, the locomotive via the small discs
$c$ is sent to the W-gate of the Z-memory whose bit too is changed from 1 to
0. At $F$, the flip-flop switch indicates the path to $A$ as far as when it
arrived to ${\mathbb{D}}_{O}$ the bits of the structure were set to 1, so that
the locomotive is sent to ${\mathbb{D}}_{D}$ via the $Z$-path. As far as the
locomotive crossed $F$ the flip-flop switch changes its selection so that it
again selects the path to the register. Accordingly, the locomotive leaves
${\mathbb{D}}_{O}$ in the initial condition of the structure, up to the switch
at $A$ whose selection is arbitrary.

At last and not the least, we have to look at what happens when the locomotive
arrives to the program after performing its operation on the register. Two
cases occur: the new instruction is the next one in the program after the
previous one; the new instruction occurs at another place in the program. In
both cases, the return track leads the locomotive to the appropriate place.

####  2.2.5 Constitution of a register

The implementation of the register requires a special examination. Weak
universality means that the initial configuration is infinite but not
arbitrary. In the present paper, it will be periodic outside a large ball
containing the implementation part of the program and also the first unit of
the two registers needed for universality, according to Minsky’s theorem, see
[13]. Each register, in some sense, follows a line and that construction along
each line is periodic.

A register consists of infinitely many units which we may index by
$\mathbb{N}$. Let $\mathcal{R}$ denote a register. By $\mathcal{R}$($n$), we
denote the $n^{\rm th}$ unit. We shall call $\mathcal{R}$(0) the first unit of
the register. Each unit contains two one-bit memories. Both memories contain
the same bit when the locomotive is away from the register. At each time $t$
of the computation, there is a number $c_{t}$ such that the bits of
$\mathcal{R}$($n$) are both set to 0 when $n\geq c_{t}$ and all of them are
set to 1 when $n<c_{t}$. We say that $c_{t}$ is the value of the register. We
also say that it is its content. When $c_{t}=0$ we also say that the register
is empty. In that case, the bit in all memories of all units of the register
is set to 0.

###### Figure 18

The idle configuration of a unit of a register. We can see the memories
devoted to the materialisation of the content of the register. On the bottom,
the access to the unit, on the top the return path and the auxiliary paths
used for performing a decrementation.

On Figure 18, we display such a unit. In order to make the structure more
visible, we use two windows: one focuses on what we call the I-memory the
other focuses on the D-memory. On the lower part of each window, we can see
two paths delimited by small circles. Those small circles are devoted to allow
the locomotive to go from the left-hand side path to the right-hand side one
when the paths are marked by the same lettre. A similar organisation can be
seen above the one-bit memories but, this time, the locomotive goes from the
right-hand side window to the left-hand side one.

###  2.3 Operations on a register

Presently, we describe how the operations on a register are performed by a
locomotive. Sub-subsection 2.3.1 deals with incrementation while
decrementation is dealt with by Sub-subsection 2.3.2. In both cases of our
discussion, the reader is invited to follow the arguments on Figure 18.

####  2.3.1 Incrementation

When a locomotive arrives from the ${\mathbb{D}}_{O}$-structure of the
register $\mathcal{R}$ at its first unit in order to increment $\mathcal{R}$,
the locomotive is running on the path $I$ of the units which is devoted to
perform the incrementation. The path $I$ leads the locomotive to the R-gate of
the I-memory of the unit. Remember that both units contain the same bit.

If the locomotive reads 1 in the I-memory, it leaves the memory through its
gate b1 so that the locomotive follows the continuation of the path $I$ until
it arrives at the next unit.

Accordingly, the locomotive crosses the units which contain 1 until it reaches
$\mathcal{R}$($n$) for the smallest $n$ such that the unit contains 0.
Consequently we are in the case when, entering the I-memory through its
R-gate, the locomotive reads 0, so that it leaves the memory through its gate
b0. There, a path leads the locomotive to the W-gate of the same memory, so
that the locomotive rewrite its bit from 0 to 1. It exits through the E-gate
of the memory where it is led to a small disc $s$ indicating a continuation
through another $s$ small disc of the right-hand side window. From that second
$s$, the locomotive goes to the W-gate of the D-memory, so that the second bit
of the unit is turned from 0 to 1. Accordingly, when the locomotive leaves the
D-memory through the E-gate, the unit is set to 1 which means that the
incrementation is performed. From the E-gate, the locomotive is led to the
$R$-path which is a return path, leading the locomotive back to the
${\mathbb{D}}_{O}$-structure. From there, the locomotive will reach the
${\mathbb{D}}_{I}$-structure which will send it back to the appropriate place
in the program.

####  2.3.2 Decrementation

Presently, consider the case of a locomotive coming to $\mathcal{R}$ in order
to decrement it. The locomotive arrives at the first unit through the path
$D$.

We first consider the case when the content $c$ of $\mathcal{R}$ is positive.
The locomotive arrives at $\mathcal{R}$$(0)$ through a path $D$ which we can
see on the lower part of the left-hand side part of Figure 18. The path is
continued on the right-hand side part and it leads the locomotive to the
R-gate of the D-memory. As far as $c>0$, the locomotive reads 1. Leaving the
memory through its gate b1, the locomotive is sent back to the $D$-path in
order to go to visit the D-memory of the next unit.

Accordingly,the locomotive arrives at $\mathcal{R}$($c$) whose content is 0 as
well as the content of $\mathcal{R}$($n$) for $n\geq c$. It means that the
locomotive has to go back to $\mathcal{R}$($c$-1) in order to set the content
of that unit to 0. To that goal, the locomotive is sent from b0 to a path wd1
which leads the locomotive to the W-gate of the I-memory of
$\mathcal{R}$($c$-1). So that the locomotive follows the same path as in the
case of an incrementation. Now, remember that entering a one-bit memory
through its W-gate rewrites its bit: if it is 0, it becomes 1, it is 1, it
becomes 0. By assumption the bits in the memories of $\mathcal{R}$($c$$-$1)
are both set to 1 so that entering the W-gate of the I-memory, the locomotive
eventually leaves the D-memory through its E-gate which sends it to the return
path $R$ and both memories of the unit are set to 0. Consequently, in that
case, the locomotive performed the decrementation. The
${\mathbb{D}}_{O}$-structure will send it to the ${\mathbb{D}}_{D}$-one
through the $D$-path so that the locomotive will reach the program at the
appropriate place.

Presently, consider the case when $\mathcal{R}$ is empty. The locomotive still
arrives at the R-gate of the D-memory of the first unit of $\mathcal{R}$. But
reading 0, the locomotive leaves the unit through the b0-gate which sent it to
an auxiliary path, the wd1-one which initiates the $Z$-path going to the
${\mathbb{D}}_{O}$-structure. The locomotive is sent through the $Z$-path to
the ${\mathbb{D}}_{D}$-structure, so that it eventually reaches the
appropriate place of the program.

Figure 18 illustrates the arrival of the locomotive at the W-gate of the
I-memory through another auxiliary path, wd2, which comes from the unit
$\mathcal{R}$($n$+1) assuming that the figure illustrates $\mathcal{R}$$(n)$.
Clearly, the incrementation is performed on the unit where the locomotive
reads 0, the decrementation is performed in the preceding unit which explains
what happens when the register is empty. Accordingly, a successful
decrementation implies that the locomotive goes back through the $R$-path
while an unsuccessful one implies the return through the wd1-path: it is
always possible to fix that one for the units with an even index while wd2
operates for the units whose index is odd.

##  3 The rules

In Sub-section 3.1, we define the format of the rules and we discuss the way
we define the totalisticity. In Sub-section 3.2 we give the rules for the
elements of the tracks, for the control and for the forks.

###  3.1 Format of the rules and totalisticity

A cell of the dodecagrid in the present cellular automaton consists of two
elements: a tile of the tiling, we call it the support of the cell, and a
finite automaton defined by the rules of the present section. Note that the
finite automaton is the same for all cells. The neighbours of a cell $c$ whose
support is $\Delta$ are the cells whose support are the $\Delta_{i}$,
$i\in\\{0..11\\}$, where $\Delta_{i}$ shares the face $i$ of $\Delta$. In that
case, $\Delta_{i}$ is called the $i^{\rm th}$-neighbour of $c$, its
$i$-neighbour for short. The numbering of the faces is the one we described in
Section 1 with the help of Figure 1.

As usual, we call alphabet of our cellular automaton the finite set of its
possible states. In the present case, the alphabet of our cellular automaton
consists of W , B , R and G . We also call W the blank as far as it is the
state of the cells of the dodecagrid except finitely many of them. Let $c$ be
a cell of the dodecagrid whose state is So and whose support is $\Delta$, and
let Si be the state of its $i$-neighbour. Let Sn be the new state of $c$, i.e.
the state taken by $c$ when it is the state associated with So and the Si by
the automaton. We write this as follows:

So.S0S1S2S3S4S5 S6S7S8S9S10S11.Sn $(1)$ and we say that S is a rule of the
automaton. All rules of the automaton we give in the present section obey the
format defined by $(1)$. Of course, So Sn and the Si belong to the alphabet
$\\{$W , B , R , G $\\}$.

Note that if $\sigma$ is a permutation on $\\{0..11\\}$ we call permuted image
of S under $\sigma$ the rule:  So.Sσ(0)Sσ(1)Sσ(2)Sσ(3)Sσ(4)Sσ(5)
Sσ(6)Sσ(7)Sσ(8)Sσ(9)Sσ(10)Sσ(11).Sn which we denote Sσ. Let S be a rule, we
call weight of S denoted by $w$(S) the number
$\displaystyle{\sum\limits_{i=0}^{11}w(\hbox{{\footnotesize\tt S}}_{i})}$
where $w$(Si) is the weight of the considered state i.e. the rank of that
state in $\\{$W ,B ,R ,G $\\}$, the rank of W being 0. Accordingly, in the
line giving a rule we also indicate its weight. As an example, the quiescent
rule will be written as follows:

1  W.WWWWWWWWWWWW.W  0

It is the first rule and its weight is 0.

As a last point, we shall present the rules not only by splitting their set
according to their role in the simulation but also, inside each of such
subsets, according to the role of the rule with respect to the motion itself.
We noted in the previous sections what we called idle configurations. In such
a condition, the configuration must remain unchanged as long as the locomotive
is not in the window which defines the configuration. Such rules are called
conservative. When the locomotive falls within the window, some cells are
changed while the others remain unchanged. Those which are changed are called
motion rules.

###  3.2 The rules for the tracks

We start our study of the rules and the construction of the rules by those
which manage the tracks. As mentioned in Sub-subsection 2.2.1, the motion of
the locomotive is depicted by the scheme (2) we reproduce below for the
convenience of the reader.  3B234234 34R34234 342G4234 3423B234 3423B234
342342R4 (2)  Here, 2, 3 and 4 denote elements of the tracks with 2, 3 and 4
milestones respectively in their decoration. Figure 6 shows us such elements.
The conservative rules induced by those elements are given by Table 1. The
first rules, thirteen of them, deal with the milestones. When the current
state is not W , it means that the locomotive is seen by the milestone. Note
that B is not the state of a milestone.

###### Table 1

Conservative rules for the tracks. When a rule is repeated, for example rule
$6$, its number is also repeated. milestones 1  W.WWWWWWWWWWWW.W  0 2
G.WWWWWWWWWWWW.G  0 3  R.WWWWWWWWWWWW.R  0 4  W.RWWWWWWWWWWW.W  2 5
W.GWWWWWWWWWWW.W  3 6  W.GGWWWWWWWWWW.W  6 7  W.RGWWWWWWWWWW.W  5 8
R.BWWWWWWWWWWW.R  1 9  R.RWWWWWWWWWWW.R  2 10  R.GWWWWWWWWWWW.R  3 11
G.BWWWWWWWWWWW.G  1 12  G.RWWWWWWWWWWW.G  2 13  G.GWWWWWWWWWWW.G  3 elements
of the track 6  W.GGWWWWWWWWWW.W  6 14  W.GGRWWWWWWWWW.W  8 15
W.GGGRWWWWWWWW.W  11 control fork 16  W.GGGGGWWWWWWW.W  15 17
W.GGGGGGWWWWWW.W  18 6  W.GGWWWWWWWWWW.W  6

Note that rule 6 is repeated: it first occurs for a blank tile which can see
two G -milestones when they are put on adjacent faces of an element of the
tracks. In the second occurrence of the rule, it is an element of the track,
namely the element 2 as far as its decoration consists of two milestones. In
the table, rules 2 up to 5 say that a blank neighbour of a milestone remains
blank while a milestone itself whose all neighbours are blank does not change
its state. Rules 6 and 7 deal with a blank tile which can see two milestones:
either two G -ones or a G -one together with an R -one. Rules 8 up to 10 say
that an R -milestone is not affected when it can see a locomotive, whichever
its state. The same role is performed by rules 11 up to 13 for a G -milestone.

###### Table 2

Motion rules for the tracks. the tracks 2 6  W.GGWWWWWWWWWW.W  6 18
W.GGWBWWWWWWWW.R  7 19  R.GGWWWWWWWWWW.W  6 20  W.GGWGWWWWWWWW.W  9 3 14
W.GGRWWWWWWWWW.W  8 21  W.GGRWRWWWWWWW.G  10 22  G.GGRWWWWWWWWW.W  8 23
W.GGRWBWWWWWWW.W  9 4 15  W.GGGRWWWWWWWW.W  11 24  W.GGGRWGWWWWWW.B  14 25
B.GGGRWWWWWWWW.B  11 26  W.GGGRWRWWWWWW.W  13 fork 6  W.GGWWWWWWWWWW.W  6 19
W.GGWBWWWWWWWW.R  7 20  R.GGWWWWWWWWWW.W  6 27  W.GGWGGWWWWWWW.W  12 control
its access 16  W.GGGGGWWWWWWW.W  15 28  R.GGGGGWWWWWWW.R  15 29
W.GGGGGWRWWWWW.R  17 30  R.GGGGGWRWWWWW.W  17 31  W.GGGRWRGWWWWW.W  16 17
W.GGGGGGWWWWWW.W  18 32  W.GGGGGGWBWWWW.R  19 33  R.GGGGGGWWWWWW.W  18 34
R.GGGGGGWRWWWW.W  20 35  G.WGRWWWWWWWWW.G  5 Table 2 gives all the motion
rules involved in the computation. In order to better understand the rules,
the conservative rules of each configuration has been repeated: it can be
recognised by the fact that its number is the same as the one it received in
Table 1. Moreover, in the neighbourhoods of the rules, we first give the
decorations and then, separated from them by a W -symbol, the possible
occurrences of non-blank states. They can be the state of a locomotive, in the
considered element of the track. They can be two non-blank states in the case
of the controller or in the case of the fork.

The reader may notice that the rules for the motion in an element of the track
are parallel in the different cases: rules 6, 14 and 15 are the conservative
rules in an idle configuration. The way the locomotive crosses an element is
given by (4):  element rules entry inside exit 2 18, 19, 20  B R G 3 21, 22,
23  R G B 4 24, 25, 26  G B R (4)  Note that the fork is a 2-element for which
rules 6, 18 and 19 apply. Now, instead of rule 20, rule 27 applies as far as
two locomotives leave the element. It is witnessed by rule 27 which indicates
two G -states outside the states corresponding to its decoration.

The access to the controller is dealt with by rule 17, the conservative rule,
together with rules 32 up to 34. A B -locomotive makes the cell becomes R ,
which allows the controller to change its state: from W to R by rule 29 and
from R to W by rule 30. Note that rule 16 is the conservative rule for a blank
controller while rule 28 conservatively applies when it is R . Rule 31 shows
us that the locomotive when the element is 4, a G -locomotive is stopped by an
R -controller. At last, rule 35 is a conservative rule for a G -milestone of a
controller or of its access cell when an R -locomotive crosses the considered
cell. Indeed, as can be seen on Figure 12, each one of two milestones of the
controller can see a milestone of the access to the controller and, of course,
conversely. So that rule 35 applies both to the controller and to its access
cell.

Note that we fixed the controller to be placed under a 4-element, as shown by
rule 31. The rule says that the locomotive, which is then in the G -state,
cannot enter the element. That requires the arrival to the access cell of the
controller to be the case of a B -locomotive. If it is not provided by the
standard periodic motion along a track, that can be arranged through a path as
indicated in the passive fixed switch or in the fork.

That last point completes the proof of Theorem 1. $\Box$

Figure 19 illustrates the motion of the locomotive on a portion of a path.
Note that the path is rather a simple one: it avoids a single cell of a track
which requires three additional cells. In the figure, the first element of the
appended cells is a 2-one so that the B -locomotive leaving the track became
an R -locomotive when it is again on the track. It is conformal to the
periodic motion on a track. Note that the configuration of the milestones of
the 3-element of the path is different from those of the track: indeed, in
another disposition, we would have milestones of a 3-element which would see a
milestone of a neighbouring 4-element. It is avoided so that the rules apply
without any problem. For a similar reason, in the decoration of the 2-element
of the track at which the path arrives, we place the milestones so that none
of them can see a milestone of a neighbouring element. We place one milestone
on face 11 and the other on a face of the upper crown which points at a blank
neighbour of the cell in $\mathcal{H}$u.

###### Figure 19

The motion of the locomotive on a portion of a path constructed for the
purpose. Note the successive states taken by the locomotive. When the
locomotive is in a cell $c$ we can see its colour on the faces of the
neighbours of $c$ which are adjacent to the face $0$ of $c$. The indices show
us the order of the pictures.

##  4 Conclusion

We have 35 rules for our cellular automaton which is outer totalistic and
weakly universal. There is no rule which is used with the same weight and the
same current state in different neighbourhoods. Several rules occur with the
same weight and with W as the current state: they have different contexts. It
occurs with the weights 9 and 12. The present cellular automaton is not
completely totalistic: rules 5, 9 and 13 have a total weight of 3, taking the
weight of the current state into account and their new state is different.
Another example is given by rules 25 and 27.

Four states seem to be needed for the motion of the locomotive on the tracks,
as already noticed. However, other results with cellular automata on which a
different constraint is put might be obtained. It is an open question. Another
open question is to consider completely totalistic cellular automata. Another
one is to look whether it is possible to construct an outer totalistic
cellular automaton which would also be strongly universal, i.e. whose set of
non-blank cells would always be finite.

And so, there are a lot of open questions.

## References

  * [1] F. Herrmann, M. Margenstern, A universal cellular automaton in the hyperbolic plane, Theoretical Computer Science, 296, (2003), 327-364.
  * [2] M. Margenstern, Cellular Automata in Hyperbolic Spaces, vol. $1$, Theory, Collection: Advances in Unconventional Computing and Cellular Automata, Editor: Andrew Adamatzky, Old City Publishing, Philadelphia, (2007), 422p.
  * [3] M. Margenstern, Cellular Automata in Hyperbolic Spaces, vol. $2$, Implementations and Computations, Collection: Advances in Unconventional Computing and Cellular Automata, Editor: Andrew Adamatzky, Old City Publishing, Philadelphia, (2008), 360p.
  * [4] M. Margenstern, An Upper Bound on the Number of States for a Strongly Universal Hyperbolic Cellular Automaton on the Pentagrid, JAC2010 Turku, Finland, (2010), Proceedings, Turku Center for Computer Science, 168-179.
  * [5] M. Margenstern, A weakly universal cellular automaton in the hyperbolic $3D$space with three states, arXiv:1002.4290v1, (2010), 54pp.
  * [6] M. Margenstern, Small Universal Cellular Automata in Hyperbolic Spaces: A Collection of Jewels, Springer Verlag, (2013), 331p.
  * [7] M. Margenstern, A Weakly Universal Cellular Automaton in the Pentagrid with Five States, Lecture Notes in Computer Science, C.S. Calude et al. (Eds.): Gruska’s Festschrift, 8808, (2014), 99-113.
  * [8] M. Margenstern, A weakly universal cellular automaton in the heptagrid with three states, arXiv:1410.1864v1, (2014), 27p.
  * [9] M. Margenstern, A Weakly Universal Cellular Automaton in the Heptagrid of the Hyperbolic Plane, Complex Systems, 27(4), (2018), 315-354.
  * [10] M. Margenstern, A Strongly Universal Cellular Automaton on the Heptagrid with Seven States, Journal of Cellular Automata, to appear.
  * [11] M. Margenstern, A strongly universal cellular automaton in with four states, arXiv:2107.04843v1, (2010), 54pp.
  * [12] M. Margenstern, Y. Song, A new universal cellular automaton on the pentagrid, Parallel Processing Letters, 19(2), (2009), 227-246.
  * [13] M. L. Minsky, Computation: Finite and Infinite Machines, Prentice Hall, Englewood Cliffs, NJ, 1967.
  * [14] I. Stewart, A Subway Named Turing, Mathematical Recreations in Scientific American, (1994), 90-92.