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.

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.