A visual introduction and software to
Abstract Geometrical Computation and signal machines

Here are two examples of the dynamics of signals machines. The left one is a random machine while the right one is designed as a never-ending divide and conquer.

This dynamics system was devised for for Habilitation à Diriger des Recherches (Durand-Lose, 2003) and has been investigated since. In 2014, these researches have been presented in the french newsstand journal Pour la Sciences (Delahaye,Jean-Paul, 2014, in French). The pictures are orbits or space-time diagrams of a special kind of dynamical systems called signal machines. In a one-dimensional space, dimensionless points move in a uniform way, when the collide, they are replaced according to rules. In every picture time elapses upward. The animation shows how the space-time diagram are generated.

1 Basics

1.1 Definitions and first example

The signals are instances of meta-signals. Each signal moves at constant speed. This speed id defined by the associated meta-signal. There are finitely many meta-signals as on the upper table.

When signal meet, they are replaced by other signals (possibly one or none). What signals are output depends only on the meta-signals associated with incoming signals. For example, the first rule states that if blue and black collide then black and green are generated. The rules are defined on the lower table (by default the same meta-signals are generated).

Please note that signals are evolving on the real line and have no dimension and that there is no absolute scale nor coordinates.

This signal machine is used to generate the space-time diagram on the left.

Meta-signals

Identifier Speed black 0 blue, yellow 1 green 2 red -2 orange, purple -1

Collision rules

In-coming Out-going { blue, black } $\to$ { black, green } { green, black } $\to$ { black, yellow } { yellow, black } $\to$ { orange, black } { black, orange } $\to$ { red, black } { black, red } $\to$ { purple , black } { black, purple } $\to$ { black, blue } { blue, black, red } $\to$ { purple , black, green } { green, black, orange } $\to$ { red, black, yellow }

1.2 Examples

Other examples of diagrams are provided below.

1.3 Rational signal machines

This is the restriction to signal machines such that:

• speeds are rational numbers, and

• signals are positions at rational coordinates in the initial configuration (for some coordinate system).

A direct induction show that collisions happens at positions with rational numbers positions. Since rational can be represented exactly on a computer as the coordinates of collisions computed exactly, these machines can be simulated exactly (this have been done, see Sect. 7).

All the illustrations are done with rational signal machine.

2 Relating to classical discrete models of computation

“Away” from special phenomena (see next sections), rational signal machines are equivalent to Turing machines since they can be simulated exactly on a computer and can simulate a Turing machine ans any equivalent model.

2.1 Simulating a 2-counter automaton

This is one way to achieve Turing-universality, 2-counter automaton are easy to implement, but their computing time has an exponential slowdown compared to Turing machines, RAM machines, etc. A two counter automaton can add 1, subtract 1 and test for zero and branch on each counter.

Each counter is encoded by its distance to the leftmost signal: $n$ corresponds to the distance $\frac{\alpha }{2^n}$ for some $\alpha$ in $(1,2)$ . So that increasing (resp. decreasing) a counter correspond to a division (resp. multiplication) by $2$ of the distance which are classical constructions for signal machines. Testing for zero is done by adding a signal at the position $1$ (it also serve as scale): starting from the left, it is met before the signal encoding a counter only if this counter is zero.

In the pictures, the signal for the first counter ($A$) is green while the second counter ($B$) is in purple.

$A=0$	$A=0$	$A=0$
$B=1$	$B=2$	$B=3$

2.2 Simulating a cellular automaton on ultimately periodic configurations

This is an example where a discrete lattice/grid is generated. The cellular automaton runs on this grid: updates at crossing, the signals ensure communication between cells.

The side signals generates the boundary to have a finite configuration (quiescent outside of a finite number of cells). The configuration is unbounded and extends on both sides.

2.3 Simulating a cyclic tag system

Cyclic tag systems were proven Turing-universal and used to prove the universality of CA rule 110 (Cook, 2004). By simulating CTS, it was proven that it is possible to be Turing-universal with only 13 meta-signals Durand-Lose (2011a). One iteration of the CTS is shown as well as a full computation.

