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)
“The main object of a revolution is the liberation of man ... not the interpretation and application of some transcendental ideology.”
—Jean Genet (1910–1986)
“To invent without scruple a new principle to every new phenomenon, instead of adapting it to the old; to overload our hypothesis with a variety of this kind, are certain proofs that none of these principles is the just one, and that we only desire, by a number of falsehoods, to cover our ignorance of the truth.”
—David Hume (1711–1776)