Godel number

A Godel number is a natural number that is assigned to a word in a formal language using a certain procedure and that uniquely identifies this word . Such a process is called Gödelization . The names refer to Kurt Gödel , who was the first to use such a method to prove his incompleteness theorem .

Formal definition

Let be the ( countable ) set of words in a formal language . One function ${\displaystyle M}$ ${\displaystyle m}$

${\displaystyle g\colon M\to \mathbb {N} }$

is called Godelization if

• ${\displaystyle g}$ injective and predictable ,
• the amount of images decidable as well ${\displaystyle g(M)}$
• which can be calculated on the defined inverse function of . ${\displaystyle g(M)}$ ${\displaystyle g}$

${\displaystyle g(m)}$is then called the Gödel number of . ${\displaystyle m}$

example

Suppose any words of the formal language that are based on the alphabet are to be godelized. Be here . ${\displaystyle L}$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma =\{a,b,c\}}$

One way of coding would be to simply assign consecutive numbers to the letters first. An a would correspond to 1, a b to 2 and a c to 3. Now you can godelize by multiplying the powers of the consecutive prime numbers corresponding to the letter : ${\displaystyle 2,3,5,7,\ldots }$

The word abccba

• The a in the first place has the value ${\displaystyle 2^{1}=2}$
• The second b has the value ${\displaystyle 3^{2}=9}$
• The third c has the value ${\displaystyle 5^{3}=125}$
• The fourth c has the value ${\displaystyle 7^{3}=343}$
• The fifth b has the value ${\displaystyle 11^{2}=121}$
• The a in the sixth position has the value ${\displaystyle 13^{1}=13}$

The Gödel number for abccba in this coding is ${\displaystyle 2\cdot 9\cdot 125\cdot 343\cdot 121\cdot 13=1\,213\,962\,750}$

Since there are an infinite number of prime numbers, words of any length can actually be coded in this way and, due to the uniqueness of the prime factorization, the word abccba can be reconstructed from the number 1213962750 . There are numbers that do not correspond to any word in the language, for example (no first letter) or (alphabet has no fourth element). But at least these invalid values ​​can be distinguished from the valid ones in a calculable way. ${\displaystyle 3=2^{0}\cdot 3^{1}}$ ${\displaystyle 16=2^{4}}$ ${\displaystyle \Sigma }$

In addition to the one shown here, there are of course other methods of gödelization. For example, the sequence of prime numbers could also be used to number the characters of the alphabet. In principle, this is not necessary, but it also allows the structure of terms (formulas) to be coded.

For example, a method described in the book Gödel, Escher, Bach by Douglas Hofstadter uses a place value system with the base 1000, which is very clear, but formally more difficult to handle than a method that is based on prime powers like the one above. This is especially true for the encodings used in IT - such as Unicode encodings such as UTF-7 , which can also be used to map the special characters. These assign a sequence of hexadecimal or binary digits to a string , which can be viewed as a whole as a Godel number (the zero byte usually means the end of the representation string , so there should be no uniqueness problems due to leading zeros - otherwise a binary 1 are prefixed). The reconstruction of the character string from this number representation is given due to the required technical functionality.

Godelization of number theoretic statements

Statements of number theory (or other mathematical theories) can be formulated using a finite alphabet whose elements (about next sign of variables, certain mathematical and logical symbols , , , , , ) includes. (The countable infinite number of variables can be represented as specially marked words of the finite alphabet.) ${\displaystyle +}$ ${\displaystyle \cdot }$ ${\displaystyle =}$ ${\displaystyle \land }$ ${\displaystyle \Rightarrow }$ ${\displaystyle \forall }$

In this way, number theoretic statements (and even proofs) can be translated into numbers. As a consequence of this, number theory, which is supposed to deal with statements about numbers, can also handle statements about number theoretic statements and proofs. This fact is where Godel's incompleteness theorem starts.

Gödelization of Turing machines

A well-known application of the Gödel number is the coding of a Turing machine using a binary word . In this way, a number is assigned to each Turing machine (i.e. the set of all Turing machines can be counted). This fact is exploited , among other things, in the holding problem . ${\displaystyle w}$

example

Of course, various conventions for numbering can be agreed. The following is a simple example of the process. Be

${\displaystyle M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},\square ,F)}$

a Turing machine. Be o. B. d. A. the quantity of states , as well as the band alphabet numbered consecutively. ${\displaystyle Q}$ ${\displaystyle \Gamma }$

${\displaystyle Q=\{q_{0},q_{1},\ldots ,q_{k}\},\Gamma =\{a_{0},a_{1},\ldots ,a_{l}\};k,l\in \mathbb {N} }$

We now code each transition with a word above the alphabet . States or terminal symbols are represented by the binary representation of their indices, the individual elements are also separated. ${\displaystyle \delta (q_{m},a_{n})=(q_{m'},a_{n'},b)}$ ${\displaystyle b\in \{L,N,R\}}$ ${\displaystyle \{0,1,\#\}}$ ${\displaystyle \#}$

${\displaystyle \delta (q_{m},a_{n})=(q_{m'},a_{n'},b)\mapsto \#\#\operatorname {bin} (m)\#\operatorname {bin} (n)\#\operatorname {bin} (m')\#\operatorname {bin} (n')\#\operatorname {bin} (b)}$

where represents head movement ( ). In order to be able to restrict ourselves to the two-digit alphabet , we introduce a mapping of the set to : ${\displaystyle b}$ ${\displaystyle L=0,N=1,R=2}$ ${\displaystyle \{0,1\}}$ ${\displaystyle \{0,1,\#\}}$ ${\displaystyle \{0,1\}}$

${\displaystyle 0\mapsto 00,1\mapsto 01,\#\mapsto 10}$.

The Turing machine with the only production becomes like that . ${\displaystyle \delta (q_{0},0)\mapsto (q_{0},0,N)}$ ${\displaystyle 1010001000100010001001_{2}=2656393_{10}}$

An alternative that dispenses with the separator takes advantage of the uniqueness of the prime factorization in order to be able to encode tuples in a number.

See also

• Church-Turing thesis

Individual evidence

1. ↑ Hans Hermes: Enumerability - Decidability - Calculability , 2nd edition. Springer, Berlin 1971; P. 4, ISBN 3-540-05334-4 , ISBN 0-387-05334-4 .
2. ↑ Vera Spillner: Why Gödel's incompleteness sentence is still a horror for mathematicians today , on: Spektrum.de of July 2, 2017, letter to the editor no.3