A strongly universal cellular automaton in the dodecagrid with five states

We mentioned the key role played by the tracks in the computation. Without them, the locomotive could not perform any operation on the registers. Without them 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 explain 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. We just mentioned that the presentation of the present paper significantly simplifies what is written in [10].

The tracks are one-way. It is useful to reduce the number of states but it raises a problem as far as a two-way circulation is required in some portions of the circuit. It is a point where the third dimension 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 over $\mathcal{H}$ while the reverse running will be performed below $\mathcal{H}$. Occasionally and locally, we shall use a plane $\mathcal{V}$ which is orthogonal to $\mathcal{H}$. Note that if $\mathcal{H}$ is fixed in all the paper, $\mathcal{V}$ may change according to the context where it is mentioned.

The present organisation of the one-way tracks is very different from that of [9]. Contrarily to that paper, we go back to mark the elements of a path by milestones. The milestones are blue, in contrast with the blank colour of most of the cells: all of them outside a large enough disk containing the initial configuration. The blank is the quiescent state of our cellular automaton: if a cell is blank and if all its neighbours are blank too, the cell remains blank. We say tracks for portions of a path which follow a line $\ell$ defined by a side of the tiles in $\mathcal{H}$. Combining several tracks gives rise to paths. On the path, a blue locomotive is running which consists of a single blue cell which moves in between blue milestones. Figure 12 illustrates the constitution of the tracks. On the figure, the lines are followed by the side 1 of the elements of tracks.

The leftmost picture of the figure shows us that an element of a track consists of a white dodecahedron $\Delta$ whose face 0 lie on $\mathcal{H}$ and on the faces 6, 9 and 10 of $\Delta$ we have three dodecahedrons $\Delta_{6}$, $\Delta_{9}$ and $\Delta_{10}$ which are blue. Those dodecahedrons close to the face opposite to face 11, opposite to face 0, are called the decoration of $\Delta$. In general, the locomotive enters an element of the track through its face 5 or 4 and it leaves the element through its face 2. In order to allow variations which we further describe, for instance in Figure 13, the locomotive may also enter through face 1, the exit face being always face 2.

The middle picture of Figure 12 shows us two tracks which lie on $\mathcal{H}$. As clearly seen, the left-hand side track follows a line of $\mathcal{H}$, in mauve in the pictures, which contains an edge of the face 1 of all the elements constituting that track. A similar remark can be formulated for the right-hand side track. According to the convention we indicated on the way a locomotive may cross an element of a track, the left-hand side track is going down while the right-hand side one is going up. The rightmost picture of the figure shows us tracks which are below $\mathcal{H}$, their face 0 also belonging to $\mathcal{H}$. Imagine that the tracks of the middle picture are removed and that we see those tracks below $\mathcal{H}$ from above $\mathcal{H}$ as if that plane were translucent. We can see that the image we need is an image of $\Delta$ under a symmetry in the plane orthogonal to $\mathcal{H}$ which contains the opposite edges 1.5 and 8.9 of $\Delta$. The numbering of the faces is thus increasing while counter-clockwise turning around face 0 while the numbering is clockwise on Figure 1. Note that below $\mathcal{H}$, the direction of the tracks is opposite to that of the tracks upon $\mathcal{H}$ which follow the same lines. It is an important feature which allows us to define a two-way path: one direction is performed upon $\mathcal{H}$ while the opposite one occurs below $\mathcal{H}$.

Moreover, in most parts of the circuit we shall describe a single locomotive is running on the circuit. In particular, in the case when a two-way track occurs in some part of the circuit, there can never be a locomotive in a track $\tau$ over $\mathcal{H}$ and another one, at the same time, in the track below $\tau$.

Figure 13 illustrates how pieces of tracks indicated in Figure 12 can be organised into paths. As long as it will be possible, paths for the locomotive will follow a straight line of the tiling which is the trace of the dodecagrid on $\mathcal{H}$. However, as the locomotive goes from the program to the register and back, such a circuit is organised along a kind of quadrangle $Q$ in the hyperbolic plane as illustrated by the top picture of Figure 13.

