88] Logique et calcul
© Pour la Science - n° 375 - Janvier 2009
88] Logique et calcul
L
’incomplétude est l’incapacité,
découverte et démontrée par
Kurt Gödel, de concevoir un
système mathématique qui
capte toutes les vérités ma-
thématiques. Le hasard est l’incapacité, que
chacun a expérimentée, de prévoir ce qui
va arriver. Quels sont les liens entre ces deux
concepts centraux de la philosophie et de la
science moderne ?
À cette question, les logiciens proposent
aujourd’hui trois faisceaux de réponses. Cha-
cun d’eux suggère des idées en opposition
avec la conception traditionnelle des mathé-
matiques comme science dont les connais-
sances s’acquièrent par la démonstration.
Raisonnable,
donc troué !
Découvert en 1930, le théorème d’incom-
plétude de Gödel affirme qu’en définissant
de façon raisonnable ce que sont les preuves
mathématiques, alors certaines vérités
mathématiques échappent nécessairement
à ces preuves.
Le mot « raisonnable » correspond à
trois exigences. Dabord, on ne souhaite pas
que les preuves conduisent à démontrer des
affirmations contradictoires. Ensuite, on veut
que les preuves permettent de démontrer
les énoncés élémentaires vrais de l’arith-
métique, par exemple que 25 est un carré,
ou qu’il existe une infinité de nombres pre-
miers. Enfin, si quelqu’un utilise cette défi-
nition des preuves pour démontrer un
théorème, on exige que la preuve soit véri-
fiable sans risque d’erreur et d’une manière
automatique. Ainsi, « raisonnable » pour un
système de preuves signifie consistant, per-
mettant de mener les raisonnements d’arith-
métique élémentaire et mécanisable.
L’incomplétude démontrée par Gödel
est avant tout une déception: elle affirme
qu’avec une notion raisonnable de preuve
mathématique, certaines vérités mathé-
matiques ne pourront pas être prouvées :
tout système raisonnable de preuves pos-
sède des trous. À y regarder de près, l’in-
complétude de Gödel affirme un peu plus
que la présence d’un trou dans tout sys-
tème de preuves imaginables, elle affirme
une «incomplétabilité».
Le premier lien entre l’incomplétude et
les probabilités que nous mentionnons pré-
cise justement cette « incomplétabilité ». Une
conséquence directe du théorème de Gödel
est qu’en ajoutant des vérités comme axiomes
à l’aide d’un algorithme – qui éventuellement
en ajoute progressivement une infinité –
jamais on ne complète vraiment. Même après
l’ajout, par un algorithme, d’une infinité
d’axiomes à un système de preuves incom-
plet, le nouveau système de preuves obtenu,
bien que plus complet, ne le sera pas totale-
ment : il existera encore des énoncés mathé-
matiques vrais qui ne seront pas démontrables
avec la notion élargie de preuves.
Que se passe-t-il si l’on ajoute des axiomes
au système que l’on veut compléter en uti-
lisant le hasard ? Le hasard permettrait-il
de compléter totalement ? Concrètement,
l’idée est d’utiliser des algorithmes probabi-
listes, c’est-à-dire des procédés de calcul qui,
de temps en temps, décident de l’opération
à effectuer en tirant au hasard un bit 0 ou 1,
en lançant une pièce de monnaie par exemple.
La réponse à cette question subtile a
été brillamment élucidée par Leonid Levin
(c’était le sujet de cette rubrique en
mai 2007). L. Levin a montré que même
en utilisant un algorithme probabiliste, on
ne réussit jamais à compléter un système
raisonnable de preuves. C’est notre première
leçon sur les rapports du hasard et de l’in-
complétude : le hasard ne permet pas de
boucher le trou de l’incomplétude.
Le hasard n’aidera pas
à compléter
Dans l’esprit de L. Levin, ce résultat d’in-
complétabilité possède une forme éten-
due. Pour lui, aucun système physique (même
s’il fonctionne durant un temps infini) ne
pourra compléter un système raisonnable
de preuves : soit il donnera des contradic-
tions, soit il laissera des trous. L. Levin conjec-
ture un principe d’indépendance entre la
physique et le monde mathématique s’ap-
puyant sur une loi de conservation de l’in-
formation : aucun procé physique ne
crée de l’information avec suffisamment d’ef-
ficacité pour compléter un système incom-
plet. Pour lui, cette loi est aussi fondamentale
que d’autres lois de conservation de la phy-
sique. Les arguments de L. Levin sont irré-
futables dans le cas des algorithmes
probabilistes, car ce sont des démonstra-
tions mathématiques ; dans le cas plus géné-
ral des procédés physiques quelconques,
Presque tout est indécidable !
Grâce aux notions probabilistes, les logiciens démontrent
que l’incomplétude de Gödel est beaucoup plus grave
et incontournable que tout ce que l’on pouvait craindre.
Jean-Paul DELAHAYE
Kurt Gödel (1906-1978)
REGARDS
LOGIQUE & CALCUL
Mathématiques
(c)2007 Charles F. Cooper Used with permission
pls_375_p000_000_delahaye.qxd_ata_02_12.qxd 8/12/08 15:49 Page 88