One can also wonder what is the minimal number of speeds to compute: two is no enough while four is. What about 3 speeds? the answer is interesting and involves Euclid’s algorithm! With 3 speeds, it is impossible to compute with a rational signal machine (on a finite initial configuration). Yet is it possible to do so if a ratio between speeds or between initial position is not. Why? well in one case Euclid’s algorithm stops and globally the signals will be imprisoned in some finite mesh making the memory finite (Durand-Lose, 2013).

3 Fractals and accumulations

3.1 Examples and generation

Since space and time are continuous. This can be used to provoke accumulation on one point or on a segment.

This can be modified to produce an infinite accumulation of signals or an accumulation on a Cantor set.

The context allows to address the Zenon paradox: infinitely many collision (discrete events) during a finite duration.

3.2 Trying to deal with accumulations

Accumulation arise naturally as fractal are generated. The simplest way to deal with it is to say that the space-time diagram is not defined from this date on. One step ahead is to use a special value at the location and to left undefined the space-time diagram in the cone of light (i.e. any location that could be reached by a signal issued from the location or above).

Trying to extends the space-time from such points could lead to undeterminism or event uncoherence.

They can be used to do analog computation in the understanding of computable analysis (Weihrauch, 2000; Durand-Lose, 2011b) and also of the semi-algebraic approach of Blum, Shub and Smale Blum et al. (1989); Durand-Lose (2007, 2008).

As displayed, four speeds are enough to generate an accumulation. With two speeds (regardless of the number of meta-signals) it is impossible to generate any.

What about three speeds? the answer is interesting and involves Euclid’s algorithm like for computing with three speeds With three speeds, it is impossible to generate an accumulation with a rational signal machine (on a finite initial configuration). Yet is it possible to do so if a ratio between speeds or between initial position is not. Why? well in one case Euclid’s algorithm stops and globally the signals will be imprisoned in some finite mesh (Becker et al., 2018).

3.3 Forecasting an accumulation is ${\mathrm{\Sigma }}_1^0$-complete

The problem is to be able to forecast the appearance of an accumulation of a rational signal machine for some initial configuration. Since rational signal machines can be simulated exactly on a computer, this problem can be expressed in the classical context of (discrete) computability. Since it is possible to simulate a Turing machine, one can devise a signal machine and initial configuration such that an accumulation is produced after the Turing machine halts. This means that the problem is undecidable. So the question went to “how much undecidable”.

It is as undecidable as whether a program computes a non-total function —one jump higher than the halting problem— (Durand-Lose, 2006). To prove this, a logical characterisation proved that is belongs to ${\mathrm{\Sigma }}_1^0$. The hardness was proven by constructing, for every two-counter machine, a signal machine and initial configuration that produces at accumulation if there exists an initial valuation of its counters such that teh computation never ends.

This is illustrated with the following picture where the main structure generates the counter values $(0,0)$ (bottom), $(1,0)$, $(0,1)$ (one line above), $(1,0)$, $(1,1)$, $(0,2)$ etc. At each intersection/for each valuation, a two counter automaton is started in a iterated shrinking structure (see Sect. 4.2). if the computation stops, the iterated shrinking structure is erased preventing the corresponding accumulation.

3.4 Accumulations on sets

For rational signal machines, if there is an isolated accumulations point, then it must happen at a time that is its a computably-enumerable real number and at a position that is the differences of such numbers(Durand-Lose, 2012).

The set of accumulation point can be very complicated. As presented above, it can be a Cantor set or a horizontal segment. Modifying the construction, the segment can be slanted (Durand-Lose and Emmanuel, 2021).

More involving, the accumulation set can form the graph of any continuous function (Emmanuel, 2023).

4 Geometric features

4.1 Basic operations to translate and to re-scale

These are geometrical primitives specific to the system. The idea is that a portion of the space-time diagram can be moved, scaled, bend, etc. such that the pieces still form the initial space-time diagram. This is possible because of the Euclidean setting, the absence of absolute scale/origin/coordinates and the null-width of signals. The basic tool underneath is that parallel lines preserves relative distances: once “frozen” into parallel signals, the configuration can be moved around.

