Abstract geometrical computation for Black hole computation (extended abstract)

Jérôme Durand-Lose (1)

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

The Black hole model of computation provides a computing power that goes beyond the classical Turing computability since it offers the possibility to decide in finite time any recursively enumerable (\RE) problem. In this article, we provide a geometric model of computation, conservative abstract geometrical computation, that has the same property: it can simulate any Turing machine and can decide any \RE problem through the creation of an accumulation. Finitely many signals can leave any accumulation, and it can be known whether anything leaves. This corresponds to a black hole artifact.

Le modèle du calcul avec un trou noir fournit une puissance de calcul supérieure au calcul Turing classique puisqu'on peut y décider tout problème récursivement énumérable(R.E.). Dans cet article, nous proposons un modèle de calcul géométrique,conservative abstract geometrical computation,qui a la même propriété : il peut simuler n'importe quelle machine de Turing et, en créant une accumulation,décider n'importe quel problème R.E.Seulement un nombre fini de signaux peuvent quitter l'accumulation et il est possible de savoir si quoique ce soit l'a quitté. Ceci correspond à l'artefact du trou noir.

Mots clés: Abstract geometrical computation; Black hole model; Energy conservation; Malament-Hogarth space-times; Turing universality; Zeno phenomena

Domaines: Informatique [cs]

Jérôme Durand-Lose. Abstract geometrical computation for Black hole computation (extended abstract). [Research Report] LIP RR-2004-15, Laboratoire de l'informatique du parallélisme. 2004, 2+11p. ⟨hal-02101791⟩