Jérôme Durand-Lose
email: durand-lose@univ-orleans.fr

Reversible conservative rational abstract geometrical computation is Turing-universal

Keywords: Abstract geometrical computation, Conservativeness, Rational numbers, Reversibility, Turing-computability, 2-counter automata

In Abstract geometrical computation for black hole computation (MCU '04, LNCS 3354), the author provides a setting based on rational numbers, abstract geometrical computation, with super-Turing capability. In the present paper, we prove the Turing computing capability of reversible conservative abstract geometrical computation. Reversibility allows backtracking as well as saving energy; it corresponds here to the local reversibility of collisions. Conservativeness corresponds to the preservation of another energy measure ensuring that the number of signals remains bounded. We first consider 2-counter automata enhanced with a stack to keep track of the computation. Then we built a simulation by reversible conservative rational signal machines.

Introduction

Reversible computing is a very important issue because it allows on the one hand to backtrack a phenomenon to its source and on the other hand to save energy. Let us note that quantum computing relies on reversible operations. There are general studies on reversible computation [START_REF] Li | Reversible simulation of irreversible computation[END_REF] as well as many model dependent results: on Turing machines [START_REF] Lecerf | Machines de Turing réversibles. Récursive insolubilité en n ∈ N de l'équation u = θ n u, où θ est un isomorphisme de codes[END_REF][START_REF] Bennett | Logical reversibility of computation[END_REF][START_REF] Bennett | Notes on the history of reversible computation[END_REF] and 2-counter machines [START_REF] Morita | Universality of a reversible two-counter machine[END_REF] (we do not use these), on logic gates [START_REF] Fredkin | Conservative logic[END_REF][START_REF] Toffoli | Reversible computing[END_REF], and last but not least, on reversible Cellular automata on both finite configurations [START_REF] Morita | Computation-universality of one-dimensional one-way reversible cellular automata[END_REF][START_REF] Morita | Reversible simulation of one-dimensional irreversible cellular automata[END_REF][START_REF] Dubacq | How to simulate Turing machines by invertible 1d cellular automata[END_REF] and infinite ones [DL95,DL97,DL02,Kar96,Tof77] as well as decidability results [START_REF] Čulik | On invertible cellular automata[END_REF][START_REF] Kari | Reversibility of 2D cellular automata is undecidable[END_REF][START_REF] Kari | Reversibility and surjectivity problems of cellular automata[END_REF] and a survey [START_REF] Toffoli | Invertible cellular automata: a review[END_REF].

Abstract geometrical computation (AGC) [START_REF] Durand-Lose | Abstract geometrical computation for black hole computation (extended abstract)[END_REF][START_REF] Durand-Lose | Abstract geometrical computation: Turing-computing ability and undecidability[END_REF] comes from the common use in the literature on cellular automata (CA) of Euclidean lines to model discrete lines in space-time diagrams of CA (i.e. colorings of Z × N with states as on the left of Fig. 1) to access dynamics or to design. The main characteristics of CA, as well as abstract geometrical computation, are: parallelism, synchrony, uniformity and locality of updating. Discrete lines are often observed and idealized as on Fig. 1. They can be the keys to understanding the dynamics like in [START_REF] Ilachinski | Cellular automata -a discrete universe[END_REF] or [START_REF] Boccara | Particle-like structures and interactions in spatio-temporal patterns generated by one-dimensional deterministic cellular automaton rules[END_REF][START_REF] Jakubowsky | Computing with solitons: a review and prospectus[END_REF]. They can also be the tool to design CA for precise purposes like Turing machine simulation [START_REF] Lindgren | Universal computation in simple onedimensional cellular automata[END_REF]. These discrete line systems have also been studied on their own [START_REF] Mazoyer | Signals in one-dimensional cellular automata[END_REF][START_REF] Delorme | Signals on cellular automata[END_REF]. Zeno like acceleration and accumulation can be brought out as on Fig. 2 of Sect. 2. Accumulations can lead to an unbounded burst of signals producing infinitely many signals in finite time (as in the right of Fig. 2). To avoid this, a conservativeness condition is imposed: a positive energy is defined for every meta-signal, the sum of the energies must be preserved by each rule. Thus no energy creation is possible; the number of signals is bounded.

To our knowledge, AGC is the only computing model that is a dynamical system with continuous time and space but finitely many local values. The closest model we know of is the Mondrian automata of Jacopini and Sontacchi [START_REF] Jacopini | Reversible parallel computation: an evolving space-model[END_REF] which is also reversible. Their space-time diagrams are mappings from R n to a finite set of colors representing bounded finite polyhedra. Another close model is the piecewise-constant derivative system [AM95,Bou99]: R n is partitioned into finitely many polygonal regions, trajectories are defined by a constant derivative on each region and form sequences of (Euclidean) line segments.

In this paper, space and time are restricted to rational numbers. This is possible since all the operations used preserve rationality. All quantifiers and intervals are over Q, not R.

The Turing computing capability of conservative signal machines is proved in [START_REF] Durand-Lose | Abstract geometrical computation for black hole computation (extended abstract)[END_REF][START_REF] Durand-Lose | Abstract geometrical computation 1: embedding black hole computations with rational numbers[END_REF] by simulating any 2-counter automaton since Turing machines and 2-counter automata compute exactly the same functions. To build a reversible version of the simulation, we have to cope with the inherent irreversibility of counter automaton (the result of Morita [START_REF] Morita | Universality of a reversible two-counter machine[END_REF] is not used here because it does not fit well with our approach): branching (there is no way to guess the previous instruction) and subtracting (0 comes from both 0 and 1).

To cope with this we add stacks to store information for reversibility. A stack over an alphabet {1, 2, . . . , l} is encoded by a rational number σ such that: 1 l+2 encodes the empty stack, otherwise 1 l+1 <σ<1. After pushing a value v on a stack σ the new stack is v+σ l+1 . The top of the stack is ⌊(l+1)σ⌋ and (l+1)σ-⌊(l+1)σ⌋ encodes the rest of the stack. This more or less corresponds to a base l+1 decimal number manipulation as can be found in e.g. [START_REF] Bournez | Achilles and the Tortoise climbing up the hyper-arithmetical hierarchy[END_REF].

This simple memory scheme can be implemented inside a reversible conservative rational signal machine. We then finish the simulation by adapting the construction from [START_REF] Durand-Lose | Abstract geometrical computation for black hole computation (extended abstract)[END_REF][START_REF] Durand-Lose | Abstract geometrical computation 1: embedding black hole computations with rational numbers[END_REF] by adding the storing of current line number before passing to the next and of the previous value of a counter whenever it reaches 0.

The definition of signal machines can be found in Sect. 2. Section 3 deals with 2-counter automata and their enhancement with stacks. Section 4 shows how the stacks are implemented. In Sect. 5, the different pieces are gathered in order to achieve the simulation. Section 6 gives a short conclusion.

Abstract geometrical computations

Abstract geometrical computations are defined by the following machines:

Definition 1 A rational signal machine is defined by (M, S, R) where M (metasignals) is a finite set, S (speeds) a mapping from M to Q and R (collision rules) a partial mapping from the subsets of M of cardinality at least 2 into the subsets of M (speeds must differ in both domain and range).

Each instance of a meta-signal is a signal. The mapping S assigns rational speeds to meta-signals. They correspond the slopes of the segments in space-time diagrams. The collision rules, denoted ρ -→ρ + , define what happens when two or more signals meet.

The extended value set, V , is the union of M and R plus two symbols: one for void, ⊘, and one for an accumulation (or black hole)

i. A configuration, c, is a total mapping from Q to V such that the set { x ∈ Q | c(x) = ⊘ } is finite.
A signal corresponding to a meta-signal µ at a position x, i.e. c(x) = µ, is moving uniformly with constant speed S(µ). A signal must start (resp. end) in the initial (resp. final) configuration or in a collision. These correspond to condition 2 in Def. 2. At a ρ -→ρ + collision signals corresponding to the metasignals in ρ -(resp. ρ + ) must end (resp. start); no other signal should be present (condition 3). A black hole corresponds to an accumulation of collisions and disappears without a trace (condition 4).

Let S min and S max be the minimal and maximal speeds. The causal past, or light-cone, arriving at position x and time t, J -(x, t), is defined by all the positions that might influence the information at (x, t) through signals, formally:

J -(x, t) = { (x ′ , t ′ ) | x -S max (t-t ′ ) ≤ x ′ ≤ x -S min (t-t ′ ) } . (x, t) J -(x, t)
Q × [0, T ] to V ) such that, ∀(x, t) ∈ Q × [0, T ] : 1. ∀t∈[0, T ], { x ∈ Q | c t (x) = ⊘ } is finite, 2. if c t (x)=µ then ∃t i , t f ∈[0, T ] with t i <t<t f or 0=t i =t<t f or t i <t=t f =T s.t.: -∀t ′ ∈ (t i , t f ), c t ′ (x + S(µ)(t ′ -t)) = µ , -t i = 0 or c ti (x i ) ∈ R and µ ∈ (c ti (x i )) + where x i = x + S(µ)(t i -t) , -t f = T or c t f (x f ) ∈ R and µ ∈ (c t f (x f )) -where x f = x + S(µ)(t f -t) ; 3. if c t (x)=ρ -→ρ + ∈ R then ∃ε, 0<ε, ∀t ′ ∈[t-ε, t+ε] ∩ [0, T ], ∀x ′ ∈[x -ε, x + ε], -c t ′ (x ′ ) ∈ ρ -∪ρ + ∪ {⊘}, -∀µ∈M , c t ′ (x ′ )=µ ⇒ µ ∈ ρ -and t ′ < t and x ′ = x + S(µ)(t ′ -t)) , µ ∈ ρ + and t < t ′ and x ′ = x + S(µ)(t ′ -t)) ; 4. if c t (x) = i then -∃ε > 0, ∀(x ′ , t ′ ) / ∈ J -(x, t), ( |x-x ′ |<ε and |t-t ′ |<ε ) ⇒ c t ′ (x) = ⊘ , -∀ε > 0, { (x ′ , t ′ ) ∈ J -(x, t) | t-ε<t ′ <t ∧ c t ′ (x ′ ) ∈ R } is infinite.
In the illustrations of space-time diagrams, time increases upwards.

