Hypercalcul

Le terme hypercalcul désigne les différentes méthodes proposées pour le calcul de fonction 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. La marque de fabrique d'un hypercalculateur est sa capacité à résoudre le problème de l'arrêt, ce dont un ordinateur ordinaire est incapable. Cependant, un ordinateur normal peut calculer le prédicat de l'arrêt de n'importe quel programme étant donnée la probabilité d’arrêt Ω, qui est un nombre réel aléatoire - et contient en conséquence une information infinie. Ω est donc un oracle pour le programme de l'arrêt. La représentation de cette quantité requiert un nombre infini de bits sur quelque médium que ce soit (elle est incompressible par essence), et il n'existe aucune procédure de décision pour la calculer. Cependant, un hypercalculteur devrait obtenir Ω par d'autres moyens que le calcul Turing-complet.

Il existe une procédure d'approximation^[1] pour les calculateurs discrets (les ordinateurs ordinaires) qui permet d'approximer Ω à l'aide d'un simple programme de partage du temps. Il n'est en revanche pas possible de savoir à quel point ce programme est proche d'Ω à un instant donné.

Possibilités théoriques et conceptuelles d'hypercalculateurs

• Un ordinateur discret ayant accès à la probabilité d'arrêt Ω 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 d'Ω donne le nombre de programmes k qui terminent parmi les 2ⁿ programmes. On procède ensuite comme suit : à chaque étape i, on exécute les i premières instructions de chacun des 2ⁿ 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^[2] (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 (et 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, pourrait accomplir une infinité d'opérations tout en restant dans le cône de lumière d'un certain évènement spatio-temporel.

Voir aussi

• Thèse de Church-Turing
• Oracle (machine de Turing)

Notes

1. ↑ J. P. Delahaye, Information complexité et Hasard, p. 87-88, ser. Langue Raisonnement Calcul 2^e éd. Hermès science publications Paris, 1999.
2. ↑ Ê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 d'Ω, qui converge lentement et monotoniquement. Bien que chaque terme de cette suite soit calculable, la limite Ω ne l'est pas. Si un calculateur était capable de réaliser toutes ces étapes d'approximation en nombre infini, d'obtenir Ω et de stocker son infinité de chiffres, il pourrait facilement résoudre le problème de l'arrêt.

Références

1. Alan Turing, Systems of logic based on ordinals, Proc. London math. soc., 45, 1939
2. 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)
3. Boris Tsirelson. The quantum algorithm of Kieu does not solve the Hilbert's tenth problem. e-print archive quant-ph/0111009 (PDF)
4. Tien Kieu, Reply to "The quantum algorithm of Kieu does not solve the Hilbert's tenth problem". e-print archive quant-ph/0111020 (PDF)
5. Hava Siegelman. Neural Networks and Analog Computation: Beyond the Turing Limit Boston: Birkhäuser.
6. 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)
7. Keith Douglas. Super-Turing Computation: a Case Study Analysis (PDF), M.S. Thesis, Carnegie Mellon University, 2003.
8. L. Blum, F. Cucker, M. Shub, S. 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.
9. Thomas Natschläger et al. the "Liquid Computer": A Novel Strategy for Real-Time Computing on Time Series
10. http://www.nature.com/nsu/010329/010329-8.html A Nature article on the above.
11. On the computational power of neural nets