halting problem proof, via diagonalization?
in [Theory]
|
Prev: Integer factorization reduction to SAT
Next: Solutions manual to Microeconomic Theory Solution Manual - Mas-Colell
From: RichD on 8 Aug 2008 05:09 I heard someone say recently, "The proof of the Turing machine halting problem is an example of diagonalization." I don't see that. As I recall, it's proof by contradiction; assume a program which accomplishes the goal, feed the code of this program to itself, etc., ad absurdum. QED Whereas diagonalization consists of constructing a list, then constructing a new object not in the list, etc. Can anyone reconcile this? -- Rich
From: David C. Ullrich on 8 Aug 2008 06:15 On Fri, 8 Aug 2008 02:09:11 -0700 (PDT), RichD <r_delaney2001(a)yahoo.com> wrote: >I heard someone say recently, "The proof of the Turing >machine halting problem is an example of diagonalization." > >I don't see that. As I recall, it's proof by contradiction; >assume a program which accomplishes the goal, feed >the code of this program to itself, etc., ad absurdum. QED > >Whereas diagonalization consists of constructing a list, >then constructing a new object not in the list, etc. > >Can anyone reconcile this? The word "diagonalization" gets used a little informally - in some sense the idea behind the two proofs, or part of the structure of the two proofs, is the same. In the proof of the uncountability of the reals we start with a sequence x_1, x_2, ... of reals. Say x_j[n] is the n-th digit in the decimal expansion of x_j. Then x_j[j] is a "diagonal" element of a certain "matrix", and the proof proceeds by constructing a real number x such that x[j] is _not_ equal to x_j[j]. Note the "not". Here's another proof by "diagonalization" that's just one notch more abstract. If A is a set then P(A) is the power set of A; that is, P(A) is the set of all subsets of A. Thm 1. If A is a set then there is no function mapping A _onto_ P(A). In other words, if f : A -> P(A) is any function then there exists S in P(A) (ie S is a subset of A) such that S is not equal to f(a) for any a in A. Proof: Suppose f : A -> P(A). Define S, a subset of A, by S = {x in A such that x is not an element of f(x)}. (Note the "not" there...) Then for any a in A, S is not equal to f(a). Suppose on the other hand that S = f(a) for some particular a in A. Now, either a is an element of S or a is not an element of S. But if a is an element of S then the definition of S shows that a is not an element of S. And if a is not an element of S then the definition of S shows that a _is_ an element of S. So both a in S and a not in S are impossible. Contradiction, QED. Let''s rephrase the theorem and the proof to make it look more like the diagonal argument showing the reals are uncountable. If A is a set then 2^A is the set of all function mapping A into the two-element set {0,1}. Since there _is_ an obvious one-to-one correspondence between P(A) and 2^A, Theorem 1 is the same as saying that there is no function mapping A onto 2^A. And that's the same as this: Thm 2. Suppose A is a set, and suppose that for every a in A we are given a function x_a, which maps A into {0,1}. (So x_a(b) is 0 or 1 for every a, b in S.) Then there exists x, a function mapping A into {0,1}, such that x is not equal to x_a for any a in A. Proof: Define x : A -> {0,1} by x(a) = 1 - x_a(a) (for all a in A). The point to that funny formula 1 - x_a(a) is just that x(a) is _not_ equal to x_a(a) (because 1 - 0 = 1 <> 0 and 1 - 1 = 0 <> 1.) Since x(a) is not equal to x_a(a), x is not the same as x_a. QED. Note that x_a(a) is the "diagonal" element of our array of functions {x_a}, and the key is constructing x so x(a) <> x_a(a). Exactly like the x[j] <> x_x[j] in the proof of uncountability of the reals. So Theorem 2 really is a diagonalization argument; the proof is almost exactly the same as the proof of uncountability of the reals. But the proof of Theorem 1 is really the same as the proof of Theorem 2, just in different notation. So Theorem 1 gets called a diagonal argument as well. Now look at the "Sketch of Proof" at http://en.wikipedia.org/wiki/Halting_problem and the comments that follow. David C. Ullrich "Understanding Godel isn't about following his formal proof. That would make a mockery of everything Godel was up to." (John Jones, "My talk about Godel to the post-grads." in sci.logic.)
From: Peter_Smith on 8 Aug 2008 10:29 [Cue shameless advertising] There's something about the aptness of extending the idea of diagonalization from "diagonalizing out of a list" to the sorts of constructions involved in constructing a standard Gödel sentence (or in proving the unsolvability of the halting problem) in my Introduction to Gödel's Theorems [www.godelbook.net], at p. 130, cf. p. 307.
From: Daryl McCullough on 8 Aug 2008 11:10 RichD says... >I heard someone say recently, "The proof of the Turing >machine halting problem is an example of diagonalization." > >I don't see that. As I recall, it's proof by contradiction; >assume a program which accomplishes the goal, feed >the code of this program to itself, etc., ad absurdum. QED > >Whereas diagonalization consists of constructing a list, >then constructing a new object not in the list, etc. > >Can anyone reconcile this? You can express the unsolvability of the halting problem as a theorem that is proved by diagonalization: Pick some standard way to assign a unique integer to every Turing machine program that takes exactly one input. We will say that the integer assigned to a Turing machine M is the "code" of M. Say that a pair <n,x> of integers is a "non-halting pair" if the Turing machine with code n does not halt on input x. Theorem 1: If <n_1,x_1>, <n_2,x_2>, ... is any computable list of non-halting pairs, then there is a non-halting pair <n,x> that is not on that list. Proof: Let M(x) be the program that checks to see if <x,x> is on the list, and if so, halts. If <x,x> is not on the list, then M(x) runs forever. Let n be the code of M. Then <n,n> is a non-halting pair, but it is not on the list. -- Daryl McCullough Ithaca, NY
From: LauLuna on 8 Aug 2008 11:30
On Aug 8, 11:09 am, RichD <r_delaney2...(a)yahoo.com> wrote: > I heard someone say recently, "The proof of the Turing > machine halting problem is an example of diagonalization." > > I don't see that. As I recall, it's proof by contradiction; > assume a program which accomplishes the goal, feed > the code of this program to itself, etc., ad absurdum. QED > > Whereas diagonalization consists of constructing a list, > then constructing a new object not in the list, etc. > > Can anyone reconcile this? > > -- > Rich Diagonalization is a very general tecnique aiming at showing thet a certain set S does not exist: e.g. a countable set of all reals (Cantor), a bijection between A and P(A) (Cantor), a recursively enumerable set of all arithmetical truths (Gödel), an arithmetically definable set of all arithmetical truths (Tarski), etc. The tecnique can be seen as a reductio of the assumption that S exists and it typically proceeds by constructing a diagonal object D that should be in S if S existed but that, by construction, cannot be in S. This is sometimes put as the indefinite extensibility of any set T 'purporting' to be S; then it's shown that there is a (diagonal) function f that for any T gives an object d such that d is in T if T=S and it's shown that d is actually not in T. You may or may not require that f be computable. Now consider the usual proof of Turing's theorem. Assume there is a Turing machine H that computes the halting problem for any Turing machine. Then we can use H to construct a double input matrix M that for any pair (m, n), where m is a code (a Gödel number) of a Turing machine and n is a natural, displays 1 if m terminates on n and 0 otherwise. Now H must be in M coded (say) by h. We give h to H (h acting as a code for (h, h)) in order to fill in the corresponding square in M. To decide the halting problem for this specific input, H has to compute what H does when fed h, that is, it has to compute whether its current computation terminates; the ensuing circularity prevents H from giving an output and forces us to leave the corresponding square in M blank. So, under the assumption that H exists, we've produced a computation (h, h) whose behavior is not represented in M, which contradicts the assumption. Since M can be regarded as a set, (h, h) is an object that should be a member of M (if H existed) but is not such; thus the procedure fits with the general diagonal procedure described above. Regards |