Conservativeness

The three space-time diagrams on the right of Fig. 2 provide examples uncompatible with Def. 2 at the time of accumulation. In each case, the number of signals is bursting to infinity and black holes are not isolated. To prevent this, the following restriction is imposed.

Definition 3 A signal machine is conservative iff there exists an energy from meta-signals to positive integers, E : M → N * , such that the total energy of the system, i.e. the sum of the energies of all present signals, is constant.

One can check easily that the total energy is constant iff for each rule the sum of the energies of incoming meta-signals and the sum of outgoing ones are equal. It follows automatically that given a conservative signal machine and an initial configuration, the number of signals in any following configuration, as well as the number of accumulations, is bounded (by the total energy divided by the least atomic energy). A simple sub-case of conservativeness is when all the meta-signals have the same energy and the numbers of in and out meta-signals are always equal.

Reversibility

A dynamical systems is said to be reversible when from any configuration it is possible to generate all the previous configurations. Moreover, the inverse dynamical system should be of the same nature.

Concerning signal machines, the "inversion" of an isolated signal is the same signal with opposite speed. Regarding collision, one has to guess its position and the in-coming signals from the out-going ones. Collisions resulting in nothing are impossible to guess going backward, and they cannot be conservative. Collisions resulting in only one signal are also impossible to predict. Reversibility holds if and only if the (partial mapping) M is one-to-one and always yields 2 or more out-going meta-signals. The inverse signal machine is the same with the rules reversed.

