Description number
Encyclopedia
Description numbers are numbers that arise in the theory of Turing machine
s. They are very similar to Gödel number
s, and are also occasionally called "Gödel numbers" 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.
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:
Letting the blank be s0, '0' be s1 and '1' be s2, 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.
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 function
s is uncountably infinite, there must certainly be many functions that cannot be computed by Turing machines.
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.
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
s. They are very similar to Gödel number
Gödel number
In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. The concept was famously used by Kurt Gödel for the proof of his incompleteness theorems...
s, and are also occasionally called "Gödel numbers" in the literature. Given some universal Turing machine
Universal Turing machine
In computer science, a universal Turing machine is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input. The universal machine essentially achieves this by reading both the description of the machine to be simulated as well as the input thereof from its own tape. Alan...
, 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
Alan Turing
Alan Mathison Turing, OBE, FRS , was an English mathematician, logician, cryptanalyst, and computer scientist. He was highly influential in the development of computer science, providing a formalisation of the concepts of "algorithm" and "computation" with the Turing machine, which played a...
's proof of the undecidability of the halting problem
Halting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
, and are very useful in reasoning about Turing machines as well.
An example of a description number
Say we had a Turing machine M with states q1, ... qR, with a tape alphabet with symbols s1, ... sm, with the blank denoted by s0, 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:- The state qi is encoded by the letter 'D' followed by the letter 'A' repeated i times (a unaryUnary* Unary numeral system, the simplest numeral system to represent natural numbers* Unary operation, a kind of mathematical operator that has only one operand* Unary coding, an entropy encoding that represents a number n with n − 1 ones followed by a zero...
encoding) - The tape symbol sj is encoded by the letter 'D' followed by the letter 'C' repeated j times
- 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:
- State: q1, input symbol: blank, action: print 1, move right, next state: q2
- State: q2, input symbol: blank, action: print 0, move right, next state: q1
Letting the blank be s0, '0' be s1 and '1' be s2, 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
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
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.
Application to undecidability proofs
Description numbers play a key role in many undecidability proofs, such as the proof that the halting problemHalting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
is undecidable
Undecidable
Undecidable may refer to:In mathematics and logic* Undecidable problem - a decision problem which no algorithm can decide* "Undecidable" is sometimes used as a synonym of "independent", where a formula in mathematical logic is independent of a logical theory if neither that formula nor its negation...
. 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 function
Partial function
In mathematics, a partial function from X to Y is a function ƒ: X' → Y, where X' is a subset of X. It generalizes the concept of a function by not forcing f to map every element of X to an element of Y . If X' = X, then ƒ is called a total function and is equivalent to a function...
s is uncountably infinite, there must certainly be many functions that cannot be computed by Turing machines.
By making use of a technique similar to Cantor's diagonal argument
Cantor's diagonal argument
Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument or the diagonal method, was published in 1891 by Georg Cantor as a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural...
, 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
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
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.
See also
- Gödel numberGödel numberIn mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. The concept was famously used by Kurt Gödel for the proof of his incompleteness theorems...
- Universal Turing machineUniversal Turing machineIn computer science, a universal Turing machine is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input. The universal machine essentially achieves this by reading both the description of the machine to be simulated as well as the input thereof from its own tape. Alan...
- Church numeral
- Halting problemHalting problemIn computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...