Codage de Gödel

En logique mathématique, un codage de Gödel (ou numérotation de Gödel) est une fonction qui attribue à chaque symbole et formule bien-formée de certains langages formels un entier naturel unique, appelé son code de Gödel, ou numéro de Gödel. Le concept a été utilisé par Kurt Gödel pour la preuve de ses théorèmes d'incomplétude. Un codage de Gödel peut être interprété comme un codage dans lequel un numéro est attribué à chaque symbole d'une notation mathématique, après quoi une séquence d'entiers naturels peut alors représenter une séquence de symboles. Ces séquences d'entiers peuvent encore être représentées par des entiers naturels isolés, facilitant leur manipulation dans les théories formelles de l'arithmétique. Depuis la publication de l'article de Gödel en 1931, le terme « numérotation de Gödel » ou « code de Gödel » a été utilisé pour désigner des assignations plus générales d'entiers naturels à des objets mathématiques. Gödel a noté que les déclarations dans un système peuvent être représentées par des entiers naturels. La signification de cela était que les propriétés des déclarations—telles que leur vérité et leur fausseté—équivaudraient à déterminer si leurs code de Gödel avaient certaines propriétés. Les nombres impliqués pourraient être très long (en termes de nombre de chiffres), mais ce n'est pas une barrière ; tout ce qui compte, c'est que nous pouvons montrer que ces chiffres peuvent être construits. En termes simples, nous concevons une méthode par laquelle chaque formule ou déclaration qui peut être formulée dans notre système obtient un nombre unique, de telle sorte que nous pouvons nous convertir mécaniquement entre les formules et les nombres de Gödel. De toute évidence, il existe de nombreuses façons de le faire. Compte tenu de toute déclaration, le numéro auquel il est converti est connu sous le nom de son numéro de Gödel. Un exemple simple est la façon dont les langues sont stockées comme une suite de nombres dans des ordinateurs utilisant ASCII ou Unicode : Le mot HELLO est représenté par 72-69-76-76-79 en utilisant ASCII.