On that picture, we can see two paths for drawing the bottom side of $Q$. The red one is a segment of a straight line in the hyperbolic plane. The blue one is an arc of a hyperbolic circle. On the model, the arc is longer than the segment. In fact, the arc is much longer: its length is proportional to an exponential function of the radius of the circle supporting the arc. The bottom pictures of the figure show us a zoom on two corners of the quadrangle: the left-hand side picture illustrates the right-hand side bottom corner. By rotating those pictures we can see how to connect the sides of $Q$. Note that the right-hand side picture connects a segment of a straight line with an arc of a circle. The elements with an entry through side 1 play an important role in the realisation of an arc of circle and on the connection between segments of different directions.

We can see that those constructions are flexible enough, so that we have a relative freedom in the construction of the circuit.

The section follows the implementation described in [10, 11]. We reproduce it here for the reader’s convenience. The illustration 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 and we can see the tiles on $\mathcal{H}$ within a circle of radius 3 from the central tile, what we call the window. An idle configuration is a configuration where there is no locomotive within the just defined window. The left-hand side of Figure 14 shows us such an idle configuration for the passive fixed switch. From what we said in Section 3.2, we know that there is no active fixed switch, so that illustration of such a switch concerns the passive one only.

We can see that the central tile is an ordinary element of the track. As a locomotive may enter through its face 5 or through its face 4, the constitution of the switch is easy: one branch of the switch arrives at face 5 in the central tile while the other branch arrives through face 4. We have a single locomotive in the window focused on the centre of the fixed switch.

Two important structures are required for implementing the remaining swit-ches : the fork and the controller. We start with the fork and we examine the case of the controller after the implementation of the flip-flop switch.

The right-hand side picture of Figure 14 illustrates the implementation of the fork in its idle configuration. That structure receives one locomotive and it yields two ones which leave the structure in opposite directions. As can be seen on the figure, the central cell differs from an element of the track: its decoration consists of five dodecahedrons which are placed on faces 6, 7, 8, 9 and 11. Moreover, the locomotive enters the tile through its face 2 and the two new locomotives exit through faces 4 and 5.

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

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, through another face of the controller, 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 3.1. We may arrange the circuit so that a new passage of the locomotive at that switch will happen a long time after the change of function of its controllers is completely changed.

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

Here again, the central cell below $\mathcal{H}$ is not an element of the track. Its decoration consists of four blue dodecahedrons which are placed on the faces 6, 9, 10 and 11 of the tile.

Figure 15 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.

The crossing happens to be a burden in the hyperbolic plane requiring several complex structures we do not need in the hyperbolic $3D$-space. The third dimension offers two possible ways to easily realize a crossing: the bridge or the tunnel. In the present paper, I have chosen the tunnel, illustrated by Figure 17. Two tracks follow a line: a red one going from right to left on the three pictures and a blue line, from bottom to top on the left-hand side picture only.

The leftmost picture of the figure is the standard projection upon $\mathcal{H}$, where each dodecahedron is projected within the face it shares with $\mathcal{H}$. In the picture, the faces of the elements of the track which lie on $\mathcal{H}$ are faces 0. Using the numbering of the tiles of $\mathcal{H}$, the elements of the track following the blue line, going from bottom to top on the picture are, in this order : sector 3, tiles 21, 8, 3 and 1; the central tile, then, in sector 1, tiles 1, 4, 12 and 33. Six other tiles can be seen : in sector 2, tiles 3, 8 and 20 and, in sector 5, 33, 12 and 4 as the track goes from right to left, following the red line $\ell$. Three tiles are missing for that track: tile 1 of sector 5, the central tile and tile 1 of sector 2. Those tiles are not upon $\mathcal{H}$ but below that plane. They are illustrated by the middle picture where $\ell$ is again represented. It is the part of the crossing track which passes under the track illustrated by the leftmost picture. In the middle picture we can see those elements of track as if $\mathcal{H}$ were translucent. Two additional tiles are indicated in the middle picture: tile 4 of sector 5 and tile 3 of sector 2. Those tiles correspond to the tiles with the same numbers in the same sectors which lie upon $\mathcal{H}$. Each of those tiles upon and below $\mathcal{H}$ allows a locomotive going upon $\mathcal{H}$ to go below that plane in order to cross the other track. Those elements require the locomotive to enter through a face 1 and to exit through a face 2.

