Hypercalcul

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

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[modifier | modifier le code]

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 \Omega, qui est un nombre réel aléatoire - et contient en conséquence une information infinie. \Omega 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 hypercalculateur devrait obtenir \Omega 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 \Omega à 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 du nombre \Omega à un instant donné.

Possibilités théoriques et conceptuelles d'hypercalculateurs[modifier | modifier le code]

  • 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[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 (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 spatiotemporel.

Voir aussi[modifier | modifier le code]

Notes[modifier | modifier le code]

  1. Jean-Paul Delahaye, Information, complexité et hasard, Hermès [détail de l’édition], p. 87-88
  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 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[modifier | modifier le code]

  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