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 00 = 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.domain.name.hidden
To unsubscribe from this group, send email to everything-list+unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
Received on Fri Sep 18 2009 - 17:00:24 PDT