Hypercalcul

Pour fonctionner correctement, certains calculs effectués par les machines ci-dessous nécessitent littéralement un espace physique et des ressources infinis, et non simplement illimités mais finis ; en revanche, avec une machine de Turing, tout calcul donné qui s'arrête ne nécessitera qu'un espace physique et des ressources finis.

Une machine de Turing capable d'effectuer une infinité d'étapes en un temps fini, un exploit connu sous le nom de supertâche , est une machine de Turing . Pouvoir exécuter un nombre illimité d'étapes ne suffit pas. Un modèle mathématique est la machine de Zénon (inspirée du paradoxe de Zénon ). La machine de Zénon effectue sa première étape de calcul en (par exemple) 1 minute, la deuxième en ½ minute, la troisième en ¼ minute, etc. En sommant 1 + ½ + ¼ + ... (une série géométrique ), on constate que la machine effectue une infinité d'étapes en un total de 2 minutes. Selon Oron Shagrir , les machines de Zénon introduisent des paradoxes physiques et leur état est logiquement indéfini en dehors d'une période ouverte unilatérale de [0, 2), donc indéfini précisément 2 minutes après le début du calcul.

Il semble naturel que la possibilité du voyage dans le temps (existence de courbes temporelles fermées , ou CTC) rende l'hypercalcul possible en soi. Cependant, ce n'est pas le cas, car une CTC ne fournit pas (à elle seule) la quantité illimitée de stockage requise par un calcul infini. Néanmoins, il existe des espaces-temps dans lesquels la région des CTC peut être utilisée pour l'hypercalcul relativiste. Selon un article de 1992, un ordinateur fonctionnant dans un espace-temps de Malament-Hogarth ou en orbite autour d'un trou noir en rotation pourrait théoriquement effectuer des calculs non-Turing pour un observateur situé à l'intérieur du trou noir. L'accès à une CTC pourrait permettre la résolution rapide de problèmes PSPACE-complets , une classe de complexité qui, bien que décidable par une machine de Turing, est généralement considérée comme insoluble en pratique.

Certains chercheurs supposent qu'un système quantique utilisant une superposition infinie d'états pourrait calculer une fonction non calculable . Ceci est impossible avec un ordinateur quantique standard basé sur le modèle des qubits , car il est démontré qu'un ordinateur quantique classique est PSPACE - réductible (un ordinateur quantique fonctionnant en temps polynomial peut être simulé par un ordinateur classique fonctionnant en espace polynomial ).

Certains systèmes physiquement réalisables convergeront toujours finalement vers la bonne réponse, mais présentent le défaut de produire souvent une réponse incorrecte et de s'y tenir pendant une période incalculable avant de finalement revenir en arrière et de corriger l'erreur.

Au milieu des années 1960, E. Mark Gold et Hilary Putnam ont proposé indépendamment des modèles d' inférence inductive ( respectivement les « fonctionnelles récursives limites » et les « prédicats par essais et erreurs » ). Ces modèles permettent d'« apprendre à la limite » certains ensembles non récursifs de nombres ou de langages (y compris tous les ensembles de langages récursivement énumérables ) ; or, par définition, seules les ensembles récursifs de nombres ou de langages peuvent être identifiés par une machine de Turing. Bien que la machine converge vers la réponse correcte pour tout ensemble apprenable en un temps fini, elle ne peut l'identifier comme correcte que si elle est récursive ; sinon, la correction n'est établie qu'en faisant tourner la machine indéfiniment et en constatant qu'elle ne modifie jamais sa réponse. Putnam a identifié cette nouvelle interprétation comme la classe des prédicats « empiriques », déclarant : « Si nous supposons toujours que la réponse la plus récente est correcte, nous commettrons un nombre fini d’erreurs, mais nous finirons par obtenir la bonne réponse. (Notez cependant que même si nous avons atteint la bonne réponse (la fin de la séquence finie), nous ne sommes jamais certains de l’avoir obtenue.) » arithmétique . Schubert écrit : « Intuitivement, l’identification limite itérée peut être considérée comme une inférence inductive d’ordre supérieur réalisée collectivement par une communauté toujours croissante de machines d’inférence inductive d’ordre inférieur. »

Une séquence de symboles est calculable à la limite s'il existe un programme fini, éventuellement non bloquant, exécuté sur une machine de Turing universelle, qui produit incrémentalement chaque symbole de la séquence. Ceci inclut le développement dyadique de π et de tout autre réel calculable , mais exclut toujours les réels non calculables. Les « machines de Turing monotones » traditionnellement utilisées en théorie de la taille des descriptions ne peuvent pas modifier leurs sorties précédentes ; les machines de Turing généralisées, telles que définies par Jürgen Schmidhuber , le peuvent. Il définit les séquences de symboles descriptibles de manière constructive comme celles pour lesquelles il existe un programme fini non bloquant exécuté sur une machine de Turing généralisée, tel que tout symbole de sortie converge finalement ; c'est-à-dire qu'il ne change plus après un certain intervalle de temps initial fini. En raison des limitations mises en évidence pour la première fois par Kurt Gödel (1931), il peut être impossible de prédire le temps de convergence lui-même par un programme bloquant ; autrement, le problème de l'arrêt pourrait être résolu. Schmidhuber ( ) utilise cette approche pour définir l'ensemble des univers formellement descriptibles ou calculables de manière constructive, ou encore les théories constructives du tout . Les machines de Turing généralisées peuvent finalement converger vers une solution correcte du problème de l'arrêt en évaluant une suite de Specker .