back to J. D.-L. main page

A visual introduction and software to

Abstract Geometrical Computation J. Durand-Lose , LIFO, U. D’Orléans

You just have to know that time elapses upward.

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.

This dynamics system was devised for my Habilitation à Diriger des Recherches (Durand-Lose, 2003) and is investigated since.

In 2014, these researches have been presented in the french newsstand journal Pour la Sciences (Delahaye, 2014, in French).

Contents

1 Some examples

The existing signals are instances of meta-signals. The meta-signal (speed) and rules in the first picture on the left are:

Meta-signals Identifier Speed black 0 blue, yellow 1 green 2 red -2 orange, purple -1 Collision rules In-coming Out-going { blue, black } → { black, green } { green, black } → { black, yellow } { yellow, black } → { orange, black } { black, orange } → { red, black } In-coming Out-going { black, red } → { purple , black } { black, purple } → { black, blue } { blue, black, red } → { purple , black, green } { green, black, orange } → { red, black, yellow }

This signal machine is used to generate the picture on the left.

2 Fractal generation

From a simple accumulation to the accumulation on a Cantor set

3 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.

4 Simulating a cellular automaton on ultimately periodic configurations

The side signals generates the boundary

5 Simulating a cyclic tag system

So that it is possible to be Turing universal with only 13 meta-signals (Durand-Lose, 2011a).

Cyclic tag systems were proven Turing-universal and used to prove the universality of CA rule 110 ((Cook, 2004))

One iteration of the CTS is shown as well as a full computation.

6 Basic operation to translate and to re-scale

7 Embedding an infinite diagram into shrinking structure

So that it is contained in a bounded part!

It uses above constructions infinitely iterated.

Empty structure on the left and with a diagram embedded inside on the right

8 Trying to deal with accumulations

Accumulation arise naturally as fractal are generated.

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,Durand-Lose, 2008).

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

What about 3 speeds? the answer is interesting and involves Euclid’s algorithm!

9 Forecasting an accumulation is Σ 1 0-complete

Which means as unpredictable as whether a program computes a non-total function (one jump higher than the halting problem) (Durand-Lose, 2006)

10 Fractal computation

This figures solves the satisfaction problem of the formula (x 1 ∨¬ x 2 )∧ x 3 . Any SAT instance can be solves in such a way (Duchier et al., 2010).

11 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,Huckenbeck, 1991) uses compass and ruler as primitives.

These models are presented in (Durand-Lose, 2016) (under press) or (Becker and Durand-Lose, 2015) (in French).

12 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_2_0.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 11 or higher.

java -jar agc_2_0.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.

References