The rightmost picture of Figure 17 shows us the projection of the tunnel on the plane $\mathcal{V}$ which is orthogonal to $\mathcal{H}$, cutting that latter plane along the line $\ell$. We represent on $\mathcal{V}$ the tiles which have a face on it only. Those which are on the same side of $\mathcal{V}$ as the central tile in the middle picture are seen in direct projections. Those which are on the other side are seen as if $\mathcal{V}$ were translucent.

Figure 18 illustrates the possible projections of an element of the track depending on whether it is seen upon $\mathcal{H}$, upon $\mathcal{V}$ or through those planes by transparency, also depending on which face is on $\mathcal{H}$ and which one on $\mathcal{V}$.

Consider the central tile of the leftmost picture of Figure 17. It is projected on its face 0 on $\mathcal{H}$ and the locomotive goes upward, entering through face 5 and leaving through face 2. Consider the entrance into the tunnel. We can see that the entry of the locomotive through face 1 and its leaving through face 2 cannot be used on both ends of the tunnel: the reason is that, at the entry, the neighbour 6 of the tile below $\mathcal{H}$ would be below face 0 of the tile of the track arriving to the entry over $\mathcal{H}$: that would stop the locomotive. That problem does not occur for the exit, so that we can use that way of working for the exit. For the entry, we need to change the tile in order to induce rules which would be rotationally compatible with the others and this time the entry into the tile below $\mathcal{H}$ is through face 7 and the exit still through face 2. That tile differs from a tile of the track by the occurrence of red neighbour on its face 3.

Figure 18 gives various views on the tiles we just mentioned. The first row of the picture indicates the projections over $\mathcal{H}$ of tiles of the track depending on the face which lies on  $\mathcal{H}$: face 0, face 1, face 2 and face 7 for the pictures 1, 2, 3 and 4 respectively on the first row of the figure. Picture 5 is the projection of the tile of the entry below $\mathcal{H}$, projected above $\mathcal{H}$ on its face 7. The second row of the figure, pictures 6 up to 10 gives the same tiles viewed through a translucent $\mathcal{H}$. Picture 11, third row of the figure, illustrates an element of the tunnel below $\mathcal{H}$ seen through a translucent $\mathcal{H}$. The fourth row illustrates the tiles for the entry into the tunnel: picture 12 for the tile above $\mathcal{H}$ and pictures 13 and 14 for the entry below $\mathcal{H}$ when it is projected on $\mathcal{V}$, picture 13, on its face 8, and when it is viewed through a translucent $\mathcal{H}$, picture 14, through its face 7. The last row of the figure illustrates the tiles for the exit from the tunnel. Pictures 15 and 16 illustrate the exit tile below $\mathcal{H}$: viewed through a translucent face 2 being on $\mathcal{H}$, while picture 16 shows us the projection on its face 0 over $\mathcal{V}$.

To conclude with the tunnel, the occurrence of a locomotive in the central tile of the tunnel will not stop a locomotive on the upper way: first, the locomotive never stops on an element of the track and, more over, in such a crossing there is a single locomotive in a window around the central point of the crossing: if it is present on one path, it cannot be present on the other one. We are now in position to deal with the memory switch, active and passive parts.

First, we 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 19 illustrates both parts of the memory switch: to left of the figure, the active part of the switch, to right, its passive part.

In the active part of the switch, left-hand side picture of Figure 19, 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 is 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$, 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. The second remark is that all the tracks indicated in the pictures are pieces of straight lines of the hyperbolic plane. A last 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. Again, we may assume that a new passage of the locomotive to the switch happens after the changes has been performed when it is the case they should occur.

It is now time to implement the one-bit memory. Figure 20 illustrates the construction for the implementation of Figure 10 in the dodecagrid.

We can see the active memory switch at $R$ and the passive one at $E$. The dark letters 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.

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. The selection observed at E is transferred to R thanks to the path connecting E to R.

