Hypercalcul

Le terme hypercalcul désigne les différentes méthodes proposées pour le calcul de fonctions non-Turing-calculables. Il a été initialement introduit par Jack Copeland. On emploie également le terme de calcul super-Turing, bien que celui d'hypercalcul puisse être connoté de la séduisante possibilité qu'une telle machine soit physiquement réalisable. Certains modèles ont été proposés, comme des réseaux de neurones avec des nombres réels en guise de poids, la capacité de conduire une infinité de calculs simultanément ou encore l'aptitude à effectuer des opérations non Turing-calculables, telles que des limites ou des intégrations.

Histoire

Un modèle plus puissant que les machines de Turing a été introduit par Alan Turing dans son article « Systems of logic based on ordinals » en 1939. Cet article examinait des systèmes mathématiques dans lesquels on dispose d'un oracle capable de calculer une unique fonction arbitraire (non récursive) des naturels vers les naturels. Il utilisa cette machine pour prouver que même dans ces systèmes plus puissants, l'indécidabilité est présente. Ce texte de Turing mit en évidence le fait que les machines oracles étaient seulement des abstractions mathématiques et ne pouvaient être physiquement réalisées.

Le défi de l'hypercalcul

Aujourd'hui, la théorie algorithmique de l'information permet de mieux comprendre ce que requiert l'hypercalcul. Outre le fait que les hypercalculateurs fassent plus que les machines de Turing, leur marque de fabrique est leur capacité à résoudre le problème de l'arrêt, pour leurs programmes, ce dont un calculateur ordinaire (une machine de Turing) est incapable. Cependant, un ordinateur peut déterminer si n'importe quel programme s'arrête ou non si on lui donne en entrée la constante Oméga de Chaitin $\Omega$ , qui est un nombre réel non calculable, qui contient la réponse au problème de l'arrêt pour chaque machine de Turing. $\Omega$ est alors un oracle pour le problème de l'arrêt. La mémorisation de cette quantité requiert une suite infinie de bits, car il n'existe aucun programme pour la calculer exhaustivement ou pour la compresser. Ainsi, un hypercalculateur doit pouvoir obtenir $\Omega$ par d'autres moyens que par un calcul au sens des machines de Turing.

Il existe une procédure d'approximation pour les calculateurs discrets (les ordinateurs ordinaires) qui permet d'approximer, approcher, $\Omega$ . Il n'est en revanche pas possible de savoir à quel point ce programme est proche du nombre $\Omega$ à un instant donné.

Possibilités théoriques et conceptuelles d'hypercalculateurs

Un ordinateur discret ayant accès à la probabilité d'arrêt $\Omega$ peut résoudre le problème de l'arrêt. Pour un programme de $n$ bits en entrée, la lecture des $n$ premiers bits du nombre $\Omega$ donne le nombre de programmes $k$ qui terminent parmi les $2^{n}$ programmes. On procède ensuite comme suit : à chaque étape $i$ , on exécute les $i$ premières instructions de chacun des $2^{n}$ programmes. On incrémente ainsi $i$ jusqu'à ce que $k$ programmes aient terminé. Il suffit de vérifier que le programme en entrée en fait partie.
Une machine de Turing capable d'effectuer une infinité d'étapes (voir supertâche).
Un ordinateur réel (une sorte de calculateur analogique idéal) pourrait effectuer des hypercalculs si la physique admettait des variables réelles au sens large (pas seulement des nombres réels calculables) et si l'on trouvait un moyen de les domestiquer pour le calcul. Cela ferait appel à des lois physiques assez déroutantes (par exemple, une constante physique mesurable avec une valeur oraculaire, comme la constante de Chaitin) et requerrait d'être capable de mesurer une valeur physique réelle avec une précision arbitraire malgré le bruit thermique et les effets quantiques.
Un système mécanique quantique qui utilise (par exemple) une superposition infinie d'états pour calculer une fonction non-calculable. Un tel système ne pourrait pas être un calculateur quantique ordinaire, car il a été prouvé que les ordinateurs quantiques sont Turing-réductibles (ils pourraient accélérer les programmes résolvant certains problèmes mais ne permettraient pas de résoudre de nouveaux problèmes).
Un calculateur numérique se trouvant dans un certain espace-temps, appelé espace-temps de Malament-Hogarth (en), pourrait accomplir une infinité d'opérations tout en restant dans le cône de lumière d'un certain évènement spatiotemporel.

