Hi, I said:

## Advertising

<< > Exercise: > What is wrong with the following argument. (I recall that by > definition a function from N to N is defined on all natural numbers). > > (false) theorem: the set of computable functions from N to N is not > enumerable. > (erroneous) proof: let us suppose (by absurdum) that the set of > computable functions from N to N is enumerable. Thus there exist an > enumeration f_1, f_2, f_3, ... f_i, .... of the computable functions > from N to N. But then I can define the following computable function > g, from N to N, by: > > g(n) = f_n(n) + 1 > > g is computable: to compute it just search in the enumeration the > function f_n, which is computable, and then apply it on n, and then > add 1. > But then g has to be in that enumeration f_i of the computable > function. Thus there is a k such that g = f_k. In particular g(k) = > f_k(k). But g(k) = f_k(k) + 1, by definition of g. Thus f_k(k) = > f_k(k)+1. And the f_i are computable functions, so f_k(k) is a well > defined number, which I can subtract on the left and the right side of > f_k(k) = f_k(k)+1, giving 0 = 1. Contradiction. So the set of > computable functions from N to N is not enumerable. > > What is wrong? We know that the set of computable function has to be > enumerable, because "computable" means we can describe how to compute > the function in a finite expression in some language, and the set of > all finite expressions has been shown enumerable. So what happens? >> Answer : > > (false) theorem: the set of computable > > functions from N to N is not enumerable. Yes that is wrong. The set of computable functions from N to N is enumerable. > > (erroneous) proof: OK, let us see where we are wrong. > > let us suppose (by absurdum) that the set of > > computable functions from N to N is enumerable. OK. (although we already know that the set of computable functions from N to N is enumerable, here it is the intended absurd hypothesis). > > Thus there exist an > > enumeration f_1, f_2, f_3, ... f_i, .... of > > the computable functions from N to N. Yes, sure. That is what is meant by enumerable. > > But then I can define the following > > computable function g, from N to N, by: > > > g(n) = f_n(n) + 1 > > > g is computable: to compute it just search > >in the enumeration the function f_n, which is > >computable, and then apply it on n, and then add 1. Here is the error. From the existence of an enumeration f_0, f_1, .... of the computable functions from N to N, the existence of a mechanical, algorithmic, computable enumeration of those f_i does not follow. And this is needed for making g computable from N to N. Although each f_i is a computable function, it is the correspondence i ----- f_i which is not computable, making g NOT computable either. There is indeed a bijection between N and the set of computable functions from N to N, but that bijection is not computable. It has to be! All right? GENERAL COMMENT: What are the lessons of those diagonalizations? First I will assume a weak form of Church thesis WCT: WCT: There exist a universal language (machine) By definition, in such language, all computable functions have an expression understandable by the corresponding universal machine. We can then enumerate the expressions in the universal language: F_1 F_2 F_3, ..., but, by the theorem above, the list of those expressions has to enumerate a larger set than the set of computable functions from N to N. We get actually an enumeration of all computable functions from some subset of N to N. The so-called computable partial functions from N to N. A function from N to N is a particular case of a function from some subset of N to N, given that N is a subset of N (!), so the class of the functions from N to N is included in the class of the partial functions from N to N. If the domain of definition of f is different from N I will say that f is strictly partial. To emphasize that f is not strictly partial, I will say that f is total: it just means f is defined on all n. We learn more: there is no expression in the universal language capable of deciding if n is the code of a f_n being total or strictly partial. For if that would exist then we would have a procedure for extracting from the F_i the f_i, making the function g above computable, and we know it can't. We also get a very strong incompleness theorem: for all effective theory there are statement, like "n codes a total function" which are undecidable in the theory. Indeed, if there was an effective theory capable of deciding all statements of the type :"n codes a total function" then such a theory would provide a way to build an expression in the language making possible to enumerate the total computable functions, which can't be. So, at a fundamental level, it shows that any machine, capable of changing itself, has to choose between universality and security. If you want all the total computable functions, not only your machine can not stop on some inputs, but it does it sometimes in a non effectively provable of verifiable way. Giving the enumerabilty of the (total or not) computable functions, which follows directly from CT, Cantor diagonalization already shows the existence of non computable functions from N to N. Indeed most of them are not computable. The set of computable functions is enumerable but the set of all functions is not enumerable, making the set of uncomputable functions from N to N not enumerable. In that sense there are far more non computable functions from N to N than computable one. But the effective diagonalization, made on the partial computable functions shows, with CT, that the function TOT, from N to N, such that TOT(n) = 1 if F_n is total, and 0 if not, is not computable. That, is, we get the uncomputability of precise functions and predicates bearing in computer science (and by Godel's arithmetization, already in number theory). ... IS WCT true? Well CT -> WCT, and there are many evidences for CT. (ASAP ...) Hope this provide some help. Happy new year, 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 -~----------~----~----~----~------~----~------~--~---