As the one-bit memory will be used later, we introduce a simplified notation: in Figure 20, 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 disc with, at its border, the five gates mentioned in Figure 20.

As will be explained in Sub-subsection 3.2.5, the locomotive arrives at a register at the same element, but not through the same face: face 5 is devoted to the locomotive coming from an incrementing instruction, face 4 is devoted to the case when the locomotive comes from a decrementing instruction. As will be seen later, the blue locomotive coming to decrement the register is changed into a red one just before arriving at the register. That difference will be justified when we study the operations on a register, in Section 3.2.5. After it performed its operation, the locomotive goes back through a particular track corresponding to the operation it performed. But, as far as all incrementations on a given register make the locomotive arrive at the same point of the register, the return to the appropriate instruction of the program requires that the instruction yielding the operation should be memorised in some way.

To that goal we define two structures ${\mathbb{D}}_{I}$ and ${\mathbb{D}}_{D}$ for incrementing and decrementing instructions respectively. Each structure consists of as many units as there are instructions of the corresponding type operating on the same register. Accordingly, each register is dotted with specific ${\mathbb{D}}_{I}$ and ${\mathbb{D}}_{D}$. We can imagine that the small orange and blue boxes of Figure 11 contain, each one, a copy of ${\mathbb{D}}_{I}$ and a copy of ${\mathbb{D}}_{D}$.

First, we consider the case of ${\mathbb{D}}_{I}$. Each unit is based on a one-bit memory which is illustrated by Figure 21. 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 gate W 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$.

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 ${\mathbb{D}}_{I}$ attached to $R$ until it finds the unit whose one-bit memory is set to 1. Indeed, at ${\mathbb{D}}_{I}$, the locomotive enters the memory of the first unit through its  R-gate. If it reads 0, it leaves the memory through b0 and the path sends it to the next unit. So that we are led to the situation when entering through R, the locomotive reads 1. Accordingly it leaves the unit through b1 which leads it to W. Consequently, the locomotive rewrites the bit, turning it to 0 and again exits through the gate E. It again meets the flip-flop switch at $A$ which sends the locomotive on its other path leading the locomotive back to the program. That new visit of the flip-flop switch at $A$ make the switch again select the track leading to $R$. Accordingly, when the locomotive leaves ${\mathbb{D}}_{I}$ the structure recovered its initial configuration. Accordingly, that scheme allows us to correctly simulate the working of the units of ${\mathbb{D}}_{I}$.

Secondly, we examine the structure of ${\mathbb{D}}_{D}$ which plays for the decrementing instruction the role which ${\mathbb{D}}_{I}$ plays 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 to be differently dealt with. 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.

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. There are two return tracks after decrementation: the $D$-track when the decrementation could be performed, the $Z$-track 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 make 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 22.

The $D$-memory 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 gate W, 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 letter 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 letter $c$. Other such discs in the figure are marked by other letters 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 22. 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 $D$-memory. When it is the case, the locomotive leaves the memory through its gate b1 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 22. 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$. Again the E-gate of the $Z$-memory 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 at $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 and after that passage of the locomotive, the switch at $F$, indicates the path to $R$: the structure recovered its initial configuration.

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 gate b1 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. 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. Accordingly, the scheme illustrated by the picture performs what is expected.

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. Whatever the track arriving to the program, it leads to the appropriate instruction: the next one in the program if the just operated one was an incrementation or a successful decrementation, a specified one if the decrementation was unsuccessful. We have to remember, when we shall discuss the rules that when it leaves a register, whatever the return path, the locomotive must be blue.

The implementation of the register requires a special examination. As the computation is supposed to start from a finite configuration, at initial time, each register has only finitely many non blank tiles. So that incrementation and decrementation necessarily change the length of the register which is always finite.

