Existe-t-il des problèmes que les ordinateurs ne peuvent pas résoudre ?

Information, divertissement, travail, éducation, solutions rapides à des problèmes complexes… En général, nous avons une idée assez solide de ce que nous voulons lorsque nous utilisons un ordinateur. En fait, il y a des moments où un système semble capable de tout résoudre, et cela nous mène à un exercice de logique très intéressant : imaginez un ordinateur avec un temps, une énergie et une puissance de traitement infinis. Existe-t-il quelque chose qui, malgré ces avantages, ne puisse pas être résolu ? La réponse courte est « oui », mais nous avons besoin de l'aide de Tom Scott pour le reste…

Le problème de la décision de Hilbert

Combien de fois cela s'est-il produit ? Une simple question nous plonge dans un trou noir de logique et de raison. Le mathématicien David Hilbert (le même que celui de l'hôtel infini) s'est retrouvé piégé dans cette situation avec son collègue Wilhelm Ackermann en 1928, année où ils ont présenté le défi de l'Entscheidungsproblem ou « Problème de la décision ». En termes extrêmement simplifiés, le problème pose ceci : est-il possible de déterminer si une déclaration ou une phrase donnée est démontrable ou non ? Avec le temps et l'énergie suffisants, pouvons-nous trouver la réponse à n'importe quoi ?

La machine de Turing et le problème de l'arrêt

Maintenant, quel est le rapport avec les ordinateurs ? En réalité, ce doute de Hilbert peut être adapté à l'univers informatique d'une manière très particulière : imaginez le code d'un programme, n'importe quel programme. Est-il possible d'analyser ce code et de déterminer automatiquement s'il s'arrêtera ou entrera dans une boucle infinie ? C'est à ce moment que quelqu'un suggère un exemple comme :

10 PRINT "BONJOUR LE MONDE"
20 GOTO 10
RUN

Évidemment, cette pièce de code mène à une boucle infinie... mais la différence est qu'elle a été conçue ainsi. Déterminer si certains programmes s'arrêtent ou continuent pour toujours, c'est facile. L'idée de prendre n'importe quel code, tous les codes, et de les analyser pour établir définitivement s'ils se terminent ou entrent en boucle peut sembler simple en surface, mais c'est mathématiquement impossible. Comment le savons-nous ? Grâce à un certain monsieur nommé Alan Turing, et à la fameuse Machine qui porte son nom, de l'année 1936.

L'explication de Tom Scott

C'est ici que Tom Scott nous vient en aide avec son explication : imaginons un programme baptisé « Halts » qui peut voir un échantillon de n'importe quel code et déterminer s'il s'arrête (nous n'avons pas besoin de savoir comment il le fait, l'important est qu'il fonctionne). Encore une fois : « Halts » voit le code et répond « oui » (il s'arrête) ou « non » (boucle infinie). Maintenant, visualisons un second programme connecté à « Halts », qui fait exactement le contraire de sa réponse. C'est-à-dire, si « Halts » a dit que le code s'arrête, le second programme entre dans une boucle infinie, et s'il a dit qu'il entre en boucle, il s'arrête.

Ce système est appelé « Opposé », parce qu'il fait essentiellement le contraire de ce que vous y entrez… mais c'est ici que Turing brise tout avec sa proposition : prendre le code complet qui compose « Opposé », et le faire s'analyser lui-même. Le résultat… c'est qu'il n'y a pas de résultat. C'est un paradoxe, une impossibilité mathématique. Même avec les conditions initiales idéales, une variation minimale effondre le processus. Et là se trouve notre réponse à la question initiale : il existe au moins une chose que les ordinateurs ne peuvent pas et ne pourront jamais résoudre.