Definition 4 A signal machine is reversible if and only if R is one-to-one and maps only on sets of cardinality at least 2.

Let us point out this is true as long as there is no accumulation! The way an accumulation disappears is like a (second order) collision resulting in nothing. Moreover if its location could be guessed, there are infinitely many way to scale it since there is no absolute scale for space nor time.

2-counter automaton with stack

A 2-counter automaton is a finite automaton coupled with two counters, A and B. The possible actions on any counter are add/subtract 1 and branch if nonzero. Such an automaton can be described with a six-operations assembly language with branching labels as on the left part of Fig. 6 (see [START_REF] Minsky | Finite and infinite machines[END_REF] for more on 2-counter automata). The configuration of a 2-counter automaton is defined by (n, a, b) (the line number and the values of the counters).

Two-counter automaton are intrinsically irreversible: subtracting 1 yields 0 for both values 0 and 1 and before a labeled instruction the instruction can be the one on the previous line or a branching to this label.

To achieve reversibility two stacks are added: one, Σ i , records the instruction number (i.e. it records the values of the instruction counter) and another one, Σ z , record the previous value (0 or 1) of any counter that holds zero after a subtraction. We write x.Σ to indicate pushing x on S or that x is the top of the stack. The dynamics is described on Fig. 3 for instructions on A. The ones for B are similar. Discarding the stacks, one gets the usual dynamics. The inverse dynamics is automatic (as long as the sequence was generated legally, otherwise things like undoing adding 1 from a zero counter might happen).

Instruction at line n

Associated action A ++ ( n, a, b, Σi, Σz ) ⊢ ( n + 1, a + 1, b, n.Σi, Σz ) A -- ( n, a + 2, b, Σi, Σz ) ⊢ ( n + 1, a + 1, b, n.Σi, Σz ) A -- ( n, 1, b, Σi, Σz ) ⊢ ( n + 1, 0, b, n.Σi, 1.Σz ) A -- ( n, 0, b, Σi, Σz ) ⊢ ( n + 1, 0, b, n.Σi, 0.Σz ) IF A != 0 m ( n, 0, b, Σi, Σz ) ⊢ ( n + 1, 0, b, n.Σi, Σz ) IF A != 0 m ( n, a + 1, b, Σi, Σz ) ⊢ ( m, a + 1, b, n.Σi, Σz )
Fig. 3. Dynamics of a 2-counter automata with memory stacks.

Stack implementation

Since we are dealing with rational numbers, it is very easy to implement an unbounded stack of natural numbers 1 to l in the following way: 1 l+2 encodes the empty stack. Let σ be a rational number encoding of a stack (0<σ<1). After pushing a value v on top of a stack σ, the new stack is v+σ l+1 . This ensures that, as soon as the stack is not empty, 1 l+1 <σ<1 and distinct from i l+1 , i ∈ {1, 2, . . . , l}. The top of the stack ⌊(l+1)σ⌋ and rest of the stack is (l+1)σ -⌊(l+1)σ⌋.

To implement this in a signal machine, a scale is defined (because the space is continuous and scaleless) and then the push operation is implemented. We are not interested in the pop and test of emptiness because our 2-counter simulation only pushes values. The pop corresponds to the inverse of push and is thus implicitly built.

