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?



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