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 Z is defined by the set of quadruples whose index is x, then x is called the Gödel number of Z. The result of application of Turing machine with Godel number x to y is usually denoted phi_x(y).

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 U as


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 phi_x(x) is also recursively undecidable.

Gödel numbers can be used to uniquely encode any list of positive integers {a_1,a_2,...,a_n} according to


where p_k is the kth 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 ( exists x)(x=sy) that reads "there exists an x such that x is the immediate successor of y" can be coded


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

See also

Encoding, Gödel's First Incompleteness Theorem, Gödel's Second Incompleteness Theorem, Recursively Undecidable, Turing Machine

Portions of this entry contributed by Alex Sakharov (author's link)

Explore with Wolfram|Alpha


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.

Referenced on Wolfram|Alpha

Gödel Number

Cite this as:

Sakharov, Alex and Weisstein, Eric W. "Gödel Number." From MathWorld--A Wolfram Web Resource.

Subject classifications