Histoire des mathématiques Concept

énumération de Gödel

Concept

fonction qui attribue à chaque symbole et formule bien-formée de certains langages formels un entier naturel unique

domaine
Logique mathématique

Son histoire

Kurt Gödel commence au début de 1930 le travail qui doit lui permettre d’obtenir un poste universitaire. Dans le monde germanique, le doctorat ne suffit pas : il faut encore une thèse d’habilitation. Son objectif est de montrer, comme le souhaite Hilbert, que les règles du calcul sur les nombres ne se contredisent pas. Il termine au début de l’automne.

L’idée centrale consiste à donner un nombre entier à chaque suite de signes utilisée dans un raisonnement. Le zéro reçoit par exemple le numéro 1, et les parenthèses les numéros 11 et 13. Une méthode d’assemblage permet ensuite de coder aussi bien les formules que les démonstrations, et de retrouver le texte à partir du code.

Ce détour transforme les affirmations sur les preuves en énoncés sur les nombres. Le système parle alors de lui-même. Une phrase affirme, en substance, qu’elle ne peut pas être démontrée.

Les deux théorèmes paraissent en mars 1931. Le projet a abouti à l’inverse du but recherché : les règles étudiées ne permettent ni de tout démontrer ni de garantir leur propre cohérence. Hilbert accueille cette nouvelle avec irritation. Son assistant Paul Bernays finit par le convaincre qu’il s’agit d’une avancée.

Ce travail vaut à Gödel un poste rémunéré à l’université. Il reçoit ensuite une invitation à l’Institute for Advanced Study de Princeton, parmi les 24 chercheurs de la première année. Deux livres popularisent le procédé : Gödel’s Proof, en 1959, puis Gödel, Escher, Bach, en 1979. Dans le second, Douglas Hofstadter emploie un code de son invention.

Sources : S. Hawking (dir.), Et Dieu créa les nombres ; Tangente hors-série n° 15, La logique ; B. Hauchecorne, Les mots et les maths ; Wikipédia, articles « Codage de Gödel » et « Gödel numbering ».

Énoncé

$$\mathrm{enc}(x_1,x_2,x_3,\dots,x_n) = 2^{x_1}\cdot 3^{x_2}\cdot 5^{x_3}\cdots p_n^{x_n}$$

Cas d’usage

  • Informatique théorique : le même codage permet, dans tout langage de programmation assez riche, d'écrire un programme universel qui simule n'importe quel autre à partir de son numéro, c'est-à-dire un interpréteur du langage écrit dans ce langage.
  • Faire parler un système formel de lui-même : chaque symbole, chaque formule et chaque suite de formules reçoit un entier unique, si bien que des énoncés sur les formules deviennent des énoncés sur les nombres.
  • Premier théorème d'incomplétude : la prouvabilité d'une formule devient une propriété arithmétique de son numéro, ce qui permet de construire la phrase qui affirme sa propre indémontrabilité.
  • Calculabilité : un programme peut énumérer tous les énoncés démontrables de l'arithmétique, sans qu'aucun programme puisse décider en un temps fini si un énoncé donné en fait partie.

Liens

porte le nom de

Sources