The rational σ is encoded with a zero-speed signal mem. The scale is defined with zero-speed signals mark 0 , mark 1 ,. . . , mark l . They are regularly positioned, never move and defined positions 0, 1, . . . , l. Thus the normal position of mem is between mark 0 and mark 1 . To push v, mem is translated by v (lower part of Fig. 4). Then this position is scaled by 1 l+1 (upper part of Fig. 4) to get σ+v l+1 . The process starts at the arrival of ← --store v . Translating is very easy: --→ mem and ---→ store v are parallel. Their distance encodes σ. Their movement stops when the first one, ---→ store v , reaches mark v . The signal catch is then issued to stop --→ mem as in the middle of Fig. 4. This collision is distance v away from the original position of mem. This is ensured by the definition of speeds (we leave to the reader to verify this linear equation system based on the speeds given in Fig. 4). When this point is reached, a scaling remains to be done. Scaling by 1 l+1 , to go from σ+v to σ+v l+1 , fix has to travel (σ+v)-σ+v l+1 = (σ+v) l l+1 units, and ←-mem and --→ mem have to travel (σ+v) + σ+v l+1 = (σ+v) l+2 l+1 units. Thus if the speeds of ←-mem and --→ mem have the same absolute value then the speed of fix must be l l+2 times the one of ←-mem (notice in Fig. 4 that -2 = -3 4 4+2 ). If the stack is empty, then backward collision between ←-mem and fix happens between mark 0 and mark 1 . So that there is a (backward) collision between --→ mem (regenerated from mark 0 and ←-mem) and catch. There no such a rule, it can be defined to have, for example, mem fixed and catch exiting on the left. It is easy to check that the rules are invertible. Let us note that, with slight modifications, ← --store v and ack could come from/be sent left or right. It is also possible to carry extra information (like a next line number) through the storing process. This is done by having a special set of ← --store i , ---→ store i , catch, fix, and ack for each possible piece of information.

←--mem -3 mem 0 --→ mem 3 ← --- storei -3 ---→ storei 3 catch 1 fix -2 ack 3 Rules {mem, ← --- storev} → { ←--mem, ---→ storev} {mark0, ←--mem} → {mark0, --→ mem} { ---→ storev , markv} → {markv, catch} { --→ mem, catch} → { ←--mem, fix} { --→ mem, fix} → {mem, ack} {marki, ← --- storev } → { ← --- storev , marki} v < i, { ---→ storev , marki} → {marki, ---→ storev } { --→ mem, marki} → {marki, --→ mem} {marki, ← -- mem} → { ← -- mem, marki} {marki, fix} → {fix, marki} {ack, marki} → {marki, ack}

Reversible computation

The idea is to use the construction provided in [START_REF] Durand-Lose | Abstract geometrical computation for black hole computation (extended abstract)[END_REF] to simulate any 2-counter automaton with a conserving signal machine (which cannot be detailed here).

Figure 5 shows how the counters are encoded using two fixed signals zero and one as a scale. A signal amounting for the current line zigzags between these signals. Figure 6 presents the code of a simple 2-counter automaton and some simulations. When a simulation stops, a signal stop appears and bounces between zero and one. In the reversible version, it exits the configuration on the right. Figure 7 show how everything is interconnected. Before going to the next configuration, the number of the just carried out instruction is stored on the left while recording the next instruction number. Each time there is a subtract 1 generating a 0, the previous value of the counter is stored on the right (cases (1, 0) and (0, 1)) whatever counter is concerned.

Conclusion

As far as there is no accumulation, reversible conservative rational abstract geometrical computation has exactly the same computing capability as Turing machines (because rational numbers can be implemented exactly).

Two-counter automaton are exponentially slower than Turing machines. This is not important since we are only interested in computational issues. Nevertheless, it is easy to simulate reversibly (but without conservativeness) Turing machine in such a way that the number of collisions is proportional to the number of TM iterations. It would be interesting to do so to study the complexity.

It is possible to apply the iterated shrinking construction of [DL05a,DL06] which preserves reversibility so that the black hole models can now be embedded in a reversible setting. We do not do it here for lack of room on one side and on the other side this would provoke an accumulation which is clearly not a reversible phenomena.

Fig. 1 .

 1 Fig. 1. Space-time diagram of a cellular automaton and its signal machine counterpart.

Fig. 2 .

 2 Fig. 2. Light-cone, a simple accumulation and three unwanted phenomena.

Fig. 4 .

 4 Fig. 4. Implementation the stack for l = 4 and push(3).

Fig. 5 .Fig. 6 .

 56 Fig. 5. Encoding positions of counters.


Jérôme Durand-Lose
email: lose@univ-orleans.fr

Irrationality is needed to compute with signal machines with only three speeds

Keywords: Accumulation, Computability, Fractal, Model of computation, Signal machine, Turing machine, Unconventional computation

Space-time diagrams of signal machines on nite congurations are composed of interconnected line segments in the Euclidean plane. As the system runs, a network emerges. If segments extend only in one or two directions, the dynamics is nite and simplistic. With four directions, it is known that fractal generation, accumulation and any Turing computation are possible. This communication deals with the three directions/speeds case. If there is no irrational ratio (between initial distances between signals or between speeds) then the network follows a mesh preventing accumulation and forcing a cyclic behavior. With an irrational ratio (here, the Golden ratio) between initial distances, it becomes possible to provoke an accumulation that generates innitely many interacting signals in a bounded portion of the Euclidean plane. This behavior is then controlled and used in order to simulate a Turing machine and generate a 25-state 3-speed Turinguniversal signal machine.

Introduction

