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.domain.name.hidden/msg05920.html
>> http://www.mail-archive.com/everything-list.domain.name.hidden/msg05949.html
>> http://www.mail-archive.com/everything-list.domain.name.hidden/msg05953.html
>> http://www.mail-archive.com/everything-list.domain.name.hidden/msg05954.html
>> http://www.mail-archive.com/everything-list.domain.name.hidden/msg05955.html
>> http://www.mail-archive.com/everything-list.domain.name.hidden/msg05956.html
>> http://www.mail-archive.com/everything-list.domain.name.hidden/msg05957.html
>> http://www.mail-archive.com/everything-list.domain.name.hidden/msg05958.html
>> http://www.mail-archive.com/everything-list.domain.name.hidden/msg05959.html
>> http://www.mail-archive.com/everything-list.domain.name.hidden/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 everything-list.domain.name.hidden
To unsubscribe from this group, send email to everything-list-unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
Received on Wed Nov 28 2007 - 10:47:55 PST