Our choice is to make the register grow as long as the computation is not completed. The operations of incrementing and decrementing can be implemented by a change of colour at the beginning end of the register: its content is the number of cells of that particular colour. The continuation of the register is made at speed $\displaystyle{1\over 2}$ for a reason we soon indicate. It happens independently of the operations performed on the register. As far as the length of the track from the register and back is enormous, the other end of the register is farther and farther from its beginning end. So, to stop the register when the stopping instruction is reached, the program sends a locomotive to all registers. Each locomotive crosses its register at speed 1. That condition guarantees that the stopping signal will eventually reach the growing end of the register so that it can stop the continuation.

The register consists of four sequences of tiles following a line $\ell$ on $\mathcal{H}$. We say that such a sequence is a strand of the register. Two strands are upon $\mathcal{H}$ and the two others are below $\mathcal{H}$. One strand over $\mathcal{H}$ contains the content of the register, we denote it by R_c. That strand is blue, denoted B and the content is blank which we denote by W. The strand below R_c is red, denote by R, and it is the return path for an incrementing instruction. We denote it by R_i. The other strand over $\mathcal{H}$ is yellow, denoted by Y and it is the return path for a decrementing instruction. We denote it by R_d. The fourth strand, hence below $\mathcal{H}$, is blue and is the path for the stopping signal. We denote it by R_s. The growing end consists of the last tiles of each sequence, those tiles being green, denoted by G. We shall see more precisely how it is performed when we shall study the rules for implementing the simulation. In order to facilitate our explanations, if $\mathcal{S}$ is one of the four strands we depicted, $\mathcal{S}$(0) denotes its first cell, more generally, $\mathcal{S}$$(i)$, with $i\in{\mathbb{N}}^{+}$, denotes the $i^{\rm th}$ element on the strand. As we also need to define the cell which has a side on $\ell$ and which is continued by $\mathcal{S}$, we denote that cell by $\mathcal{S}$(-1). We define a numbering for the tiles of $\mathcal{S}$ as illustrated by Figure 8 and as explained in our discussion about the neighbours of a tile. The motion of a locomotive from a face 5 to a face 2 allows us to see that on two strands, R_c and R_s, the motion goes on $\mathcal{S}$($n$) by following increasing values of $n$ while of the two other ones, R_i and R_d, it goes by following decreasing values of $n$.

Before looking at each strand separately, we have to look at the implementation we give to the strands.

Here is an example of the constraint raised by the rotation invariance. Consider the following rules: $(a)$ W.RYWWR WWWWWW.R and $(b)$ W.RRYWW WWWWWW.W . For both of them, the neighbourhood has the reduced form: $(r)$ WWWWWWWWWRRY. It can be checked on Figure 6 that the rotation around the axis through the midpoint of 4.5 and 7.8 transforms $(a)$ onto $(r)$ while a rotation around faces 4 and 7 transforms $(b)$ onto $(r)$. Rule $(a)$ is necessary for the motion of a red locomotive on a strand according to the definition given to that strand of a register in [10]. But rule $(b)$ is needed according to Proposition 2. Accordingly the definition of our strands have to be seriously tuned.

We use the notations introduced in Sub-subsection 3.2.5. Let us remind the reader that the four strands of a register are R_c, R_i, R_d and R_s. Two of them, R_c and R_d are over $\mathcal{H}$ while the two others, R_i and R_s are below that plane. Each $\mathcal{S}$($n$) has its face 0 on $\mathcal{H}$ and for each of them, its face 1 has a side on a line $\ell$ of $\mathcal{H}$ attached to that register. That fixes the numbering as already mentioned. Note that for strands over $\mathcal{H}$ the numbering is increasing while clockwise turning around the projection of the cell. For the strands seen through a translucent $\mathcal{H}$ the numbering is counterclockwise increasing.

A cell has at least four important neighbours : a cell of the same coordinate belonging to another strand seen from its faces 0 and 1 and two cells of the same strand seen from its faces 5 and 2. We append two decorations to each $\mathcal{S}$($n$) : a blue cell on its faces 4 and 6 for R_i and R_d, on its faces 3 and 7 on R_c and R_s.

