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.
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.
Read more about this topic: Description Number
Famous quotes containing the words application to, application and/or proofs:
“It would be disingenuous, however, not to point out that some things are considered as morally certain, that is, as having sufficient certainty for application to ordinary life, even though they may be uncertain in relation to the absolute power of God.”
—René Descartes (1596–1650)
“Science is intimately integrated with the whole social structure and cultural tradition. They mutually support one other—only in certain types of society can science flourish, and conversely without a continuous and healthy development and application of science such a society cannot function properly.”
—Talcott Parsons (1902–1979)
“I do not think that a Physician should be admitted into the College till he could bring proofs of his having cured, in his own person, at least four incurable distempers.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)