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

Abstract : 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.
Document type :
Reports
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101865
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:08:31 AM
Last modification on : Sunday, May 19, 2019 - 1:20:43 AM

File

RR2004-09.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101865, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

2

Files downloads

7