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:
““Five o’clock tea” is a phrase our “rude forefathers,” even of the last generation, would scarcely have understood, so completely is it a thing of to-day; and yet, so rapid is the March of the Mind, it has already risen into a national institution, and rivals, in its universal application to all ranks and ages, and as a specific for “all the ills that flesh is heir to,” the glorious Magna Charta.”
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)
“I think that a young state, like a young virgin, should modestly stay at home, and wait the application of suitors for an alliance with her; and not run about offering her amity to all the world; and hazarding their refusal.... Our virgin is a jolly one; and tho at present not very rich, will in time be a great fortune, and where she has a favorable predisposition, it seems to me well worth cultivating.”
—Benjamin Franklin (1706–1790)
“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)