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:

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 


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)?



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 

Reply via email to