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 00 = 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.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 Mon Sep 21 2009 - 19:47:48 PDT