Melvin Henriksen–professeur de mathématiques émérite au Harvey Mudd College–offre cette explication :
Donner un énoncé mathématiquement précis du théorème d’incomplétude de Godel ne ferait qu’occulter son important contenu intuitif à presque tous ceux qui ne sont pas des spécialistes de la logique mathématique. Je vais donc, à la place, le reformuler et le simplifier dans le langage des ordinateurs.
Imaginez que nous ayons accès à un ordinateur très puissant appelé Oracle. Comme les ordinateurs avec lesquels nous sommes familiers, Oracle demande que l’utilisateur « entre » des instructions qui suivent des règles précises et il fournit la « sortie » ou la réponse d’une manière qui suit également ces règles. La même entrée produira toujours la même sortie. L’entrée et la sortie sont écrites sous forme d’entiers (ou de nombres entiers) et Oracle n’effectue que les opérations habituelles d’addition, de soustraction, de multiplication et de division (lorsque cela est possible). Contrairement aux ordinateurs ordinaires, il n’y a aucun souci d’efficacité ou de temps. Oracle exécute des instructions correctement données, quel que soit le temps nécessaire, et il ne s’arrête que lorsqu’elles sont exécutées – même si cela prend plus d’un million d’années.
Prenons un exemple simple. Rappelez-vous qu’un nombre entier positif (appelons-le N) supérieur à 1 est appelé nombre premier s’il n’est divisible par aucun nombre entier positif autre que 1 et N. Comment demanderiez-vous à Oracle de décider si N est premier ? Dites-lui de diviser N par chaque nombre entier compris entre 1 et N-1 et de s’arrêter lorsque la division est égale ou qu’elle atteint N-1. (En fait, vous pouvez vous arrêter s’il atteint la racine carrée de N. S’il n’y a pas eu de divisions paires de N à ce moment-là, alors N est premier.)
Ce que dit le théorème de Godel, c’est qu’il existe des questions correctement posées impliquant uniquement l’arithmétique des nombres entiers auxquelles Oracle ne peut pas répondre. En d’autres termes, il existe des affirmations que – bien que saisies correctement – Oracle ne peut pas évaluer pour décider si elles sont vraies ou fausses. De telles assertions sont dites indécidables, et sont très compliquées. Et si vous en apportiez une au Dr Godel, il vous expliquerait que de telles assertions existeront toujours.
Même si on vous donnait un modèle « amélioré » d’Oracle, appelé OracleT, dans lequel une affirmation indécidable particulière, UD, est décrétée vraie, une autre affirmation indécidable serait générée pour prendre sa place. Plus déroutant encore, on pourrait aussi vous donner un autre modèle « amélioré » d’Oracle, appelé OracleF, dans lequel UD serait décrété faux. Quoi qu’il en soit, ce modèle aussi générerait d’autres énoncés indécidables, et pourrait donner des résultats différents de ceux d’OracleT, mais tout aussi valables.
Ne trouvez-vous pas cela choquant et proche du paradoxe ? C’était encore plus choquant pour le monde mathématique en 1931, lorsque Godel a dévoilé son théorème d’incomplétude. Godel n’a pas formulé son résultat dans le langage des ordinateurs. Il travaillait dans un système logique bien défini et les mathématiciens espéraient que son résultat dépendait des particularités de ce système. Mais au cours de la décennie suivante, un certain nombre de mathématiciens – dont Stephen C. Kleene, Emil Post, J.B. Rosser et Alan Turing – ont montré que ce n’était pas le cas.
La recherche sur les conséquences de ce grand théorème se poursuit encore aujourd’hui. Toute personne ayant accès à Internet et utilisant un moteur de recherche comme Alta Vista peut trouver plusieurs centaines d’articles de qualité très variable sur le théorème de Godel. Parmi les meilleures choses à lire, cependant, se trouve Godel’s Proof d’Ernest Nagel et James R. Newman, publié en 1958 et édité en livre de poche par les Presses universitaires de New York en 1983.