Hi David, Mirek, Tom, Barry and All, In the preceding post, I gave you an informal proof in naïve set theory that the set of functions from N to N was not enumerable.

Note: the preceding post = http://www.mail-archive.com/everything-list@eskimo.com/msg14063.html It is not in my intention at all to convince you that Cantor's result is true. A problem which occurs is the many invocation of Gods. Cantor himself will hide paradoxes and also will discuss with theologians on those problems. Today we know Cantor's theorem is provable in reasonably sound accounts of sets, like Zermelo Fraenkel Set Theory, ZF. But it is not my purpose to dwelve into set theory. My purpose is computability theory. What happens if we try to restrict ourselves to *computable* functions from N to N, instead of *all* functions from N to N. In this case we would not be obliged to refer to Gods, those who were able to "see" an arbitrary and infinite long sequence of numbers. But we get somehow the anti-problem. How to define what is a computable function? We can hardly be satisfied by an anti-solution like: Anti-definition: A function from N to N is computable if it can be computed without any invocation to any Gods. So we have to find a more positive definition, and invoke *finite and humble* creature instead. Humble, because we have to be sure not attributing to them any magical and hard to define qualities like cleverness, intelligence, intuition or any god-like predicate. So here is an informal "definition" of what is an (intuitively) computable function from N to N. "Definition": a function f is computable if there is a finite set of instructions such that a complete asshole can, on each n compute in a finite time the result f(n). OK. "complete asshole" is probably a bit popular, and I will use the adverb "unambiguously" instead. Also, what are the instructions? Whatever they are, they have to be described in some language, which has to be unambiguous (understandable by that humble finite creature). So here is a better "definition" of what is a computable function from N to N. A function f from N to N is said (intuitively) computable if there is a language L in which it is possible to describe unambiguously through a finite expression in L how, for any n to compute f(n) in a finite time. The finite expression are intended to express the instructions. A language is the given of a finite alphabet A, and a subset L of unambiguous expressions. If A is a finite or enumerable alphabet, then I will denote by A°, the set of finite expressions written with the alphabet A. I recall that If A is finite or enumerable, then A° is enumerable too. Indeed, you can put an alphabetical order on all sequences of length 1, and then of length 2, etc. Exemple: A = {S, K, (, ) } Ordering the finite expressions, using the order "K < S < ( < )" on the alphabet: finite expressions= K, S, (, ), [length one] KK, KS, K(, K), SK, SS, S(, S), (K, (S, ((, (), )K, )S, )(, )), [length two] KKK , ... [length 3] KKKK, ... [length 4] Note that ")))KK))S())" is a finite expression on the alphabet. It is does not refer to a combinator, which are associated only to well-formed expressions, like, if you remember, (K(SK)), or ((S(KS))K), making a subset of the set of all (finite) expressions. Now, two fundamental definitions: Universal Language: A language L is universal if all computable functions (from N to N) can be described in L. Universal Machine: A machine M is universal if M understands L, and so M can actually compute the value f(n) of any computable function from its description in the universal language L and the input n. (Note that such a universal *machine*, should be describable itself by an expression in the universal language. We will come back on this later). Now the question is: Is there an universal language? Is there a universal machine? Is that an obvious question? Definitions like above are not proof of existence. Traditionnaly here I do sometimes present a proof, by diagonalization, that there are no universal machine, and ask the student to find possible errors. Here I will NOT proceed like that and proceed directly instead. For this I will first consider the problem of the cardinality of the set of computable functions, and then provide more definitions. The cardinality of the set of computable functions. Well, if L is a language, it has a finite alphabet A. Then, the subset of its unambiguous expressions (for the instruction) is a subset of the set of all its finite expressions, which we have seen to be enumerable. So the set of computable functions from N to N is enumerable. By Cantor, the set of functions from N to N is not enumerable: thus there are drastically more uncomputable functions than computable functions. Definition: Perfect Universal Machine (or Language): I will say that a universal machine (or language) is perfect, or secure, if the machine computes (or the language defines) only computable functions from N to N. By universality such a machine computes all computable functions from N to N. By security or perfection, such machine computes thus all and only all computable functions from N to N. By the definition of a function from N to N (in a preceding post), this means that such a universal secure machine will, on any unambiguous expression representing its instructions, output a value f(n) for any n, after a finite time. So a perfect universal machine, when following its instruction, never crash, by which I mean going in some loop or infinite task, well, that is, loosing the contact with the user or some neighborhood. Fundamental Theorem 1 : there are no *secure* universal machine. All universal machine, if there is ever one, have to be imperfect. Proof (reductio ad absurdo) Suppose there is a secure universal machine M. The set of expressions it can compute provide a secure universal language L. That set is not only enumerable (given that it is a subset of an enumerable set) but above all, it can be enumerated effectively (by the "ashole"). Indeed the set of all unambiguous expressions, which, by perfection, describes computable functions from N to N, is enumerable by the method described above. Assuming the existence of such an universal secure language, we can effectively enumerate all the computable functions from N to N: f_1 f_2 f_3 f_4 f_5 f_6 f_7 f_8 ... where f_i represents the function computed by the i-th expression. But then the function g defined on each n by g(n) = f_n (n) + 1 is a computable function from N to N. To compute g on 777, for example, search the 777th expression in L by the method above, and apply it on 777, then add 1. But g cannot be computed by the secure universal machine M: indeed, if M compute g, it means there is an expression in L explaining how to compute g, and thus there is a k such that g = f_k, but then, applying g on its number: g(k) = f_k (k) on one hand, (presence of f_k in the list by universality) and g(k) = f_k(k) + 1 on the other hand, by definition of g. That is f_(k) = f_k (k) + 1 But the machine never crashes and computes all and only all functions from N to N, so f_k(k) is a number, so I can substract it on both sides, giving 0 = 1. Contradiction. QED. Remarks: the proof looks like Cantor proof that N^N is not enumerable. Here we know at the start that N^N, once restricted to computable functions, is enumerable. So if we know that a machine is a secure machine, we know that (by definition) all its expression defines functions from N to N, so we know that the machine cannot be universal. If we believe that a machine is a universal, then we can deduce two things: it has to compute some other beats Bs. Then, no set of instruction can for sure distinguish the ... instructions defining functions from N to N and the Bs. Proof: from such a set of instruction you could securized the universal machine, and get a perfecr one, which is impossible by the 1. Any machine M is left with a choice: security or universality, if that exists. But never both! But does a universal language, and its corresponding universal (and thus insecure) machine, really exist? We still don't know that! That means: does it exist a machine computing all computable functions? Equivalently: does it exist a universal language in which all computable function can be described by an expression. Of course now we know that if such a universal machine exists, it will be insecure and will compute, not just all computable functions from N to N, but also other sort of beast. So, as you know, Church did *define* a computable function by a function computable by a lambda expression, in its conversion calculus. Kleene tought it could refute Church's pretension of universality, by *diagonalising* against the set of lambda expressions. Let us look what happens. We don't have to define the lambda expressions or any other candidate to universality to make the following reasoning, which is the same as above, yet in a different context again! We are now in the context of someone presenting us with a well specified language L and pretending it is universal: it does compute all computable functions from N to N, he says! Now, the unambiguous expressions U_i of the language L * can* again be effectively enumerated: U_1 U_2 U_3 U_4 U_5 ... Each expression like that denotes now either a computable function from N to N, or as we have to expect something else. And we have to expect they are no computable means to distinguish which U_i represents functions from N to N, and which represents the other beast. Now, the only thing which can happen when following instruction and not giving a number as output, in this case, is that the process of computation run for ever. Due to this, we have an argument for the consistency of Church thesis. Indeed, the diagonalisation above, where now the f_i are the *partial computable functions*, meaning they are from N to N, OR from a subset of N to N, does no more lead to a contradiction. That f_i is the perhaps total perhaps not, function computed by the U_i: f_1 f_2 f_3 f_4 f_5 f_6 f_7 f_8 Yes the function g defined, (but no more necessarily on each n) by g(n) = f_n (n) + 1 can be represented by an expression in the language. So there is a k such that g = f_k indeed. And thus g(k) = f_k(k), and g(k) = f_k(k)+1 Right. So what happens if the universal machine compute g(k) ? Well, in the computer jargon, the machine crash. The poor humble creature go in loop, or in some infinite task without ever any thought for the user until this one reboot the system. But thanks to that crashing, Church thesis remains consistent. I have to go ... Please ask questions. By experience I know this can be confusing: we do always the same diagonalisation, and get different results. Of course the premises are different. I let you think a bit, before resuming and proceeding trough. Please, ask questions if anything remains unclear. The motivation is that a Lobian Machine will be mainly a sort of enlightened universal machine, i.e. a universal machine knowing that she is universal. "knowing" in a very weak and technical sense which will be made precise in due course. 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 -~----------~----~----~----~------~----~------~--~---