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.
Contact the MathWorld Team
-0.283882181415