On the left, the system is stopped then shifted and restarted. The middle picture show how a configuration ca be scaled (here halved). The right picture show an application of this scaling.

4.2 Embedding an infinite diagram into a shrinking structure

The construction in previous section can be iterated so that the whole original space-time diagram is contained in a bounded part!

It uses above constructions infinitely iterated. The iteration structure is displayed on the left. On the right, this structure/operator operated on a space-time diagram of the first section.

4.3 Local homothetic transformations

It is possible to have part of the space-time diagram modified with a homothetic transformation automatically. Homothetic is not the right word, on one axis there is no scaling (this direction can be used for a continuous on and off) and different from one on another direction.

In the left picture below, the space-time the scaling goes on and off with the crossing of the signals from the left.

In the right picture below, four zone are identified. The bottom and top zones are unmodified while the two middle zone are.

Please note that frontier speed/slopes are defined by the modifications on each side.

5 Fractal computation

Since space and time are continuous, it is always possible to find room for extra signals or to shrink down the computation. This is used to solve the satisfaction problem of boolean formula. The first step is to produce a finite binary tree such that each level provide the two valuations of a variable. So for $n$ boolean variables, $n$ level are needed and $2^n$ valuations are generated at the leafs. The evaluation of the formula is done at the leafs, then the tree is folded and the existence of a positive evaluation is carried forward.

This figures solves the satisfaction problem of the formula $(x_1\vee \mathrm{\neg }{x}_2)\wedge x_3$. Any SAT instance can be solves in such a way Duchier et al. (2010).

This can be modified in order that each fording node est either a disjunction (as above) or a conjunction. This way it is also possible to solve the quantified satisfaction problem (Duchier et al., 2012).

6 Related models

The model from Jacopini and Sontacchi Jacopini and Sontacchi (1990) generates/interprets finite polyhedron as space-time diagrams and computations. The model from Huckenbeck Huckenbeck (1989, 1991) uses compass and ruler as primitives. These models are presented in Durand-Lose (2016) or Becker and Durand-Lose (2015) (in French).

7 Available software

A simulator and dedicated languages has been developed to implement the various constructions and generate illustrations. This is a prototype used for research not a fully developed, tested and commented piece of software.

Although it is possible to encode everything in java (this was done for a long time), I developed a language not to made things simple and readable.

• example.agc is an simple example

  /*  To launch this example work
    java -jar agc.jar example.agc
  */
  
  
  use AGC ;   // To load AGC librairy
  
  
  signal_machine := create_signal_machine {  // create a signal machine
  
    // Define meta-signals (inside the machine)
    a := add_meta_signal ( "==" , 3 ) { color => Red ; } ;
    b := add_meta_signal ( "<<" , -3 ) ;
  
    // Define a collision rule (inside the machine)
    [ a , b ] --> [ b ] ;
  
    // Create a configuration (inside the machine)
    c := create_configuration {
      a @ -7 ;   // Add a signal at a position
      a @ -10 ;
      a @ -15 ;
      a @ -1 ;
      "<<" @ 6/3 ;
    };
  
    // Create a run
    r := c.run () ;
  
    // advance to next collision
    r.step () ;
  
    // advance by 2 collisions
    r.step ( 2 ) ;
    // Create a pdf output of the run
    r.export ( "PDF" , "./out1.pdf" ) ;
  
  } ;
  

It can be executed with the following runnable jar: DOWNLOAD. It needs java 17 or higher.

java -jar agc_2.1.jar <file.agc>

Sorry it does not come with more explanation, but the example should provide enough clues for a basic use. There is nothing special about this language and syntax and semantics are straightforward. This is a full Turing-powerful language along with loop, conditional execution, function definition…

I started writing some documentation for the specific signal machine instructions.

This comes as is with no warranty of any kind.

Feedback, comments, bug reports are welcomed.