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:
“The receipt to make a speaker, and an applauded one too, is short and easy.—Take of common sense quantum sufficit, add a little application to the rules and orders of the House, throw obvious thoughts in a new light, and make up the whole with a large quantity of purity, correctness, and elegancy of style.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)
“It is known that Whistler when asked how long it took him to paint one of his “nocturnes” answered: “All of my life.” With the same rigor he could have said that all of the centuries that preceded the moment when he painted were necessary. From that correct application of the law of causality it follows that the slightest event presupposes the inconceivable universe and, conversely, that the universe needs even the slightest of events.”
—Jorge Luis Borges (1899–1986)
“A man’s women folk, whatever their outward show of respect for his merit and authority, always regard him secretly as an ass, and with something akin to pity. His most gaudy sayings and doings seldom deceive them; they see the actual man within, and know him for a shallow and pathetic fellow. In this fact, perhaps, lies one of the best proofs of feminine intelligence, or, as the common phrase makes it, feminine intuition.”
—H.L. (Henry Lewis)