Le 27-nov.-07, à 17:27, Günther Greindl a écrit :
> > Dear Bruno, > > thanks for your posts! I like them very much! > Looking forward to further stuff, Thanks for telling. In this post I recall Cantor's proof of the non enumerability of the set of infinite binary sequences. First with a drawing, and then with mathematical notation. The goal is to train you with the notations. Then I do the same with the almost exactly identical proof that the set of functions from N to N is also non enumerable. I hope you have no more problem with the identification of the set of functions from N to 2 (where 2 = {0, 1}), with the set of infinite binary sequences. Please ask in case of any trouble with that. A function from N to any set A always gives rise to an infinite sequence of elements of A. Note that I will never use Cantor's result. I explain it just to illustrate the use of diagonalization, and to contrast it with the use in the next post which will illustrate a capital feature of all universal machine. *** 1) 2^N is not enumerable (proof by drawing) Cantor argument goes like this. It is a reductio ad absurdo: Suppose that the set of infinite binary sequence is enumerable. That means that there is a bijection between N and that set. Such a bijection will have a shape like: 0 -------- 000101101111010100111... 1 -------- 011111111010100110000... 2 -------- 100011001001000100110... 3 -------- 101010101001010100100... 4 -------- 100000000001001111010... 5 -------- 000111111111100000010... ... But then I can find an infinite binary sequence which *cannot* be in the image of that "bijection". Indeed here is one: 1 0 1 1 1 0 ... It is the complementary sequence build from the diagonal sequence. QED. *** 1bis) 2^N is not enumerable (proof without drawing). Suppose that the set of binary infinite sequences is enumerable. That means there is a bijection between N and that set. It means that for each natural number i, there is a corresponding sequence s_i, and that all infinite binary sequences belongs somewhere in the enumeration s_0 s_1 s_2 s_3 s_4 s_5 ... Each s_i is a function from N to 2. For example, if s_0 denote the first sequence in the "drawing" above, it means that s_0(0) = 0, s_0(1) = 0, s_0(2) = 0, s_0(3) = 1, s_0(4) = 0, s_0(5) = 1, s_0(6) =1, etc. That is, s_i(j) the jth number (0 or 1) in the sequence s_i. s_i(j) gives the matrix drawn above, for i and j natural numbers. Then the number s_i(i), for i natural numbers gives the diagonal sequence, and the sequence 1- s_i(i) gives the complementary of the diagonal, and that sequence cannot belongs to the list of the s_i. We can make explicit the contradiction. If the sequence 1- s_i(i) was in the list s_i, there would exist a number k such that s_k(x) = 1 - s_x(x). But then for x = k, s_k(k) = 1 - s_k(k). But s_k(k) has to be one or zero, and in the first case you get 1 = 1 - 1 = 0, and in the other case you get 0 = 1 - 0 = 1. Contradiction. Damn... I must already go. I suggest you work by yourself the very similar proof that N^N is not enumerable. Of course you can derive this immediately from what we have just seen, given that a function from N to 2, is a particular case of a function from N to N. But it is a good training in *diagonalisation* to find the direct proof. I hope you can see that the set of all functions from N to N can be identify with the set NXNXNX... of sequences of natural numbers. I do quickly the "drawing proof", and let you write the more explicit proof (without drawing). Suppose there is such a bijection. It will look like: 0 -------- 23 456 76 67 ... 1 -------- 0 8 23 5 ... 2 -------- 67 10 10 123 ... 3 -------- 9 0 0 4 ... ... But then the sequence of numbers: 24 9 11 5 .... cannot be in that list. All right? See you tomorrow, Bruno > > Bruno Marchal wrote: >> >> >> Hi Mirek, Brent, Barry, David, ... and all those who could be >> interested >> in the INTRO to Church thesis, >> >> >> >> I have to go, actually. Just to prepare yourself to what will follow, >> below are recent links in the list . It could be helpful to revise a >> bit, or to ask last questions. >> I will ASAP come back on Cantor's Diagonal, (one more post), and then >> I >> will send the key fundamental post where I will present a version of >> Church thesis, and explain how from just CT you can already derive >> what >> I will call the first fundamental theorem. This one says that ALL >> universal machine (if that exists) are insecure. >> >> It is needed to explain why Lobian machine, which are mainly just >> Universal machine knowing that they are universal, cannot not be above >> all "theological" machine. As you can guess, knowing that they are >> universal, will make them know that they are insecure. >> >> All the term here will be defined precisely. In case you find this >> theorem depressing, I suggest you read "The Wisdom of Insecurity" by >> Alan Watts (Pantheon Books, Inc. 1951). An amazingly "lobian" informal >> philosophical text. >> >> Here are the last posts I send: >> >> 1) Bijections 1 >> http://www.mail-archive.com/everything-lis...m/msg13962.html >> 2) Bijections 2 >> http://www.mail-archive.com/everything-lis...m/msg13986.html >> 3) Bijection 3 >> http://www.mail-archive.com/everything-lis...m/msg13991.html >> 4) Cantor's diagonal >> http://www.mail-archive.com/everything-lis...m/msg13996.html >> >> Don't hesitate to ask any question if something remains unclear, >> >> Bruno >> >> >> PS: >> I recall the combinators thread, which could help later (but please >> don't consult them now, unless you already love lambda calculus or the >> combinators). >> >> The old (2005) combinators posts: >> >> http://www.mail-archive.com/everything-list@eskimo.com/msg05920.html >> http://www.mail-archive.com/everything-list@eskimo.com/msg05949.html >> http://www.mail-archive.com/everything-list@eskimo.com/msg05953.html >> http://www.mail-archive.com/everything-list@eskimo.com/msg05954.html >> http://www.mail-archive.com/everything-list@eskimo.com/msg05955.html >> http://www.mail-archive.com/everything-list@eskimo.com/msg05956.html >> http://www.mail-archive.com/everything-list@eskimo.com/msg05957.html >> http://www.mail-archive.com/everything-list@eskimo.com/msg05958.html >> http://www.mail-archive.com/everything-list@eskimo.com/msg05959.html >> http://www.mail-archive.com/everything-list@eskimo.com/msg05961.html >> >> >> http://iridia.ulb.ac.be/~marchal/ http://iridia.ulb.ac.be/~marchal/ --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Everything List" group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~----------~----~----~----~------~----~------~--~---