halting problem proof, via diagonalization?
in [Theory]
|
Prev: Integer factorization reduction to SAT
Next: Solutions manual to Microeconomic Theory Solution Manual - Mas-Colell
From: Paul E. Black on 12 Aug 2008 15:55 On Saturday 09 August 2008 02:28, Balthasar wrote: > On Fri, 8 Aug 2008 09:44:09 -0700 (PDT), MoeBlee <jazzmobe(a)hotmail.com> > wrote: >> Moreover, the anti-diagonal differs from every entry in the list. >> That's all that is required to show that the anti-diagonal is not >> on [or in] the list. >> > In the following I'll give a formal proof for this (the latter) claim. > > First some definitions. The /list/ L will be represented as an infinite > sequence: L = (l_n). The l_ns are the /entries/ in the list L = (l_n). Suppose we instead define a set L' = L U d, that is, all the above l_ns plus another value d. Now if we assume that d differs from every "countable"(?) entry in L', that is, An(n e N -> ~(d = l_n)) the proof does not hold. d can differ from "every" entry and still be in L'. Of course, there's nothing surprising about this. I think "julio" is essentially envisioning putting the limit entry (just) after the end of the infinite sequence. Julio wonders why we can't envision such a place, too. Although I can write the words "after the end of the infinite sequence", it doesn't mean the phrase indicates anything mathematically consistent or meaningful. > Accordingly we define for any list L = (l_n): > > x in L =df En(n e N & x = l_n). > "x is in the list L." > > x not in L =df ~(x in L) > "x is not in the list L." > > Now we have the assumption: > > L = (l_n) & An(n e N -> ~(d = l_n)). > > "The anti-diagonal d differs from every entry in the list L." > > We want to prove: > > d not in L. > > "The anti-diagonal d is not in the list L." > > Proof (in NJ + identity): > > 1 (1) L = (l_n) & An(n e N -> ~(d = l_n)) A > 2 (2) d in L A > 1 (3) L = (l_n) 1 &E > 1,2 (4) d in (l_n) 2,3 =E > 1,2 (5) En(n e N & d = l_n) 4 Def. "in" > 6 (6) a e N & d = l_a A > 6 (7) a e N 6 &E > 6 (8) d = l_a 6 &E > 1 (9) An(n e N -> ~(d = l_n)) 1 &E > 1 (10) a e N -> ~(d = l_a) 9 UE > 1,6 (11) ~(d = l_a) 7,10 ->E > 1,6 (12) _|_ 8,11 ~E > 1,2 (13) _|_ 5,6,12 EE > 1 (14) ~(d in L) 2,13 ~I > 1 (15) d not in L 14 Def. "not in" > > Hence we have shown: > > L = (l_n) & An(n e N -> ~(d = l_n)) |- d not in L. > > qed. Thanks for the neat proof. -paul-
From: herbzet on 12 Aug 2008 19:35 Daryl McCullough wrote: > herbzet says... > > >I've read over your posts of the last week and considerably farther > >back. I see nothing that I can understand as a definition or > >construction of the oo-th member of a list of reals in [0, 1], > >except a vague suggestion that it is formed by (transfinite?) > >induction on the members of the list. > > It doesn't actually matter what the oo-th member of the list is. > Diagonalization can produce as many new numbers as you like (as > long as you only like countably many). So we can alter Cantor's > diagonization procedure to produce two (or however many) > new reals. For example, in base-10, if you have an infinite > list of decimal expansions of reals between 0 and 1, you > can produce two new reals d1 and d2 that are not on the list: > > Let r(n)[m] = decimal place number m of real number n in the list. > Let d1[m] = decimal place number m of d1. > Let d2[m] = decimal place number m of d2. > > Then define d1 and d2 as follows: > > If r[n][n] < 5, then > d1[n] = 6 > d2[n] = 7 > > If r[n][n] > 5, then > d1[n] = 2 > d2[n] = 3 > > Then d1 and d2 will be two *different* reals that are not > on the list. If d1 happens to be r(oo) (whatever that is), > it will certainly *not* be the case that d2 is equal to r(oo), > since d1 is unequal to d2. Even if we limit ourselves to an alphabet of two symbols (say, '0' and '1') we can still construct lots of non-members of a given list, even though there is a unique anti-diagonal. All that is required is to construct a number that is distinct from each member of the list at some position; it doesn't necessarily have to be on the diagonal. For example, we could form the number d with its 2n-th digit taken different from the 2n-th digit of the n-th entry on the list (changing '1' for '0' and vice versa). All the rest of d's digits could be anything you want, all zero's for example. This number d (or one constructed by some other scheme) is not guarenteed to be distinct from the anti-diagonal, but it probably would be. I'd have to think a little further to think up a scheme that was guarenteed to produce numbers distinct from the anti-diagonal as well as from each member of the list with a binary alphabet. -- hz
From: herbzet on 12 Aug 2008 19:58 herbzet wrote: > Daryl McCullough wrote: > > herbzet says... > > > > >I've read over your posts of the last week and considerably farther > > >back. I see nothing that I can understand as a definition or > > >construction of the oo-th member of a list of reals in [0, 1], > > >except a vague suggestion that it is formed by (transfinite?) > > >induction on the members of the list. > > > > It doesn't actually matter what the oo-th member of the list is. > > Diagonalization can produce as many new numbers as you like (as > > long as you only like countably many). So we can alter Cantor's > > diagonization procedure to produce two (or however many) > > new reals. For example, in base-10, if you have an infinite > > list of decimal expansions of reals between 0 and 1, you > > can produce two new reals d1 and d2 that are not on the list: > > > > Let r(n)[m] = decimal place number m of real number n in the list. > > Let d1[m] = decimal place number m of d1. > > Let d2[m] = decimal place number m of d2. > > > > Then define d1 and d2 as follows: > > > > If r[n][n] < 5, then > > d1[n] = 6 > > d2[n] = 7 > > > > If r[n][n] > 5, then > > d1[n] = 2 > > d2[n] = 3 > > > > Then d1 and d2 will be two *different* reals that are not > > on the list. If d1 happens to be r(oo) (whatever that is), > > it will certainly *not* be the case that d2 is equal to r(oo), > > since d1 is unequal to d2. > > Even if we limit ourselves to an alphabet of two symbols (say, > '0' and '1') we can still construct lots of non-members of > a given list, even though there is a unique anti-diagonal. > > All that is required is to construct a number that is distinct > from each member of the list at some position; it doesn't > necessarily have to be on the diagonal. > > For example, we could form the number d with its 2n-th > digit taken different from the 2n-th digit of the n-th > entry on the list (changing '1' for '0' and vice versa). > All the rest of d's digits could be anything you want, > all zero's for example. Then we could make them all one's to form a number d_0. One of d or d_0 would surely be different from the anti-diagonal, as well as different from each member of the list. -- hz
From: herbzet on 12 Aug 2008 20:41 herbzet wrote: > herbzet wrote: > > Daryl McCullough wrote: > > > herbzet says... > > > > > > >I've read over your posts of the last week and considerably farther > > > >back. I see nothing that I can understand as a definition or > > > >construction of the oo-th member of a list of reals in [0, 1], > > > >except a vague suggestion that it is formed by (transfinite?) > > > >induction on the members of the list. > > > > > > It doesn't actually matter what the oo-th member of the list is. > > > Diagonalization can produce as many new numbers as you like (as > > > long as you only like countably many). So we can alter Cantor's > > > diagonization procedure to produce two (or however many) > > > new reals. For example, in base-10, if you have an infinite > > > list of decimal expansions of reals between 0 and 1, you > > > can produce two new reals d1 and d2 that are not on the list: > > > > > > Let r(n)[m] = decimal place number m of real number n in the list. > > > Let d1[m] = decimal place number m of d1. > > > Let d2[m] = decimal place number m of d2. > > > > > > Then define d1 and d2 as follows: > > > > > > If r[n][n] < 5, then > > > d1[n] = 6 > > > d2[n] = 7 > > > > > > If r[n][n] > 5, then > > > d1[n] = 2 > > > d2[n] = 3 > > > > > > Then d1 and d2 will be two *different* reals that are not > > > on the list. If d1 happens to be r(oo) (whatever that is), > > > it will certainly *not* be the case that d2 is equal to r(oo), > > > since d1 is unequal to d2. > > > > Even if we limit ourselves to an alphabet of two symbols (say, > > '0' and '1') we can still construct lots of non-members of > > a given list, even though there is a unique anti-diagonal. > > > > All that is required is to construct a number that is distinct > > from each member of the list at some position; it doesn't > > necessarily have to be on the diagonal. > > > > For example, we could form the number d with its 2n-th > > digit taken different from the 2n-th digit of the n-th > > entry on the list (changing '1' for '0' and vice versa). > > All the rest of d's digits could be anything you want, > > all zero's for example. > > Then we could make them all one's to form a number d_0. > One of d or d_0 would surely be different from the > anti-diagonal, as well as different from each member > of the list. I've been ignoring the problem of dual representations of numbers, e.g. .1000... = .0111... but I guess someone else could cope with that if they cared to. The fact that we can easily cope with it using base 10 numeration is a satisfactory solution anyway. -- hz
From: Daryl McCullough on 13 Aug 2008 07:26
herbzet says... >I've been ignoring the problem of dual representations of >numbers, e.g. .1000... = .0111... but I guess someone else >could cope with that if they cared to. The fact that we can >easily cope with it using base 10 numeration is a satisfactory >solution anyway. There are several ways to cope with dual representations. One is to use a higher base. Another is to assume that the original list includes every dual-representation real in both its representations. Another is to take bits two at a time and at stage n, make sure that the diagonal differs from real number in both bit number 2n and bit number 2n+1. (Which is really equivalent to using base-4 instead of base-2) -- Daryl McCullough Ithaca, NY |