The main reason for those decorations is to ensure the rotation invariance of the rules. Let us now explain why namely those faces are involved. In order to understand that it is necessary to describe how the register is growing. We decided that R_c is B, at least, close to the growing end, that R_s also is B while R_i is R and R_d is Y. Let $N_{t}$ be the coordinate such that, at time $t$, $\mathcal{S}$$(n)$ is W if $n>N_{t}$ and that it is the colour of its strand if $n<N_{t}$. For $n=N_{t}$, we decide that $\mathcal{S}$$(n)$ is G. We also decide that, at time $2t$, each neighbour of $\mathcal{S}$$(n)$ which has a single non-blank neighbour becomes B while $\mathcal{S}$$(n)$ remains G. To decide what to do at time $2t$+1, it is necessary to closer look at the situation. Two figures help us to see the configuration of the end of the register: Figures 23 and 24.

The former figure is a cut along a plane $\mathcal{V}$ which is perpendicular to $\ell$ and which contains a face of each $\mathcal{S}$$(n)$ for some $n$. On the right-hand side of the figure, we have the representation on $\mathcal{H}$ while, on the left-hand side, we have the projections of the tiles we can see. Remember the condition we have given for a neighbour $S_{i}$ of $\mathcal{S}$$(n)$: $S_{i}$ must have eleven white neighbours while its single non-blank neighbour is $\mathcal{S}$$(n)$ itself whose colour is G. Which faces of $\mathcal{S}$$(n)$ satisfy such a condition?

The figure indicates that on all cells, a priori, we have all faces except faces 0, and 1, and also face 2 for R_c and R_s and face 5 for R_i and R_d. But, we have to take into account the fact that $S_{7}$ and $S_{8}$ of each $\mathcal{S}$($n$) can see $S_{6}$ and $S_{10}$ respectively on $\mathcal{S}$$(n$$-$$1)$ for R_i and R_d, on $\mathcal{S}$$(n$+$1)$ for R_c and R_s. Moreover, $S_{3}$ of each $\mathcal{S}$($n$) can see $S_{4}$ on $\mathcal{S}$($n$$-$1) for R_i and R_d or on $\mathcal{S}$($n$+1) for R_c and R_s. Now, on R_c and R_s, $S_{7}$ of $\mathcal{S}$($n$) can see $S_{6}$ of R_d and R_i respectively for the same coordinate. If we wish to obtain G on $\mathcal{S}$($N_{t}$+1), we must take advantage of the fact that the $S_{2}$ of R_c and R_s can see the $S_{5}$ of both R_i and R_d, similarly for the $S_{5}$ of R_i and R_d with the $S_{2}$ of both R_c and R_s. Accordingly, each of those $S_{i}$’s have two B-neighbours and they all can see a G-cell. We can then decide that in such a case the B-cell becomes G and that the former G-cell takes the colour of its strand. We remain with what to do with the other B-neighbours of the G-$\mathcal{S}$$(N_{t})$. From what we just remarked, $S_{6}$ or $S_{7}$, and also $S_{3}$ or $S_{4}$, it depends on which strand the cell is, is blue and can see another blue neighbour. We can decide that such a B-cell remains B.

If we do that, what can be said? In that case, we can see that on R_c or R_s, an $S_{6}$ neighbour of the G-cell which is white remains white as far as it can see the G-cell and a B-decoration on $\mathcal{S}$($N_{t}$$-$1). Accordingly, that cell remains white. We have the same argument with $S_{4}$ for the same cell. A similar argument holds for $S_{7}$ and $S_{3}$ on the G-cell of R_i and of R_d. Accordingly, at time $2t$+1 we can decide that the B-cells which can see their G-neighbour as their unique non-blank neighbour become white. Accordingly, the new cell of the strand receives the same decoration as its neighbour $\mathcal{S}$($N_{t}$$-$1) on the strand. All other neighbours are white outside its neighbours 0, 1, 2, 5 and outside the decorations, neighbours 3 and 7 on R_c and on R_s, neighbours 4 and 6 on R_i and on R_d.

Those conclusions hold for $\mathcal{S}$($n$) with $n>0$. For $n=0$ it is important that the cell knows that it is the first one of the strand. As the cell cannot see the decoration of its neighbours, that information of being the first cell must be given in the decoration. For R_c, it receives one additional blue cell on face 9. A single blue cell on face 9 is also given to R_i. However, R_d receives two additional red cells on faces 9 and 11. Eventually, R_s is fitted with a single blue cell on face 9.

