Re: The seven step series

```Hi,

I sum up the definition and results seen so far.```
```
N = {0, 1, 2, ...}, the set of natural numbers (also called positive
integers).

N^N = {f such that f is a function from N to N} = the set of functions
from N to N.

Universal language: a language in which we can describe formally how
to compute any intuitively computable functions.

Weak Church thesis: there exists a universal language.

Church thesis: lambda-calculus is universal.
Turing thesis: the Turing machine specification language is universal
Markov thesis: the Markov formalism is universal
Post laws: production system is universal
Beniov-Deutsch: quantum turing machine is universal
etc.

All such thesis have been proved equivalent. Instead of lambda
calculus, turing machines, Markov systems or Post production
FORTRAN, LISP, Prolog, C++, etc.). Thanks to Church thesis, I will not
need to actually use any of those formal systems, and what we prove
will be true for any of them. Actually I am using only the weak Church
thesis.

Computable = programmable in my favorite universal language (this
definition use the (weak) Church thesis)

N^N-comp = {f such that f is a computable function from N to N}

N^N-comp+ = {f such that f is a computable function from a subset of N
to N} = {f such that f is a partial computable function}

Note that N is a particular subset of N; so a computable function
(defined on the whole N) is a particular case of a partial function,
so N^N-comp is included in N^N-comp+

Training exercise: try to reprove for your own benefit that:

N^N is non enumerable

N^N-comp is enumerable

N^N-comp is non computably enumerable (the bijection exists but is not
computable)

N^N-comp+ is enumerable

N^N-comp+ is computably enumerable (allowing repetition: different
numbers can correspond to the same function).

Bruno

On 21 Sep 2009, at 19:47, Bruno Marchal wrote:

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

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