Gödel numbering

A Gödel number is a natural number that is assigned to a word a formal language for a specific method and this word uniquely identifies. Such a method is referred to as Godelization. All enumerations defined on the coding of programs in a programming language Gödel numbering. The names refer to Kurt Godel, who stated the first time such a procedure, to prove his incompleteness theorem.

Formal definition

Be the ( countable ) set of words of a formal language. A function

Is called Gödelization when

• Injective and computable
• The image set decidable and
• Which is calculated to defined inverse function of.

One calls the Gödel number of.

Example

Suppose any words of formal language, based on the alphabet, should be gödelisiert. It should be.

One possibility would be the encoding, first assign the letter simply sequential numbers. "A" correspond to 1, a "b" of 2 and a "c" of the third one can now gödelisieren by multiplying the corresponding powers of the letter continuous primes together:

The word " abccba "

• The "a " in the first place has the value
• The "b" in the second place has a value of
• The "c" has a value of third
• The "c" in fourth place has the value
• The "b" in fifth place has the value
• The "a " in sixth place has the value

The Gödel number for " abccba " in this encoding is therefore

Since there are infinitely many prime numbers, one can in this way actually encode arbitrarily long words and due to the uniqueness of the prime factorization can be approximately from the number 1213962750 again the word " abccba " reconstruct. Although there are numbers that do not match any word of the language, for example (no first letter) or ( alphabet has no fourth element ). But at least these invalid values ​​can differ in a predictable way from the valid.

In addition to the one shown here, there are of course other methods to perform a Gödelization.

The method as described in the book Gödel, Escher, Bach used, for example, a value system with base 1000, which is very graphic, but formally more difficult to handle than a method based on prime powers such as the above.

Gödelization number-theoretic statements

In this way, therefore, can be number-theoretic statements (and even evidence) translate into numbers. As a consequence thereof, the number theory, yes should treat statements about numbers, treat statements about number-theoretic statements and evidence. This fact is the point at which attaches Gödel's incompleteness theorem.

Gödelization of Turing machines

A well-known application of the Gödel number is the encoding of a Turing machine by a binary word. In this way, any Turing machine is assigned a number (that is, the set of all Turing machines is countable ). This fact is used among other things in the halting problem.

Example

Of course, a variety of conventions for numbering can be reconciled. In the following, the operation is to be shown by a simple example. Be

A Turing machine. Be wlog the set of states, and the tape alphabet numbered.

We now encode the time being with each transition by a word over the alphabet. States or terminal symbols are represented by the binary representation of their indices, the individual elements are separated with.

The head movement is (). To limit ourselves to the two-digit alphabet, we perform a mapping of the set on a:

The Turing machine with the single production becomes so.

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