halting problem proof, via diagonalization?
in [Theory]
|
Prev: Integer factorization reduction to SAT
Next: Solutions manual to Microeconomic Theory Solution Manual - Mas-Colell
From: julio on 8 Aug 2008 12:39 On 8 Aug, 16:30, LauLuna <laureanol...(a)yahoo.es> wrote: > 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. And this is where there are most of the objections. Below again a simple argument to show that from the very same construction we could induce the exact opposite result: 1: The diagonal differs from the 1st entry in the 1st place; 2: The diagonal differs from the 2nd entry in the 2nd place; ... n: The diagonal differs from the n-th entry in the n-th place; It seems straightforward to induce that, at the limit, the difference between the diagonal and the limit entry tends to zero. -LV > 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
From: MoeBlee on 8 Aug 2008 12:44 On Aug 8, 9:39 am, ju...(a)diegidio.name wrote: > Below again a simple argument to show that from the very same > construction we could induce the exact opposite result: > > 1: The diagonal differs from the 1st entry in the 1st place; > 2: The diagonal differs from the 2nd entry in the 2nd place; > ... > n: The diagonal differs from the n-th entry in the n-th place; > > It seems straightforward to induce that, at the limit, the difference > between the diagonal and the limit entry tends to zero. WHAT limit? You need to DEFINE "limit" in terms of some topology, metric, ordering, or whatever. We don't just use the word "limit" without the context of the EXACT sense of a limit as it has been DEFINED. Moreover, the anti-diagonal differes from every entry in the list. That's all that is required to show that the anti-diagonal is not on the list. MoeBlee
From: Aatu Koskensilta on 8 Aug 2008 12:44 julio(a)diegidio.name writes: > Below again a simple argument to show that from the very same > construction we could induce the exact opposite result: > > 1: The diagonal differs from the 1st entry in the 1st place; > 2: The diagonal differs from the 2nd entry in the 2nd place; > ... > n: The diagonal differs from the n-th entry in the n-th place; > > It seems straightforward to induce that, at the limit, the difference > between the diagonal and the limit entry tends to zero. Wonderful. I wonder how many people will rush in to the rescue, asking "What limit entry?" or exclaiming most ferociously "There is no limit entry!". Surely you can anticipate this response just as well as the next man. The obvious question, then, is why bother? Why not come up with some novel rubbish? -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechen kann, darüber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: julio on 8 Aug 2008 12:47 On 8 Aug, 17:44, Aatu Koskensilta <aatu.koskensi...(a)uta.fi> wrote: > ju...(a)diegidio.name writes: > > Below again a simple argument to show that from the very same > > construction we could induce the exact opposite result: > > > 1: The diagonal differs from the 1st entry in the 1st place; > > 2: The diagonal differs from the 2nd entry in the 2nd place; > > ... > > n: The diagonal differs from the n-th entry in the n-th place; > > > It seems straightforward to induce that, at the limit, the difference > > between the diagonal and the limit entry tends to zero. > > Wonderful. I wonder how many people will rush in to the rescue, asking > "What limit entry?" or exclaiming most ferociously "There is no limit > entry!". Surely you can anticipate this response just as well as the > next man. The obvious question, then, is why bother? Why not come up > with some novel rubbish? Because I cannot get what is wrong with it. The "limit" is of course induction. -LV > -- > Aatu Koskensilta (aatu.koskensi...(a)uta.fi) > > "Wovon man nicht sprechen kann, darüber muss man schweigen" > - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: julio on 8 Aug 2008 12:53
On 8 Aug, 17:44, MoeBlee <jazzm...(a)hotmail.com> wrote: > On Aug 8, 9:39 am, ju...(a)diegidio.name wrote: > > > Below again a simple argument to show that from the very same > > construction we could induce the exact opposite result: > > > 1: The diagonal differs from the 1st entry in the 1st place; > > 2: The diagonal differs from the 2nd entry in the 2nd place; > > ... > > n: The diagonal differs from the n-th entry in the n-th place; > > > It seems straightforward to induce that, at the limit, the difference > > between the diagonal and the limit entry tends to zero. > > WHAT limit? You need to DEFINE "limit" in terms of some topology, > metric, ordering, or whatever. We don't just use the word "limit" > without the context of the EXACT sense of a limit as it has been > DEFINED. It's induction over the infinite ordered list (we have discussed this for hundred posts and you still ask the same question). > Moreover, the anti-diagonal differes from every entry in the list. > That's all that is required to show that the anti-diagonal is not on > the list. There is no reason for your "moreover". Moreover, the difference in question tends to zero, so that the anti-diagonal happens to correspond to the limit entry: you have (yet) not addressed that. -LV > MoeBlee |