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 [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 -~----------~----~----~----~------~----~------~--~---
