Hi Brent, Mirek, David, ....
From what you told me, I think you have no problem with Cantor 's
diagonal.
Are you ok with the key post, that is with the two supplementary uses
of the diagonal in the enumerable context?
Let me sum up, please consult the preceding posts for details.
1) Cantor:
If
f_1 f_2 f_3 f_4 ....
represents the image of a candidate bijection from N to N^N,
then
the diagonal function g, defined by
g(n) = f_n(n) + 1
gives a counter-example, that is, a function from N to N, which is not
in the image of the candidate bijection.
This works for any candidate bijection, so we can conclude that there
are no bijections between N and N^N.
2) We restrict the set of all functions from N to N. Now we consider
that the functions have to be computable, and this means that there
exist a language in which we can define those functions.
Lemma (= preliminary proposition): the set of things definable in a
language L is enumerable. (All right?)
Is there a universal language in which we can define all (total)
computable function from N to N?
a) Theorem: the answer to that question is NO, if it is asked that all
expressions (= well formed instructions for one variable function, say)
in the language define all AND ONLY ALL computable functions.
Proof:
if it was the case that all the expressions (for function of one
variable) defines all total computable function from N to N, then, by
the lemma, the set of such functions are not only enumerable, but can
be enumerated mechanically, computably, etc.
....
b) Theorem: if the answer is yes, then a universal machine cannot be
securized by any machine.
....
Oops: I'm interrupted. I let you try to finish this post. I come back
on it friday, or next week. Please don't hesitate to ask me any
question, or to make any remark, including meta-remarks, jokes, or
whatever. It would help me to have an idea if most of you get the point
or if most of you did not get it ... It is simple, but admittedly not
so simple, sure.
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 Tue Dec 11 2007 - 10:22:02 PST