I sum up the definition and results seen so far.

N = {0, 1, 2, ...}, the set of natural numbers (also called positive  

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

All such thesis have been proved equivalent. Instead of lambda  
calculus, turing machines, Markov systems or Post production  
rules, ... you can use your favorite programming language (ADA,  
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  

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  

N^N-comp+ is enumerable

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


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


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