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.

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

Reply via email to