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
IdentifierSpeed
black0
blue, yellow1
green2
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 Σ10-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 (x1∨¬ x2)∧ x3. 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

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:

Sorry it does not come with more explaination, but the example should provide enough clues for a basic use. There is a full Turing-powerful 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 Durand-Lose, 2015]
Becker, F. and Durand-Lose, 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: NP-Completeness, 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., Durand-Lose, 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.
[Durand-Lose, 2003]
Durand-Lose, J. (2003). Calculer géométriquement sur le plan – machines à signaux. Habilitation à Diriger des Recherches, École Doctorale STIC, Université de Nice-Sophia Antipolis. In French.
[Durand-Lose, 2006]
Durand-Lose, 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.
[Durand-Lose, 2007]
Durand-Lose, 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.
[Durand-Lose, 2008]
Durand-Lose, 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.
[Durand-Lose, 2011a]
Durand-Lose, J. (2011a). Abstract geometrical computation 4: Small Turing universal signal machines. Theoret Comp Sci, 412:57–67.
[Durand-Lose, 2011b]
Durand-Lose, J. (2011b). Abstract geometrical computation 5: embedding computable analysis. Nat Comput, 10(4):1261–1273. Special issue on Unconv. Comp. ’09.
[Durand-Lose, 2016]
Durand-Lose, 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 space-model. 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 LATEX by HEVEA.