A visual introduction 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... you have to guess their fabric!

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

Contents

1  Some examples

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

meta-signalspeed
black0
blue, yellow1
green2
red-2
orange, purple-1
{ blue, black } → { black, green }
{ green, black } → { black, yellow }
{ yellow, black } → { orange, black }
{ black, orange } → { red, black }
{ black, red } → { purple , black }
{ black, purple } → { black, blue }

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, 2011).

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, 2010) 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).

References

[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.
[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. Symposium 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, S. B., 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, S. B., Löwe, B., and Sorbi, A., editors, Computation and Logic in the Real World, 3rd Conf. Computability in Europe (CiE ’07), 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, 2010]
Durand-Lose, J. (2010). Abstract geometrical computation 5: embedding computable analysis. Nat. Comput., in press. special issue on Unconv. Comp. ’09.
[Durand-Lose, 2011]
Durand-Lose, J. (2011). Abstract geometrical computation 4: small Turing universal signal machines. Theoret. Comp. Sci., 412:57–67.
[Weihrauch, 2000]
Weihrauch, K. (2000). Introduction to computable analysis. Texts in Theoretical computer science. Springer, Berlin.
This document was translated from LATEX by HEVEA.