Aller au contenu

Hypercalcul

Un article de Wikipédia, l'encyclopédie libre.

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[1], 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.

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. 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 leur 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 , 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. 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 par d'autres moyens que par un calcul au sens des machines de Turing.

Il existe une procédure d'approximation[2] pour les calculateurs discrets (les ordinateurs ordinaires) qui permet d'approximer, approcher, . Il n'est en revanche pas possible de savoir à quel point ce programme est proche du nombre à 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 peut résoudre le problème de l'arrêt. Pour un programme de bits en entrée, la lecture des premiers bits du nombre donne le nombre de programmes qui terminent parmi les programmes. On procède ensuite comme suit : à chaque étape , on exécute les premières instructions de chacun des programmes. On incrémente ainsi jusqu'à ce que 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[3] (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.
  1. 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).
  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 , qui converge lentement et de façon monotone. 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

[modifier | modifier le code]
  • Alan Turing, Systems of logic based on ordinals, Proc. London math. soc., 45, 1939
  • Hava Siegelmann (en), Neural Networks and Analog Computation: Beyond the Turing Limit Boston: Birkhäuser, 1998.