Hi David,
Le 29-août-07, à 16:57, I (Bruno Marchal) wrote : > > I must go. Tomorrow I begin to explain the idea of a computable > function. To let you think in advance I give you a problem: have you an > idea why NON computable functions have to exist? I feel a bit guilty because, 'course, that is a *very* tricky question, and I have made quite a jump here! Let me continue in that vein! Could we even hope that a the notion of computability can be defined mathematically? Is not "computable" an epistemic notion? How could we think that a function computable by the french is necessarily computable by the belgians, and vice versa? Should not John Mikes interrupt me, and tell me: "Bruno, whatever definition of computability you will give to us, it will only define, at the best, a notion of *human* computability, certainly not an absolute notion! Where does my confidence that John would be wrong here comes from? Well, most of you know the answer, my confidence comes from .... what is known as "Church's Thesis" CT (sometimes by Post Law, or Church-Turing thesis, or Post-Markov-Kleene thesis, ...). David, here is a little roadmap: GOAL: to get a thorough understanding that the notion of computability is absolute. This is needed, not only for grasping that the universal dovetailer is really universal (and thus for the grasping of the informal UDA), but is also needed to get a thorough understanding that the notion of provability is not absolute, and cannot been made universal. John would be right to criticize any notion of absolute provability; but for the notion of computability, well, a miracle will occur (Godel's eventual wording on CT). MEANS: I think, if you are patient enough, that I will go back were the story starts, and I think it starts with GALILEO. Galileo is indeed the first, as far as I know, to realize that there is a bijection between N and 2N (by which I mean the set of even numbers). Galileo was disturbed by the fact a set (N) could be put in one-one correspondence with a proper subset of itself (2N). I will come back on this, but for now I am thinking on the following roadmap: Bijection Enumeration (bijection with N) Non enumerable set And only when this will be clear, can we introduce the subtler and most important concept of mechanical or effective or recursive enumeration and introduce Church thesis and computability. And then we will proceed toward the notion of provability, and only then can we address the notion of "machine theology" .... OK? We have to address that Church Miracle. So: Do you see that there is a bijection between N = {0, 1, 2, 3, 4 ...} and 2N = {0, 2, 4, 6, 8, ...}. Which one? Do you see that there is a bijection between N and NXN (= the set of couple (x, y) with x and y belonging to N)? Bruno 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 -~----------~----~----~----~------~----~------~--~---