On 16 Sep 2009, at 18:12, Bruno Marchal wrote:

## Advertising

> > > 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. 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. 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? 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 -~----------~----~----~----~------~----~------~--~---