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. 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. 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.