Hi Brent, Mirek, David, ....

 From what you told me, I think you have no problem with Cantor 's 

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:


f_1  f_2  f_3  f_4 ....

represents the image of a candidate bijection from N to N^N,


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.


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.



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