We gather that information on the neighbours of $\mathcal{S}$($n$) as follows: $\mathcal{S}$($n$), $n>0$: R_c : 0: R, 1: Y, 2:B^∗, 3:B, 5:B^∗, 7: B, others: W; R_i : 0: B^∗, 1: B, 2:R, 4:B, 5:R, 6: B, others: W; R_d : 0: B, 1: B^∗, 2:Y, 4:B, 5:Y, 6: B, others: W; R_s : 0: Y, 1: R, 2:B, 3:B, 5:B, 7: B, others: W; $\mathcal{S}$(0): R_c : 0: R, 1: Y, 2:B^∗, 3:B, 5:W, 7: B, 9: B, others: W; R_i : 0: B^∗, 1: B, 2:W, 4:B, 5:R, 6: B, 9: B, others: W; R_d : 0: B, 1: B^∗, 2:Y, 4:B, 5:Y, 6: B, 9: R, 11: R, others: W; R_s : 0: Y, 1: R, 2:B, 3:B, 5:B, 7: B, 9: B, others: W; (7)    Note that in (7), the asterisk indicates that B may be replaced by W: remember that on R_c, the value $v$ stored in the register is indicated by $v$ contiguous blank cells starting from R_c(0) which, consequently, is B when $v=0$. That possibility also concerns R_i and R_d which can see R_c through their face 0 and 1 respectively. It does not concern R_s which cannot see R_c.

Figure 24 illustrates the configuration of the end of the register when the G-cells are covered by B-neighbours. We can see the faces which are covered with a blank cell. The left-hand side part of the figure illustrates R_c and R_d, the strands above $\mathcal{H}$. The right-hand side part of the figure illustrates R_i and R_s which hang below $\mathcal{H}$ and which are viewed through a translucent $\mathcal{H}$. The figure applies the convention for colouring the faces of the dodecahedrons we already defined. It can be seen that the cells of R_c and of R_s are blue, while those of R_i are red and those of R_d are yellow.

The orientations for the motion of a locomotive on a strand are from face 5 to face 2 on all strands. In both R_c and R_s it means a motion from $\mathcal{S}$(0) to the G-cell of $\mathcal{S}$, while it is the opposite direction on both R_d and R_i. Those orientations are conformal to the role of the strands: on R_c the locomotive looks after the lowest $c$ such that R_c($c$) is blue, on R_s it looks after the G-cell; on R_i and R_d, the locomotive looks after $\mathcal{S}$(-1). The cells $\mathcal{S}$(-1) can be seen on Figure 25.

Note the specific decorations of the cells $\mathcal{S}$(-1). We summarize what is illustrated by Figure 25 as follow, following the conventions of (7):

$\mathcal{S}$(-1): R_c : 2, B^∗, 6, 9, 10: Y, others: W; R_i : 5: R, 6,9: R, 10: Y, others: W; R_d : 2: Y, 6,9: Y, 10:R, others: W; R_s : 5: B, 6: B, 7: R, 9, 10: B, others: W; R_c(-2): $a$ : 6, 9, 10: B, others: W; $b$ : 6: R, 7: B, 9, 10: R, others: W; $c$ : 6, 7, 11: Y, 9: B, others: W; (8)    We indicated three cells R_c(-2), denoted by $a$, by $b$ and by $c$. The reason is that three paths abut R_c(-1): the first path ending with R_c(-2)_a leads a locomotive from the ${\mathbb{D}}_{I}$ attached to the register. The second path ending with R_c(-2)_b leads the locomotive from the ${\mathbb{D}}_{D}$ attached to the register. The third path, starting from R_c(-2)_c, leads the locomotive from the register to the ${\mathbb{D}}_{D}$ of that register when the locomotive failed to perform the decrementation.

It is now time to look at the rules. We start with the conservative rules which allow the structure to remain unchanged as long as the locomotive is not present. We also append the motion rules for coming locomotives on R_c and R_s, for leaving ones on R_i and R_d.

Table 4