Abstract geometrical computation: Turing-computing ability and unpredictable accumulations (extended abstract).

Jérôme Durand-Lose (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

In the Cellular Automata (CA) literature, discrete lines inside (discrete) space-time diagrams are often idealized as Euclidean lines in order to analyze a dynamics or to design CA for special purposes. In this article, we present an analog model of computation corresponding to this abstraction: dimensionless signals are moving on a continuous space in continuous time generating Euclidean lines on (continuous) space-time diagrams. Like CA, this model is parallel, synchronous, uniform in space and time, and uses local updating. The main difference is that space and time are continuous and not discrete (i.e. R instead of N). In this article, the model is restricted to Q in order to remain inside Turing-computation theory. We prove that our model can carry out any Turing-computation through two-counter automata simulation. Because of the nature of time, Zeno phenomena, i.e. accumulations, can happen. By reducing the NTOT problem (whether a recursive function is not total), we prove that forecasting any accumulation is $\Sigma^0_2$-complete in the arithmetical hierarchy, i.e. totally undecidable.

Dans la littérature des automates cellulaires (AC), les lignes discrètes apparaissant sur les diagrammes espace-temps sont souvent assimilées à des lignes du plan euclidien pour analyser une dynamique ou au contraire produire un AC particulier. Dans cet article, nous présentons un modèle de calcul ana-logique correspondant à cette abstraction : des signaux sans dimension se déplacent dans un espace continu et engendre de vraies droites sur les dia-grammes espace-temps (continus). Comme pour les AC, le modèle de calcul est parallèle, synchrone, uniforme dans le temps comme l’espace et les mises à jours se font de manière locale. La principale différence est que le temps est continu et non plus discret. Dans cet article, nous nous restreignons à valeurs rationnelles afin de rester dans le cadre de la théorie de Turing. Nous prouvons qu’il y est possible d’effectuer n’importe quel calcul au sens de Turing par la simulation d’automates `a deux compteurs. A cause de la nature continue du temps, des phénomènes de type Zénon,i.e.des accumulations, peuvent apparaître. En réduisant le problème NTOT(une fonction récursive est-elle totale ?), nous prouvons que la prévision d’une accumulation est Σ02-complète dans la hiérarchie arithmétique,i.e.totalement indécidable.

Mots clés: Abstract Geometrical Computation; Analog Model of Computation; Arithmetic Hierarchy; Cellular Automata; Geometry; Turing Universality; Zeno Phenomena

Mots clés: Phénomène type Zénon; Modèles de calcul analogiques; Hiérarchie arithmétique; Automates cellulaires; Géométrie Turing universalité

Domaines: Informatique [cs]

Jérôme Durand-Lose. Abstract geometrical computation: Turing-computing ability and unpredictable accumulations (extended abstract).. [Research Report] LIP RR-2004-09, Laboratoire de l'informatique du parallélisme. 2004, 2+11p. ⟨hal-02101865⟩