Imagine yourself with some color pencils and a sheet of paper together with ruler and compass. Some colored line segments are drawn and you are given rules so as to extend the drawing. According to the rules and the initial drawing/conguration you might stop soon, have to extend the paper indenitely or draw forever in a bounded part of the paper as on top of Fig. 1(a). Could such a system compute?

This communication concentrates on the case where the dynamical system is a signal machine. In this setting, one drawing direction is distinguished and used as time axis. Line segments are enlarged synchronously until they intersect one another and get replaced. This goes on until no more collision can happen.

The line segments are the traces of signals and their intersections are collisions. Each signal corresponds to some meta-signal. During a collision, in-coming (c) Two speeds: nitely many collisions. Problematics. Signal machines are very powerful and colorful complex systems capable of computing in the classical Turing understanding [START_REF] Durand-Lose | Abstract geometrical computation: Turing computing ability and undecidability[END_REF]. This communication is in the line of minimality thresholds in order to have Turing-computability capability (like [START_REF] Rogozhin | Small universal Turing machines[END_REF][START_REF] Woods | The complexity of small universal Turing machines: A survey[END_REF] for Turing machines and [START_REF] Cook | Universality in elementary cellular automata[END_REF][START_REF] Ollinger | Four states are enough! Theoret[END_REF] for cellular automata; a more general picture is presented in [START_REF] Margenstern | Frontier between decidability and undecidability: a survey[END_REF]). This communication extends [START_REF] Durand-Lose | Abstract geometrical computation 4: small Turing universal signal machines[END_REF] on small Turing-universal signal machines (few meta-signals but 4+ speeds) and [START_REF] Becker | Abstract geometrical computation 8: Small machines, accumulations & rationality[END_REF] that addresses only accumulation (i.e. not computation) with 3-speed signal machines.

Accumulations are easy to produce and are the cornerstone to hyper-computation in the model [START_REF] Durand-Lose | Abstract geometrical computation 3: Black holes for classical and analog computing[END_REF]. The present communication investigates the minimal number of speeds so that accumulations or Turing computations are possible (starting from a nite conguration). Four meta-signals of dierent speeds are enough to make an accumulation as depicted in Fig. 1(a). Four speeds and 15 meta-signals are enough to compute [START_REF] Durand-Lose | Abstract geometrical computation 4: small Turing universal signal machines[END_REF].

In this communication, only the number of dierent speeds is considered and in particular the case of three speeds. One speed does not allow any collision (see Fig. 1(b)). With two speeds, the number of collisions is nite and signals have to follow a regular grid which has no accumulation (see Fig. 1(c)). Three-speed signal machines with rational speeds and rational initial positions always enter a cyclic behavior with no accumulation and limited computing capability. But if an irrational ratio between distances in the initial conguration is allowed, then accumulations are possible as well as any Turing computation.

State of the art. Signal machines are one of the unconventional models of computation dealing with Euclidean geometry together with Euclidean abstract machines [START_REF] Huckenbeck | Euclidian geometry in terms of automata theory[END_REF][START_REF] Mycka | The euclid abstract machine: Trisection of the angle and the halting problem[END_REF], Piecewise Constant Derivatives systems [START_REF] Bournez | Some bounds on the computational power of piecewise constant derivative systems (extended abstract)[END_REF] and colored universes [START_REF] Jacopini | Reversible parallel computation: an evolving spacemodel[END_REF].

Signal machines were originally introduced as a continuous counterpart of (discrete) cellular automata to provide a context for the underlying Euclidean (continuous) reasoning often found in the literature as well as to propose an abstract formalization of the concept of signal [1416].

Accumulations provide a powerful tool to accelerate a computation, to do hyper-computation and analog computation [START_REF] Durand-Lose | Abstract geometrical computation 3: Black holes for classical and analog computing[END_REF]. Fractals can be generated and their construction modied so as to achieve massive parallelism and the capability to solve eciently NSPACE-complete problems (Q-SAT in [START_REF] Duchier | Computing in the fractal cloud: modular generic solvers for SAT and Q-SAT variants[END_REF]).

In [START_REF] Becker | Abstract geometrical computation 8: Small machines, accumulations & rationality[END_REF], the present author and colleagues already proved that irrational ratio between speeds or between initial distances is needed in order to have an accumulation with three speeds. They exhibit a geometrical implantation of the Euclid algorithm inside the computation. If all ratios are rational then this algorithm stops (generating a non-accumulating mesh) otherwise it goes on indenitely provoking the accumulation. They also cover the case of an irrational ratio between speeds which is not addressed here.

Contribution. If all the ratios are rational, then some global regular mesh emerges.

The signals have to be on that mesh which does not have any accumulation point.

Moreover, being on this mesh ensures that the collisions have to be ultimately periodic so that the dynamics is ultimately cyclic and computing capability is limited. (The behavior is called cyclic and not periodic since at the conguration level, there is no periodicity.) Using the Golden ratio between distances makes it possible to draw a fractal which accumulates. Because of self-similarity, ensuring one repetition step is enough.

With three speeds, it is straightforward to simulate a Turing machine on a bounded tape. But even though the tape remains nite, it cannot be bounded in the general case. From the fractal construction, a scheme is extracted to extend the tape on demand and get the full Turing computing power.

