Gödel Number

Turing machines are defined by sets of rules that operate on four parameters: (state, tape cell color, operation, state). Let the states and tape cell colors be numbered and represented by quadruples of ordinal numbers. Then there exist algorithmic procedures that sequentially list all consistent sets of Turing machine rules. A set of rules is called consistent if any two quadruples differ in the first or second element out of the four. Any such procedure gives both an algorithm for going from any integer to its corresponding Turing machine and an algorithm for getting the index of any consistent set of Turing machine rules.

Assume that one such procedure is selected. If Turing machine  is defined by the set of quadruples whose index is , then  is called the Gödel number of . The result of application of Turing machine with Godel number  to  is usually denoted .

Given the equivalence of computability and recursiveness, it is common to use Gödel numbers as indexes of recursive functions as well. The fact that it is possible to assign Gödel numbers to recursive functions implies that there is a countable infinite number of recursive functions. Hence, by Cantor's theorem, there exist functions which are not recursive. Each recursive function has an infinite number of distinct Gödel numbers.

Gödel numbers allow for a straightforward formal definition of the universal Turing machine  as

(1)

Many recursively undecidable problems are formulated in terms of Gödel numbers. For example, Gödel numbers are used in the theorem about recursive undecidability of the halting problem. Determining the convergence of  is also recursively undecidable.

Gödel numbers can be used to uniquely encode any list of positive integers  according to

(2)

where  is the th prime number.

When used to study statements in arithmetic, a Gödel number is a unique number for a given statement that can be formed as the product of successive primes raised to the power of the number corresponding to the individual symbols that comprise the sentence. For example, the statement  that reads "there exists an  such that  is the immediate successor of " can be coded

(3)

where the numbers in the set (8, 4, 13, 9, 8, 13, 5, 7, 16, 9) correspond to the symbols that make up . Prime-power coding using Gödel numbers can also be used to encode Turing machine rules.

REFERENCES

Davis, M. Computability and Unsolvability. New York: Dover 1982.

Hofstadter, D. R. Gödel, Escher, Bach: An Eternal Golden Braid. New York: Vintage Books, p. 18, 1989.

Kleene, S. C. Mathematical Logic. New York: Dover, 2002.

Rogers, H. Theory of Recursive Functions and Effective Computability. Cambridge, MA: MIT Press, 1987.

Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 1110 and 1120-1121, 2002.