Qu´a fait Gödel avec son théorème ?
Jusqu´au début du siècle les mathématiciens étaient persuadés qu´on pouvait, un peu à la manière des écoliers en géométrie, démontrer toutes les vérités mathématiques par déduction.
Gödel a démontré en 1931 deux résultats mathématiques :
Il se peut que dans certains cas, on puisse démontrer une chose et son contraire ( inconsistance).
Il existe des vérités mathématiques qu´il est impossible de démontrer ( incomplétude)
Le plus célèbre de ces résultats est le second, qu´on appelle théorème d´incomplétude de Gödel.
Quelques définitions
Système formel
Preuve
Machine de Turing
Programme informatique
Une preuve simplifiée du théorème
Malgré les performances et la diversité des ordinateurs actuels, tous ont un modèle théorique commun appelé machine de Turing. On peut donner à une machine de Turing un programme arbitrairement long, mais évidemment de taille finie, qui répond VRAI ou FAUX à une affirmation qu´on lui donne, sans jamais se tromper.
La question est:
Si un humain est capable de savoir si la phrase qu´il donne à la machine est vraie ou fausse, la machine est-elle aussi capable de découvrir la vérité ?
Gödel donne alors la phrase suivante à la machine:
" La machine ne répondra jamais VRAI à cette phrase"
Que fait la machine ?
Si elle répond VRAI, elle affirme que " La machine ne répondra jamais VRAI à cette phrase" est une affirmation vraie. Or ce n´est pas le cas, puisqu´elle vient justement de répondre VRAI à la phrase. Si la machine ne se trompe pas, elle ne peut donc pas répondre VRAI.
Si elle répond FAUX, elle affirme que " La machine ne répondra jamais VRAI à cette phrase" est une affirmation fausse. Or l´affirmation n´est pas fausse puisque la machine vient justement de répondre FAUX. Si la machine ne se trompe pas, elle ne peut donc pas répondre FAUX.
Et nous, pouvons nous répondre à la question ? ...
La phrase dit : " La machine ne répondra jamais VRAI à cette phrase". Nous venons de voir qu´en effet, la machine ne peut pas répondre VRAI. Nous savons donc que cette phrase est une vérité. Pourtant la machine ne pourra pas la découvrir...
Le théorème d´un peu plus près