Outline. Section 2 provides all the denitions. Section 3 shows that in the rational case the dynamics is trapped into a mesh that does not allow any accumulation and restrain computing capability. Section 4 shows how to get an accumulation with non-rational ratio between distances. Section 5 provides the simulation of any Turing machine in such a case. Conclusion, remarks and perspectives are gathered in Sect. 6.

Denitions

This communication deals only with nite congurations so all denitions are restrained to this case.

A signal machine collects the denitions of available meta-signals, their speeds (positive for rightward signals and negative for leftward ones) and their collision rules. For example, the machine to generate Fig. 1(a) is composed of the following meta-signals (with speed): le ( 12 ), zig (4), zag (-4), and ri (-1

2 ). There

(let V = M ∪ R ∪ { } so that c : R → V ) such that |c -1 (M ∪ R)| < ∞.
If there is a signal of speed s at x, then, unless it enters a collision before, after a duration ∆t, its position is x + s•∆t.

∃x 1 , x 2 ∈R, x 1 = x 2 , ∃µ 1 , µ 2 ∈M    x 1 + d•S(µ 1 ) = x 2 + d•S(µ 2 ) , c(x 1 ) = µ 1 ∨ (c(x 1 ) = ρ -→ ρ + ∧ µ 1 ∈ ρ + ) , c(x 2 ) = µ 2 ∨ (c(x 2 ) = ρ -→ ρ + ∧ µ 2 ∈ ρ + ) .
It is +∞ if there is no such d. The sequence of collision times is dened by: t 0 = 0, t n+1 = t n + ∆(c t n ) where c t denote the conguration at time t.

This sequence is nite if there is an n such that ∆(c t n ) = +∞. Otherwise, since it is non-decreasing, it admits a limit. If the sequence is nite or its limit is innite, then the whole space-time diagram is dened. Otherwise, there is an accumulation and the limit conguration is left undened. Denition 4 (Dynamics between collisions) For t between t and t+∆(c t ), the conguration at t is dened as follows. Signals are set:

c t (x ) = µ i c t (x) = µ∨(c t (x) = ρ -→ ρ + ∧µ ∈ ρ + ) where x = x +(t-t )•S(

µ).

(There is no collision to set.) It is everywhere else.

Denition 5 (Dynamics at a collision time) For the conguration at t = t + ∆(c t ), collisions are set rst:

c t (x ) = ρ -→ ρ + i for all µ ∈ ρ -, c t (x µ ) = µ∨(c t (x µ ) = ρ -→ ρ + ∧µ ∈ ρ + ) where x µ = x +(t-t )•S(µ).
Then meta-signals are set (where there is not already a collision). It is everywhere else.

A space-time diagram is the collection of consecutive congurations which forms a two dimensional picture. In the space-time diagram in Fig. 1(a) the sequence of collision times is given by the collisions of zig on ri, then zag on le, then zig on ri... This sequence accumulates on top of the space-time diagram.

Denition 6 (Rational signal machine) A signal machine is rational if all speeds are rational numbers and any non-position in any initial conguration must also be a rational number.

Since the position of collisions are solutions of systems of rational linear equations, they are rational. (Coordinates of accumulation may be non-rational [START_REF] Durand-Lose | Abstract geometrical computation 7: Geometrical accumulations and computably enumerable real numbers[END_REF].)

Denition 7 (Rational-like) A signal machine is rational-like if its speeds are rational up to a coecient. (There is no restriction on possible initial conguration.) A conguration is rational-like if all the ratios between distances between signals are rational.

Linear transformation. It is possible to linearly change the speed of the metasignals or the positions in the initial conguration. As long as the coecient is positive, the dynamics is not changed. This comes from the absence of any absolute origin or scale. This is not formally proved (this was done, e.g., in [START_REF] Durand-Lose | Calculer géométriquement sur le plan machines à signaux[END_REF]Chap. 5]), but exemplied by the space-time diagrams in Fig. 2.

A linear transformation with a positive ratio of all the positions in the initial conguration only corresponds to changing the spatial origin and the space scale (Fig. 2(a)), time scale has to be changed accordingly.

A linear transformation with a positive ratio of all the speeds of the signal machine results in a change in the scale of time (but not of space, Fig. 2(b)).

The term added corresponds to a drift, i.e. a slant in the time axis (Fig. 2(c)).

(a) Initial positions divided by 2.

(b) Speeds multiplied by 2.

(c) Speeds multiplied by 2 plus 1. Only locations are aected. The existence of a collision as well as the computing capability does not depend on linear transformations with positive ratio.

Normalization. When considering a nite set of real numbers, there is always a unique linear transformation with positive ratio that maps the two lowest values in the set to 0 and 1. We call this a 0-1-normalization.

If all ratios between distances in a conguration are rational then its 0-1normalization has only signals at rational coordinates: with O and I the signals with new coordinate 0 and 1, a signal at position M have coordinate OM /OI which is rational since non-degenerated linear operators preserve ratio.

That ratios between distances are rational is both a sucient and necessary condition to rescale into Q. Up to normalization, the dynamics of a rational-like signal machine on a rational-like conguration is the one of a rational signal machine.

3 Rational 3-speed signal machines

