back to J. D.L. main page
A visual introduction and software to
Abstract Geometrical ComputationJ. DurandLose, LIFO, U. D’Orléans 
You just have to know that time elapses upward.
The pictures are orbits or spacetime diagrams of a special kind of dynamical systems called signal machines.
In a onedimensional 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 (DurandLose, 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 metasignals.
The metasignal (speed) and rules in the first picture on the left are:
Metasignals
Identifier  Speed 
black  0 
blue, yellow  1 
green  2 
red  2 
orange, purple  1



 Collision rules 
Incoming   Outgoing 
{ blue, black }  →  { black, green } 
{ green, black }  →  { black, yellow } 
{ yellow, black }  →  { orange, black } 
{ black, orange }  →  { red, black }

 Incoming   Outgoing 
{ 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 2counter automaton
This is one way to achieve Turinguniversality, 2counter 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 metasignals (DurandLose, 2011a).
Cyclic tag systems were proven Turinguniversal 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 rescale
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,DurandLose, 2011b) and also of the semialgebraic approach of Blum, Shub and Smale (Blum et al., 1989,DurandLose, 2007,DurandLose, 2008).
As displayed, 4 speeds are enough to generate an accumulation.
With 2 speeds (regardless of the number of metasignals) 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 nontotal function (one jump higher than the halting problem)
(DurandLose, 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 spacetime diagrams and computations.
The model from Huckenbeck (Huckenbeck, 1989,Huckenbeck, 1991) uses compass and ruler as primitives.
These models are presented in (DurandLose, 2016) (under press) or (Becker and DurandLose, 2015) (in French).
12 Available software
This come as is no warranty of any kind.
This is prototype used for research no a fully developped, tested and commented piece of software.
Nevertheless feedback, comments, bug reports are welcomed.
DOWNLOAD big jar containing other jar (antlr itext).
There should be some doc (javadoc generated) inside.
I recently added a language (yet undocummented) not have to hardcode into java:

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 := sm { // create a signal machine
// Define metasignals (inside the machine)
a := ms ( "==" , 3 ) { color =>Red ; } ;
b := ms ( "<<" , 3 ) ;
// Define a collision rule (inside the machine)
[ a , b ] > [ b ] ;
// Create a configuration (inside the machine)
c := conf {
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" ) ;
} ;
Sorry it does not come with more explaination, but the example should provide enough clues for a basic use.
There is a full Turingpowerful language along with loop, conditional execution, function definition... which is even less documented (not to say correct and stable).
Please forward me any bug with the language.
References

[Becker and DurandLose, 2015]

Becker, F. and DurandLose, J. (2015).
Construire et calculer dans un monde 2D.
In Ollinger, N., editor, Informatique Mathématique — une
photographie en 2015, pages 135–177. CNRS édition.
 [Blum et al., 1989]

Blum, L., Shub, M., and Smale, S. (1989).
On a Theory of Computation and Complexity over the Real
Numbers: NPCompleteness, Recursive Functions and
Universal Machines.
Bull Amer Math Soc, 21(1):1–46.
 [Cook, 2004]

Cook, M. (2004).
Universality in elementary cellular automata.
Complex Systems, 15:1–40.
 [Delahaye, 2014]

Delahaye, J.P. (2014).
Une théorie rêvée du calcul.
Pour la Science, 437:90–96.
in French.
 [Duchier et al., 2010]

Duchier, D., DurandLose, J., and Senot, M. (2010).
Fractal parallelism: Solving SAT in bounded space and time.
In Otfried, C., Chwa, K.Y., and Park, K., editors, Int. Symp.
on Algorithms and Computation (ISAAC ’10), number 6506 in LNCS, pages
279–290. Springer.
 [DurandLose, 2003]

DurandLose, J. (2003).
Calculer géométriquement sur le plan – machines à
signaux.
Habilitation à Diriger des Recherches, École Doctorale
STIC, Université de NiceSophia Antipolis.
In French.
 [DurandLose, 2006]

DurandLose, J. (2006).
Forcasting black holes in abstract geometrical computation is highly
unpredictable.
In Cai, J.Y., Cooper, B. S., and Li, A., editors, Theory and
Applications of Models of Computations (TAMC ’06), number 3959 in LNCS,
pages 644–653. Springer.
 [DurandLose, 2007]

DurandLose, J. (2007).
Abstract Geometrical Computation and the Linear Blum, Shub
and Smale Model.
In Cooper, B. S., Löwe, B., and Sorbi, A., editors, Computation and Logic in the Real World, 3rd Conf. Computability in Europe
(CiE 2007), number 4497 in LNCS, pages 238–247. Springer.
 [DurandLose, 2008]

DurandLose, J. (2008).
Abstract geometrical computation with accumulations: Beyond
the Blum, Shub and Smale model.
In Beckmann, A., Dimitracopoulos, C., and Löwe, B., editors, Logic and Theory of Algorithms, 4th Conf. Computability in Europe (CiE ’08)
(abstracts and extended abstracts of unpublished papers), pages 107–116.
University of Athens.
 [DurandLose, 2011a]

DurandLose, J. (2011a).
Abstract geometrical computation 4: Small Turing universal
signal machines.
Theoret Comp Sci, 412:57–67.
 [DurandLose, 2011b]

DurandLose, J. (2011b).
Abstract geometrical computation 5: embedding computable
analysis.
Nat Comput, 10(4):1261–1273.
Special issue on Unconv. Comp. ’09.
 [DurandLose, 2016]

DurandLose, J. (2016).
Computing in Perfect Euclidean Frameworks.
In Adamatzky, A., editor, Advances in Unconventional
Computing, volume 1: Theory, pages 141–163. Springer.
 [Huckenbeck, 1989]

Huckenbeck, U. (1989).
Euclidian geometry in terms of automata theory.
Theoret Comp Sci, 68(1):71–87.
 [Huckenbeck, 1991]

Huckenbeck, U. (1991).
A result about the power of geometric oracle machines.
Theoret Comp Sci, 88(2):231–251.
 [Jacopini and Sontacchi, 1990]

Jacopini, G. and Sontacchi, G. (1990).
Reversible parallel computation: an evolving spacemodel.
Theoret Comp Sci, 73(1):1–46.
 [Weihrauch, 2000]

Weihrauch, K. (2000).
Introduction to computable analysis.
Texts in Theoretical computer science. Springer, Berlin.
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.