La thèse de Church-Turing dit en substance que n'importe quelle fonction que l'on considère comme calculable peut être calculée par une machine de Turing. Les ordinateurs que nous rencontrons tous les jours sont exactement aussi puissants qu'une machine de Turing universelle, ni plus, ni moins. Nous savons qu'il existe des fonctions qui ne sont pas calculables par une machine de Turing. Le problème le plus courrament utilisé pour illustrer ce fait est le problème d'arrêt : est-il possible de décider si une machine de Turing à laquelle on donne des données va s'arrêter, ou bien va boucler infiniment ? La manière intuitive de faire cela échoue : on peut faire tourner la machine pendant 10 minutes, et si elle s'arrête on répond oui. Mais si elle ne s'est pas arrêtée au bout de dix minutes, rien ne nous permet de conclure qu'elle ne va pas s'arrêter dans les minutes suivantes.
On peut prouver assez facilement qu'il est impossible de faire un programme exécuté sur une machine de Turing qui puisse décider si un programme quelconque se termine. L'idée générale consiste à supposer qu'un tel programme P existe, c'est à dire que P(A) dit oui si A se termine, et non si A boucle. Ensuite, on construit un programme Q(A) qui dit oui si A boucle (si P(A) répond non), et boucle si A se termine (si P(A) répond oui). Lorsqu'on applique Q à lui même, Q(Q), il répond oui si Q ne se termine pas, et ne se termine pas si Q se termine. C'est absurde, et donc on doit conclure que Q n'existe pas. La seule difficulté pour construire Q est de construire P, donc P n'existe pas. Nous sommes donc en présence d'un problème de décision non calculable. Existe-t-il un moyen de s'en sortir ?
Des théoriciens ont défini des machines de Zénon, aussi connues sous le nom de machines de Turing accélérées. Leur nom s'inspire des réflexions du philosophe Zénon, dont j'ai déjà parlé ici. Une machine de Zénon est une machine de Turing qui met une demi-minute à faire sa première étape de calcul, puis un quart de minute à faire la seconde, un huitième pour la troisième, etc. Comme elle calcule de plus en plus vite, et que la somme (ifinie) des délais nécessaires à chaque étape tend vers un, au bout d'une minute elle aura effectué un nombre infini de calculs. Par conséquent, on peut définir une machine de Zénon qui possède une valeur particulière X commençant à 0, à qui on donne un programme P, et qui doit écrire 1 dans X si jamais P se termine. Au bout d'une minute, on observe X. Si X=1, c'est que P s'est terminé. Si X=0, c'est que P ne s'arrête jamais.
Les machines de Zénon ont deux défaut. Le premier défaut est qu'elles semblent être uniquement du domaine de l'idée ; intuitivement, on imagine mal une machine qui accélère infiniment. Toutefois, des solutions physiques ont été proposées, qui seraient théoriquement possibles si certaines hypothèses sont vérifiées. Une des solutions consiste à lancer la machine dans un trou noir. Du point de vue d'un observateur externe, la machine effectue ses calculs de plus en plus vite, et au moment où elle est absorbée par le trou noir, elle a effectué un nombre infini de calculs. Je vous passe les détails, mais parmis les hypothèses douteuses, nous avons besoin d'une source d'énergie infinie, et nous avons besoin que le temps soit infiniment divisible.
Le deuxième défaut est qu'elles peuvent produire des incongruités. En effet, si on imagine une machine de Zénon qui fait X=1, X=0, X=1, X=0... alors quelle sera la valeur de X au bout d'un nombre infini d'itérations ? Est-ce un signe que les machines de Zénon sont impossibles, et cela peut-il nous révéler quelque chose concernant les solutions physiques dont j'ai parlé plus haut ?
À lire aussi sur la question, un article de Jean-Paul Delahaye dans le numéro 312 de Pour la Science.