If speeds are rational up to a coecient, then their 0-1-normalization results in rational speeds. The 0-1-normalized speeds are 0, 1, and (a rational value greater than 1) 1+p/q (with p, q ∈ N, 1 ≤ p, q and relatively prime). They are linearly transformed into -q, 0 and p.

The 0-1-normalized initial conguration is scaled so that all (signal) positions are natural numbers. The extreme positions are 0 and n.

Denition 8 ((p, q, n)-mesh) The (p, q, n)-mesh corresponds to the union of the following half-lines of R × R + : V v : x = v/(p+q) where v ∈ {0, 1, 2, . . . , n(p+q)}, L l : x ≤ n, and x + q.t = l/p where l ∈ {0, 1, 2, . . . } and R r : 0 ≤ x and xp.t = r/q where r ∈ {. . . , -1, 0, 1, 2, . . . , (n.q)}. Figure 3 shows the display of such a mesh. Half-lines V v are vertical, L l have a negative slope and are dotted and R r have a positive slope and are dashed. A mesh has only L l half-lines when x < 0 and only R r half-lines when n < x. When 0 ≤ x ≤ n, then all three kinds of lines are present and each every point of intersection is incident upon a line of each type. Moreover, there is a line of each kind starting at positions (x, 0) when x ∈ {0, 1, 2, ..., n}.

Lemma 1. During the computation of a rational machine with speeds -q, 0 and p from an initial conguration with no signal outside of {0, 1, 2, ..., n}, there is no signal outside the mesh (p, q, n). This is true because: initially signals are on the mesh on a half-line with the same speed/slope (all are issued from coordinates in {0, 1, 2, ..., n}); if a signal is on such half-lines, it remains upon it until it participates in a collision; and new signals appear only in collisions, collisions can only happen at line crossings and all three kinds of lines go on from there.

If the computation would lead to an accumulation, then this accumulation should also be on the mesh. But the mesh has no accumulation.

The mesh is time periodic in the region 0 ≤ x ≤ n and the computation in this part does not receive anything from the outside. When considering the congurations at time where lines intersect on x = 0, the mesh is exactly the same. On 0 ≤ x ≤ n, these congurations can be described by a xed length string on meta-signals and collision rules. Since this alphabet is nite (and the system is deterministic), this eventually enters a cycle.

Outside of the region 0 ≤ x ≤ n, the mesh is also ultimately time-periodic.

No collision happens there and the output signals also eventually enter a cycle. This also holds for rational-like machines on rational-like initial congurations.

Accumulation with the Golden ratio

Using the Golden ratio, it is possible to generate the accumulating fractal in Fig. 4(a). The signal machine is directly read from the picture as depicted in Fig. 4(b). The signal machine is rational-like but not rational since the initial conguration is not.

The initial conguration is not part of the fractal cycle since we prefer to have all signals but one parallel. The distance between cell and seed is taken to be one. The exact position of right between cell and seed is not important. To position border, ϕ has to be given a value so that the fractal is generated, i.e. the ratio of the distance of the three last signals is preserved.

As indicated in Fig. 4(b), the rst ratio is ϕ 1 . To compute the next ratio, the distance between the third cell and border has to be 1 because of the presence of the parallelogram (with left and right sides) and the parallelism of the cell and By equaling these ratios, ϕ is 1+ √ 5 2 , the Golden ratio.

The construction then repeats forever. The ratio is preserved and the fractal is generated. Lemma 3. A 3-speed signal machine started on an irrational conguration can generate an accumulation, even when all speeds are rational.

In fact, this is for any non-rational ratio. Moreover, any non-rational ratio between speeds can also be transferred into distances so that an accumulation can be produced [START_REF] Becker | Abstract geometrical computation 8: Small machines, accumulations & rationality[END_REF]. q 1 q 0 , a → b, q 1 b a q 0 q 1 a, q 0 → b, q 1 (b) Transition case δ(q 0 , a) = (q 1 , b, →)

Computing with the Golden ratio

Meta-signal Speed q 0 , q 1 -2 q 0 , q 1 2 q 1 q 1 q 0 q 0 (c) States {q 0 , q 1 } b a q 0 q 1 q 0 , a → q 1 , b b a q 0 q 1 a, q 0 → q 1 , b (d) Transition case δ(q 0 , a) = (q 1 , b, ←)
0 . . . c b b q 0 . . . c c b q 0 . . . c c c # q 0 . . . c c c b q 1 . . . c c b b q 1 . . . (a) Turing machine run q 0 a q 0 b q 0 c c q 0 b q 0 q 0 b q 0 b q 0 border c
e n l a r g e c l e f t r i g h t q 0 r i g h t c r i g h t

q 0 c q 1 q 1 b q 1 border c c b c
e n l a r g eq 1 (b) Labeled simulation (c) Longer simulation this means that the head is looking for a cell that does not exist yet. Signal border is replaced by a motionless signal encoding the state (q 0 in the gure) and preserving the position of border. Simultaneously, an enlarge signal is sent on the left to create the new cell.

