On 18 Sep 2009, at 17:00, I wrote:


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


OK. I have defined a computable function (from N to N) as being a  
function which can computed from a finite description in some  
language, and this makes them intuitively enumerable. The admittedly  
vague idea here, is that any set of finite things is either finite or  
enumerable.

But of course, this is not entirely convincing, we could use a non  
enumerable set to multiply non enumerably finite beings, and a case  
could be made that if we allow a non enumerable set of languages, or a  
non enumerable set of beings understanding those languages, we could  
find for *any* functions, a language defining that function or a being  
computing that function, making all function computable, by some  
being, and this would make the notion of computability relative if not  
trivial.

Let me do something which illustrates this in a non trivial way,  
though, but which relies on what I have already said about the  
ordinals some times ago. I will repeat the definition.

I will write as if I was criticizing myself.

The notion of computable function does not make sense, by the argument  
above. To define a notion of computability, you have to define first a  
fixed language L, in which the correct grammatical expressions will be  
definition of functions, that is will correspond to the description of  
how to compute those functions, on each of their arguments. In that  
case, the f_n are clearly *computably* enumerable. The bijection n ->  
f_n has to be computable, then. But in that case,  the g function,   
the one defined by g(n) = f_n(n) + 1,  is clearly computable, and the  
Cantor-like diagonal argument just showed that that g is NOT  
*definable* in the language L. L cannot be universal.

And given that the argument seems not to depend on which language L,  
it looks like we have proved that there is no universal language.

After all I could build a new language now, by adding a primitive  
computing g to the L language. Diagonalizing again would provide a new  
function g2, which we can add as new primitive again, and so one,  
getting

L, g, g2, g3, g4, ...

I could even build a more powerful language by adding a primitive  
which computes all gi automatically, giving a new primitive, that I  
can add to L, so that this process can be extended into the  
constructive tranfinite (if you remember the post on the growing  
functions, and the ordinals).

Could such a process converge toward a language computing all  
computable functions? That is, is there a universal language in which  
we can define all computable function?

It will not converge for any effective, or constructive of computable  
ordinal, because if it does, we would get a computable bijection from  
N to N^N-comp. This we already know cannot exist, the diagonal leads  
to 0 = 1.

Could it converge on non effective ordinals. Yes, and this can be used  
to make precise the idea that by liberalizing enough the notion of  
language we can define universal language. But using a non effective  
ordinal to define the notion of computable would illustrate only how  
non universal that notion could be.

All this to make more amazing the seemingly naive proposal by Church,  
to Kleene, for a definition of computability:

A function is computable only if I can described in my language (which  
was lambda calculus, the famous cousin of the combinators).

Kleene will try to diagonalize on Church functions, but will not  
succeed. The reason is that Church language defines a vaster class of  
functions that N^N-comp. Those will be noted phi_n, to distinguish  
them from the computable functions. That class is computably  
enumerable, the bijection n ==> phi_n is computable, but not all are  
computable functions from N to N, so may be undefined. This saves the  
language from the diagonal: now g can belong to the class, and so g  
will be some f_k, and f_k(k) will be equal f_k(k)+1. But f_k(k) will  
be undefined, the computation of f_k(k) will run forever, the computer  
is crashing, if you want.

  If the language L is universal, it defines all computable functions  
from N to N. This means that in the computable enumeration of the  
partial computable functions from N to N., phi_n, that is

phi_1, phi_2, phi_3, ....

All the f_n will appear, here and there. The f_n constitute a  
enumerable subset of the phi_i. But certainly not a computably  
enumerable subset. If L is universal, then there is absolutely no  
algorithm for telling, in general, if phi_j is a total function or a  
strictly partial function. If that would exist, we would be able to  
effectively filtrated the f_n from the phi_n, to provide an effective  
enumeration of all N^N-comp, which gives 0 = 1.

Note this. Here we have used arithmetical realism. If you remember, it  
was the use of the excluded middle which provides me the tool to prove  
that there are irrational numbers x and y such that x^y  is rational,  
showing you only that the solution was in the set {sqrt(2)^sqrt(2),  
(sqrt(2)^sqrt(2))^sqrt(2)}. Here, by assuming a language L is  
universal (for N^N-comp) we have to accept that the functions f_n are  
non constructively dispersed in a vaster set: the phi_i. The  
universality of the language makes that dispersion absolutely non  
computable. We see that the price of universality is the unability to  
compute definable feature of nameable of objects, and unpredictible  
behavior.

Is Church thesis true?

There are four deep reasons to find CT rather plausible.

1) The closure of the class of partial computable functions for the  
diagonalization.
2) All attempts, some very independent, some very different, to define  
a general notion of computability has always given the same class N^N- 
comp.
3) Anything proved comp-insoluble remains unsolved
4) the common impression we do share the elementary intuition of  
finite things and of applying finite things on themselves repetitively  
up to a possible but not guarantied satisfaction.

The rational x^y disperse itself non constructively in  
{sqrt(2)^sqrt(2), (sqrt(2)^sqrt(2))^sqrt(2)}, but I told you that  
complex mathematics can show that the precise solution is  
sqrt(2)^sqrt(2). But the non constructive dispersion of the f_n in the  
phi_n cannot be dispensed with. The diagonal above shows exactly that,  
and that is what makes arithmetical realism indispensable if we want a  
notion of universality. Here realism really means an acceptance of a  
universal modesty about our ways to separate the f_n from the phi_n,  
and many propositions relating those objects and the machines which  
compute them.

Let <x,y> represents a the image of a computable bijection from NXN to  
N, so that we can code a couple of numbers by one number. Let phi_n be  
a "universal enumeration" (that is an enumeration of all partial  
computable functions)
I will say that a number u is universal, if phi_u(<x,y>) = phi_x(y).

I have to go. Ask question, and don't worry if it seems difficult. It  
is difficult.  Conceptually, just not for the notations and the typo  
errors .... I will sum up soon all what the same diagonalization proved.

Diagonalization and non constructive reasonings are the key tools for  
the study of machine's theology and machine's machine's theology ....   
You can see this as the self-study of an abyssal intrinsic ignorance,  
with the discovery that it is related to life forms and many other  
unknowns and mysteries ....

Questions, remarks?

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