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 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 Fri Aug 31 2007 - 07:08:05 PDT