This creation uses the same parallelogram construction as before (dotted signals left and right) and closed on top by q 0 . The lower right is used to restore border and set q 0 on movement. The latter, instead of colliding with a symbol signal, collides with the upper right. The collision happens as if it were on the blank symbol. The needed meta-signals and collision rules are given in Fig. 7.

Meta-signal Speed left, enlarge -2 right 2 border 0 (a) Extra symbols a r i g h t e n l a r g e q 0 right, q 0 → q 0 , border q 0 , border → enlarge, q 0 (f) For each state q 0 Fig. 7. Extra encoding to enlarge the simulation.

q 0 q 1 right, q 0 → a, q 1 (b) Case δ(q 0 , #) = (q 1 , a, →) a r i g h t q 0 q 1 right, q 0 → q 1 , a (c) Case δ(q 0 , #) = (q 1 , a, ←) q 0 q 1 Meta-signal Speed q 0 , q 1 0 (d) States {q 0 , q 1 } a a

Conclusion and perspectives

With three speeds, it is possible to accumulate only if there is an irrational ratio between initial positions or between speeds (see [START_REF] Becker | Abstract geometrical computation 8: Small machines, accumulations & rationality[END_REF] for speeds).

The number of meta-signals for the Turing-machine simulation with the Golden ratio is 1 for each symbol plus 3 for each state plus 4. With the small universal Turing machines listed in [START_REF] Woods | The complexity of small universal Turing machines: A survey[END_REF], a Turing-universal 25-meta-signal 3-speed signal machine using a Golden ratio distance can be constructed.

With a Golden ratio location, undecidable problems arise. Directly from classical computability theory, to have only nitely many collisions (or to enter a cyclic behavior) is not decidable. In the simulation of a Turing machine, if the head goes on the right each time, then an accumulation is generated. For an accumulation to happen, the head would have to explore all the cells on the right which is also not decidable. (In the general case, forecasting an accumulation is Σ 0 2 -complete [20].) An irrational ratio is an important piece of information (it could encode the halting problem). We conjecture that it is possible to use it as an oracle.

In [START_REF] Durand-Lose | Abstract geometrical computation 3: Black holes for classical and analog computing[END_REF], accumulations are used in order to hyper-compute, with an irrational ratio, computations and accumulations become possible, we conjecture that it is possible to solve the halting problem and even to climb the nite levels of the arithmetic hierarchy with three speeds and the Golden ratio.

Signal machines are know to be able to do analog computations [START_REF] Durand-Lose | Abstract geometrical computation 3: Black holes for classical and analog computing[END_REF] with real numbers encoded in distances. Up to what extent is analog computation possible with three speeds?

Fig. 1 .

 1 Fig. 1. Basic cases.

Denition 1 (

 1 are only two collision rules: le, zag -→ le, zig and zig, ri -→ zag, ri . It might happen that exactly three (or more) meta-signals meet. In such a case, collision rules involving three (or more) meta-signals are used. There can be any number of meta-signals in the range of a collision rule, as long as their speeds dier (i.e. they are not parallel). Signal machine) A Signal machine, (M, S, R), is dened by: M is a nite set of meta-signals, S is a function from meta-signals to real numbers, assigning speeds, and R is a deterministic set of collision rules. A collision rule is written ρ = ρ -→ ρ + where ρ -and ρ + are sets of meta-signals of dierent speeds, and ρ -must have at least two meta-signals. The set of collision, rules, R is deterministic: ρ = ρ implies that ρ -= ρ -. A conguration is a function from the real line (space) into the set of metasignals and collision rules plus one extra value (nothing there). There should be nitely many non-locations. Denition 2 (Conguration) A conguration, c, is a function from the real line into meta-signals, rules, and the value

  At a collision, all incoming signals are immediately replaced by outgoing signals in the following congurations according to collision rules. Denition 3 (Sequence of collision times) Considering a conguration, c, the time to the next collision, ∆(c), is equal to the minimum of the positive real numbers d such that:

Fig. 2 .

 2 Fig. 2. Linear transformations on the space-time diagram of Fig. 1(a).

Fig. 3 .

 3 Fig. 3. (3, 2, 3)-mesh.

Rational 3 -

 3 speed signal machines always enter a cyclic behavior. Transient time and cycle duration can be computed from the initial conguration and machine. These bounds prevent Turing-universality. Lemma 2. Rational 3-speed signal machines cannot produce accumulation and are not Turing-universal.

Fig. 4 .

 4 Fig. 4. Accumulating with three speeds and an irrational position.

Fig. 5 .

 5 Fig.5. An example of this simulation is given on the lower half of Fig.6.The tape is nite but not bounded. Starting from a nite conguration, the representation of the tape should be enlargeable. The fractal presented in previous section allows one to generate an unbounded sequence of sites (purposely named cell) to simulate the tape of a Turing machine. It is not fully generated to avoid an accumulation. A new cell is generated only when the tape needs enlargement.An enlargement can be seen on the upper half of Fig.6(b). It is started when a rightward state-encoding signal (q 0 in the gure) reaches the border signal,

Fig. 5 .

 5 Fig. 5. Basic encoding of a Turing machine.

Fig. 6 .

 6 Fig. 6. Computing with three speeds and an irrational position.

This work was partially funded by the ANR project AGAPE, ANR-09-BLAN-0159-03. Jerome.