Description numbers are numbers that arise in the theory of Turing machines, very similar to Gödel numbers, and they are also occasionally called that in the literature. Given some universal Turing machine, every Turing machine can, given its encoding on that machine, be assigned a number. This is the machine's description number. These numbers play a key role in Alan Turing's proof of the undecidability of the halting problem, and are very useful in reasoning about Turing machines as well. An artistic representation of a Turing Machine . ... In formal number theory a Gödel numbering is a function which assigns to each symbol and formula of some formal language a unique natural number called a Gödel number (GN). ... The Turing machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or mechanical procedure. As such it is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. ... Alan Turing is often considered the father of modern computer science. ... In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input. ...

An example of a description number

Say we had a Turing machine M with states q₁, ... q_R, with a tape alphabet with symbols s₁, ... s_m, with the blank denoted by s₀, and transitions giving the current state, current symbol, and actions performed (which might be to overwrite the current tape symbol and move the tape head left or right, or maybe not move it at all), and the next state. Under the original universal machine described by Alan Turing, this machine would be encoded as input to it as follows:

1. The state q_i is encoded by the letter 'D' followed by the letter 'A' repeated i times (a unary encoding)
2. The tape symbol s_j is encoded by the letter 'D' followed by the letter 'C' repeated j times
3. The transitions are encoded by giving the state, input symbol, symbol to write on the tape, direction to move (expressed by the letters 'L', 'R', or 'N', for left, right, or no movement), and the next state to enter, with states and symbols encoded as above.

The UTM's input thus consists of the transitions separated by semicolons, so its input alphabet consists of the seven symbols, 'D', 'A', 'C', 'L', 'R', 'N', and ';'. For example, for a very simple Turing machine that alternates printing 0 and 1 on its tape forever: Unary may mean Unary numeral system Unary operator — a kind of operator that has only one operand This is a disambiguation page — a navigational aid which lists other pages that might otherwise share the same title. ...

1. State: q₁, input symbol: blank, action: print 1, move right, next state: q₂
2. State: q₂, input symbol: blank, action: print 0, move right, next state: q₁

Letting the blank be s₀, '0' be s₁ and '1' be s₂, the machine would be encoded by the UTM as:

DADDCCRDAA;DAADDCRDA;

But then, if we replaced each of the seven symbols 'A' by 1, 'C' by 2, 'D' by 3, 'L' by 4, 'R' by 5, 'N' by 6, and ';' by 7, we would have an encoding of the Turing machine as a natural number: this is the description number of that Turing machine under Turing's universal machine. The simple Turing machine described above would thus have the description number 313322531173113325317. There is an analogous process for every other type of universal Turing machine. It is usually not necessary to actually compute a description number in this way: the point is that every natural number may be interpreted as the code for at most one Turing machine, though many natural numbers may not be the code for any Turing machine (or to put it another way, they represent Turing machines that have no states). The fact that such a number always exists for any Turing machine is generally the important thing. In mathematics, a natural number is either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). The former definition is generally used in number theory, while the latter is preferred in set theory and computer science. ...

Application to undecidability proofs

Description numbers play a key role in many undecidability proofs, such as the proof that the halting problem is undecidable. In the first place, the existence of this direct correspondence between natural numbers and Turing machines shows that the set of all Turing machines is denumerable, and since the set of all partial functions is uncountably infinite, there must certainly be many functions that cannot be computed by Turing machines. In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input. ... Undecidable has more than one meaning: In mathematical logic: A decision problem is undecidable if there is no known algorithm that decides it. ... In mathematics the term countable set is used to describe the size of a set, e. ... In mathematics, a partial function is a relation that associates each element of a set (sometimes called its domain) with at most one element of another (possibly the same) set, called the codomain. ... In mathematics, an uncountable set is a set which is not countable. ...

By making use of a technique similar to Cantor's diagonal argument, it is possible exhibit such an uncomputable function, for example, that the halting problem in particular is undecidable. First, let us denote by U(e, x) the action of the universal Turing machine given a description number e and input x, returning 0 if e is not the description number of a valid Turing machine. Now, supposing that there were some algorithm capable of settling the halting problem, i.e. a Turing machine TEST(e) which given the description number of some Turing machine would return 1 if the Turing machine halts on every input, or 0 if there are some inputs that would cause it to run forever. By combining the outputs of these machines, it should be possible to construct another machine δ(k) that returns U(k, k) + 1 if TEST(k) is 1 and 0 if TEST(k) is 0. From this definition δ is defined for every input and must naturally be total recursive. Since δ is built up from what we have assumed are Turing machines as well then it too must have a description number, call it e. So, we can feed the description number e to the UTM again, and by definition, δ(k) = U(e, k), so δ(e) = U(e, e). But since TEST(e) is 1, by our other definition, δ(e) = U(e, e) + 1, leading to a contradiction. Thus, TEST(e) cannot exist, and in this way we have settled the halting problem as undecidable. Cantors diagonal argument is a proof devised by Georg Cantor to demonstrate that the real numbers are not countably infinite. ... In mathematics and computing, an algorithm is a procedure (a finite set of well-defined instructions) for accomplishing some task which, given an initial state, will terminate in a defined end-state. ...

See also

• Gödel number
• Universal Turing machine
• Church numeral
• Halting problem

In formal number theory a Gödel numbering is a function which assigns to each symbol and formula of some formal language a unique natural number called a Gödel number (GN). ... The Turing machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or mechanical procedure. As such it is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. ... A Church integer is a representation of natural numbers as functions, invented by Alonzo Church as part of his lambda calculus. ... In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input. ...

References

• John Hopcroft and Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation, 1st edition, Addison-Wesley. ISBN 0-201-44124-1. (the Cinderella book)
• Turing, A. M. "On computable numbers, with an application to the Entscheidungsproblem", Proc. Roy. Soc. London, 2(42), 1936, pp. 230-265.