Voir aussi

Notes

↑ par Hava Sigelman en particulier, Hava Siegelmann, The simple dynamics of super Turing theories; Theoretical Computer Science Volume 168, Issue 2, 20 November 1996, Pages 461-472. (link is to ScienceDirect website copy).
↑ Jean-Paul Delahaye, Information, complexité et hasard, Hermès [détail de l’édition], p. 87-88.
↑ Être simplement capable d'exécuter une infinité d'étapes (c.-à-d. ne jamais s'arrêter) ne suffit pas. En revanche, la notion de calcul à la limite fait l'affaire. Considérons à nouveau la procédure d'approximation du nombre $\Omega$ , qui converge lentement et de façon monotone. Bien que chaque terme de cette suite soit calculable, la limite $\Omega$ ne l'est pas. Si un calculateur était capable de réaliser toutes ces étapes d'approximation en nombre infini, d'obtenir $\Omega$ et de stocker son infinité de chiffres, il pourrait facilement résoudre le problème de l'arrêt.

Références

Alan Turing, Systems of logic based on ordinals, Proc. London math. soc., 45, 1939

Tien Kieu, Quantum Algorithm for the Hilbert's Tenth Problem, Int. J. Theor. Phys., 42 (2003) 1461-1478, e-print archive quant-ph/0110136 (PDF)

Boris Tsirelson (en), The quantum algorithm of Kieu does not solve the Hilbert's tenth problem. e-print archive quant-ph/0111009 (PDF)

Tien Kieu, Reply to "The quantum algorithm of Kieu does not solve the Hilbert's tenth problem". e-print archive quant-ph/0111020 (PDF)

Hava Siegelmann (en), Neural Networks and Analog Computation: Beyond the Turing Limit Boston: Birkhäuser, 1998.

Hava Siegelmann, The simple dynamics of super Turing theories; Theoretical Computer Science Volume 168, Issue 2, 20 November 1996, Pages 461-472. (link is to ScienceDirect website copy)

Keith Douglas, Super-Turing Computation: a Case Study Analysis (PDF), M.S. Thesis, Carnegie Mellon University, 2003.

Lenore Blum, Felipe Cucker, Michael Shub, Stephen Smale, Complexity and Real Computation, Springer-Verlag 1997. General development of complexity theory for abstract machines that compute on real or complex numbers instead of bits.

Thomas Natschläger et al. the "Liquid Computer": A Novel Strategy for Real-Time Computing on Time Series

http://www.nature.com/nsu/010329/010329-8.html A Nature article on the above.

« On the computational power of neural nets »^{(Archive.org • Wikiwix • Que faire ?)}

Portail de l'informatique théorique

[1] r Hava Sigelman en particulier, Hava Siegelmann, The simple dynamics of super Turing theories; Theoretical Computer Science Volume 168, Issue 2, 20 November 1996, Pages 461-472. (link is to ScienceDirect website copy).

[2] Jean-Paul Delahaye, Information, complexité et hasard, Hermès [détail de l’édition], p. 87-88.

[3] Être simplement capable d'exécuter une infinité d'étapes (c.-à-d. ne jamais s'arrêter) ne suffit pas. En revanche, la notion de calcul à la limite fait l'affaire. Considérons à nouveau la procédure d'approximation du nombre $\Omega$ , qui converge lentement et de façon monotone. Bien que chaque terme de cette suite soit calculable, la limite $\Omega$ ne l'est pas. Si un calculateur était capable de réaliser toutes ces étapes d'approximation en nombre infini, d'obtenir $\Omega$ et de stocker son infinité de chiffres, il pourrait facilement résoudre le problème de l'arrêt.