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  

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?



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 
For more options, visit this group at 

Reply via email to