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

Système d'archivage DSpace/Manakin

Voir la notice simple

dc.contributor.author Laboratoire de l'informatique du parallélisme en_US
dc.contributor.author Durand-Lose, Jérôme en_US
dc.date.accessioned 2007-03-06T14:16:59Z
dc.date.available 2007-03-06T14:16:59Z
dc.date.issued 2004-03 en_US
dc.identifier.other LIP-RR - 2004-09 en_US
dc.identifier.uri http://hdl.handle.net/2332/1001
dc.description.abstract (eng) 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. en_US
dc.format.extent 2+11p en_US
dc.format.extent 235220 bytes
dc.format.extent 23 bytes
dc.format.mimetype application/pdf
dc.format.mimetype application/octet-stream
dc.language.iso eng en_US
dc.rights http://lara.inist.fr/utilisation.jsp en_US
dc.source.uri http://www.ens-lyon.fr/LIP/Pub/Rapports/RR/RR2004/RR2004-09.ps.gz en_US
dc.subject Abstract Geometrical Computation en_US
dc.subject Analog Model of Computation en
dc.subject Arithmetic Hierarchy en
dc.subject Cellular Automata en
dc.subject Turing Universality en
dc.subject Zeno Phenomena en
dc.subject Geometry en
dc.title Abstract geometrical computation: Turing-computing ability and unpredictable accumulations (extended abstract). en_US
dc.type Research report en_US

Fichiers dans ce document

Dans la(les) collection(s)

Voir la notice simple


Recherche avancée


Mon compte

Bookmark and Share