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 9 Aug 2008 02:49 On 9 Aug, 07:28, Balthasar <nomail(a)invalid> wrote: > On Fri, 8 Aug 2008 09:44:09 -0700 (PDT), MoeBlee <jazzm...(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). > 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." And again I'll notice that what you are assuming holds thanks to Cantor, so that your proof is just irrelevant to the present and related discussions. -LV > 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. > > The proof will even go trough in minimal logic + identity. > > Though it will fail in some systems of /crank logic/: > > "For every line of Cantor's list it is true that this line does not > contain the diagonal number. Nevertheless the diagonal number may > be in the infinite list." (WM) > > B.
From: Balthasar on 9 Aug 2008 02:55 On Sat, 09 Aug 2008 08:28:00 +0200, Balthasar <nomail(a)invalid> 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). > 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): [...] > Of course there's a simpler method to show this. From our definition of /x in L/ for a list L = (l_n), we have d in L <-> En(n e N & d = l_n). Hence ~(d in L) <-> ~En(n e N & d = l_n). Hence d not in L <-> An(n e N -> ~(d = l_n)). With other words, "d not in L" just "means" that d differs from every entry in L = (l_n). qed. Though this result seems to present another difficulty for WM's position: "For every line of Cantor's list it is true that this line does not contain the diagonal number. Nevertheless the diagonal number may be in the infinite list." B.
From: julio on 9 Aug 2008 03:08 On 9 Aug, 07:55, Balthasar <nomail(a)invalid> wrote: > On Sat, 09 Aug 2008 08:28:00 +0200, Balthasar <nomail(a)invalid> 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). > > 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): [...] > > Of course there's a simpler method to show this. > > From our definition of /x in L/ for a list L = (l_n), we have > > d in L <-> En(n e N & d = l_n). > Hence > ~(d in L) <-> ~En(n e N & d = l_n). > Hence > d not in L <-> An(n e N -> ~(d = l_n)). > > With other words, "d not in L" just "means" that d differs from every > entry in L = (l_n). qed. The endless ways of the same paralogism. But, will you ever get it? Infinity, clearly enumerable, here and now. It extends easily: you are an instance of the class of the failing machines. -LV > Though this result seems to present another difficulty for WM's > position: > > "For every line of Cantor's list it is true that this line does not > contain the diagonal number. Nevertheless the diagonal number may > be in the infinite list." > > B.
From: Balthasar on 9 Aug 2008 03:10 On Sat, 09 Aug 2008 08:28:00 +0200, Balthasar <nomail(a)invalid> 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. > Concerning the former claim just some comments (for our crank): Actually, Cantor himself did not consider /real numbers/ (and/or their decimal expansion) in his proof where he introduced the diagonal argument, hence all this (cranky) talking about "limits" and "limit entry" and whatnot could not arise. So, for the sake of the argument, let's _not_ consider a list of real numbers (and/or of their decimal expansions), but a list of infinite sequences of the two symbols /a/ and /b/. Now let's just consider one such list (to point out the construction of the anti-diagonal): (1) [a] a b b a a b a ... (2) a [a] a a a a b b ... (3) b b [b] b a a b a ... (4) a b b [b] a b b b ... : ... (Note, I put a [] around each symbol of the diagonal.) In this case we get the anti-diagonal by replacing /a/ with /b/ and vice versa. Hence we get the sequence b b a a ... Now this sequence differs from any sequence in the list by at least one symbol. (@Crank: Exercise!) With other words, it differs from every entry in the list. --------------------------------------------------------- B.
From: julio on 9 Aug 2008 03:17
On 9 Aug, 08:10, Balthasar <nomail(a)invalid> wrote: > On Sat, 09 Aug 2008 08:28:00 +0200, Balthasar <nomail(a)invalid> 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. > > Concerning the former claim just some comments (for our crank): So you in panic keep repeating yourself over and over again. I've just seen in a movie that's the way to recognize a machine masked as a human. I'm again impressed by how much wisdom there is in common wisdom. -LV > Actually, Cantor himself did not consider /real numbers/ (and/or their > decimal expansion) in his proof where he introduced the diagonal > argument, hence all this (cranky) talking about "limits" and > "limit entry" and whatnot could not arise. > > So, for the sake of the argument, let's _not_ consider a list of real > numbers (and/or of their decimal expansions), but a list of infinite > sequences of the two symbols /a/ and /b/. Now let's just consider one > such list (to point out the construction of the anti-diagonal): > > (1) [a] a b b a a b a ... > (2) a [a] a a a a b b ... > (3) b b [b] b a a b a ... > (4) a b b [b] a b b b ... > : ... > > (Note, I put a [] around each symbol of the diagonal.) > > In this case we get the anti-diagonal by replacing /a/ with /b/ and vice > versa. Hence we get the sequence > > b b a a ... > > Now this sequence differs from any sequence in the list by at least one > symbol. (@Crank: Exercise!) > > With other words, it differs from every entry in the list. > > --------------------------------------------------------- > > B. |