Pourquoi aucune machine ne pourra-t-elle jamais trancher toutes les questions des mathématiques ?

Parce que certaines questions piègent toute machine qui essaie d'y répondre. En 1928, David Hilbert et Wilhelm Ackermann ont demandé un algorithme capable de prendre n'importe quel énoncé logique et de répondre « oui » ou « non » : est-il valide ? C'était l'Entscheidungsproblem, le « problème de la décision ». En 1936, Alonzo Church et Alan Turing ont chacun prouvé qu'un tel algorithme ne peut pas exister.

C'est la voie de Turing qui est restée, parce qu'elle parle de machines. Il a montré qu'une machine parfaite à décider les maths permettrait aussi de répondre à une question en apparence plus simple : pour n'importe quel programme et ses données, va-t-il finir par s'arrêter, ou tourner pour toujours ? On l'appelle aujourd'hui le problème de l'arrêt. Puis il a montré que cette question n'a pas de réponse générale.

La preuve est un piège magnifique. Imagine qu'on te donne un programme qui prédit toujours correctement si un programme s'arrête. Construis un programme contrariant qui interroge le prédicteur à son propre sujet, puis fait l'inverse : si le prédicteur dit « tu vas t'arrêter », il boucle pour toujours ; s'il dit « tu vas boucler », il s'arrête aussitôt. Demande maintenant au prédicteur ce que fera le contrariant. Quoi qu'il réponde, il a tort. Le prédicteur parfait ne peut donc pas exister. L'astuce est cousine de l'argument diagonal de Cantor sur les infinis.

Ce fut un coup dur pour Hilbert, qui croyait encore en 1930 qu'aucun problème n'était insoluble et dont la devise était « nous devons savoir, nous saurons ». Cela ne veut pas dire qu'on ne peut jamais savoir si un programme s'arrête : les cas simples sont faciles, et de vrais outils prouvent que des programmes précis se terminent. Cela veut dire qu'aucune méthode unique ne marche dans tous les cas.