I give the answer.

On 17 Sep 2009, at 16:27, Bruno Marchal wrote: > > On 16 Sep 2009, at 18:12, Bruno Marchal wrote: > > >> >> >> If it is OK, in the next post we begin to address the computability >> issue. I give you an anticipative exercise or subject reflection. >> This is a deep exercise. Its solution leads to the notion of >> universal function and universal number/machine. More exactly it >> leads to an evaluation of the price we have to pay if we want to >> believe in that notion. >> >> We have seen that the set N^N is non enumerable. This means it is a >> *huge* infinite set, compared to N. >> We could argue that there are too much functions in that set. Most >> usual functions that we encounter in real life, both in math and >> physics, seem to share the property that they are computable. This >> means that we can write some rules or recipe for computing them, or >> that, may be, we can build some mechanical device capable of >> computing them. The natural functions we met were the exponential >> f(n) = 2^n, or the factorial(n), or similars. It seems that we can >> explain to each other how to compute them, and you already known >> that we can build machines computing them indeed. So, we could >> decide, if only to avoid those big infinities, to restrict ourself >> on the computable functions. Let us define N^N-comp to be the set >> of computable functions from N to N. >> >> The question is: is there a bijection from N to N^N-comp ? > > > This is a tricky question. > > I give you an argument that there is a bijection between N and N^N- > comp. Followed by an argument that there is no bijection between N > and N^N-comp. > > Which one is wrong? > > > 1) A "proof" that N^N-comp is enumerable. > > I said that a function from N to N, is computable (and thus in N^N- > comp), if there is a recipe explaining how to compute it. > But this means that there has to be a language in which we can > describe or encode that explanation. A language is a set of finite > expressions build from some finite alphabet. But we have seen that > the set of finite expressions build on an alphabet (which is always > a finite set) is enumerable. Those expressions, corresponding to the > explanation describing the recipe for a computable function, will > constitute a subset of the set of all expressions, and is thus > enumerable. So N^N-comp is enumerable. That is correct. N^N-comp is enumerable. > > 2) A "proof" that N^N-comp is NOT enumerable. > > Suppose N^N-comp is enumerable, and let f_n be such an enumeration, > with n in {0, 1, 2, ...}. Consider the diagonal function g defined > by g(n) = f_n(n) + 1. All f_n are computable, and surely "+ 1" is > computable, so g is a computable function. That is wrong. It is true that all the f_n are computable, and that "+ 1" is computable. But to compute g on n I have to find f_n, and although all f_n are computable, the bijection itself which send n to f_n cannot be computable. Why? Well if it is, given that by the reasoning above shows correctly that N^N-comp is enumerable, what follows would lead to 0 = 1. > But then g has to belong to f_n, which enumerates the computable > functions. So there is a k such that g = f_k. But then g(k) = f_k(k) > = f_k(k) + 1. But f_k is a computable function from N to N, so > f_k(k) is a number, which I can subtract on both side, so 0 = 1. So > N^N^comp is not enumerable. > > Well, there is a problem, isn't it? N^N-comp cannot be both > enumerable and non enumerable. So one of those proofs has to be > wrong. Which one? So it was the second "proof" which was wrong. We have implicitly assumed that the enumeration f_n was a computable enumeration. The reasoning above in "1)" has show that there is a bijection between N and N^N-comp, and not that such an enumeration could be done by a *computable* bijection between N and N^N. We say that the f_n are, although enumerable, not computably enumerable. On the set N^N of all functions from N to N, Cantor diagonal shows that N^N is non enumerable. On the set N-N-comp, the diagonal shows that N^N-comp, although enumerable is non computably enumerable. OK? take the time to swallow this, and ask question if this seems not clear. We are at the crux of the subject. ---------------- Next anticipative exercise. If N^N-comp is not or non *computably* enumerable, so that we cannot enumerate mechanically, using some recipe, the f_n, is there still some hope to develop a *universal* machine, or a *universal* language, or a *universal* dovetailer? all capable of computing ALL computable function? How to escape the diagonal contradiction? We would appreciate that a universal could be able, given the nth "program" (identified by the number n), and the datum m, to compute f_n(n). Indeed that is how we will *define* universal machine. But if the machine cannot find "mechanically" the f_n, what can we do or hope for? What is the price of universality? GĂ¶del's theorem has forced us to abandon the notion of universal provability (in the realm of the relations and functions on numbers), and this results mainly from the use of a diagonal argument 5Godel 1931). So when Church told him that he decided to define computable by the formal language of Lambda-calculus, Kleene thought this was impossible, and that he could by diagonalization refute that universality pretension. But 'overnight', after failing to diagonalize against lambda-calculus, he realize that Church *may* be correct, and he invented the vocable of "Church thesis". CHURCH's (original) thesis: a function from N to N is computable if we can explain in lamdda-calculus how to compute it. What could be so special about Church language that it could define ALL computable functions from N to N, and yet be immune to the diagonal argument? 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@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~----------~----~----~----~------~----~------~--~---