Hi David, Mirek, Tom, Barry and All,

In the preceding post, I gave you an informal proof in naïve set theory 
that the set of functions from N to N was not enumerable.

Note: the preceding post =

It is not in my intention at all to convince you that Cantor's result 
is true. A problem which occurs is the many invocation of Gods. Cantor 
himself will hide paradoxes and also will discuss with theologians on 
those problems.

Today we know Cantor's theorem is provable in reasonably sound accounts 
of sets, like Zermelo Fraenkel Set Theory, ZF.

But it is not my purpose to dwelve into set theory. My purpose is 
computability theory.

What happens if we try to restrict ourselves to *computable* functions 
from N to N, instead of *all* functions from N to N.

In this case we would not be obliged to refer to Gods, those who were 
able to "see" an arbitrary and infinite long sequence of numbers.

But we get somehow the anti-problem. How to define what is a computable 

We can hardly be satisfied by an anti-solution like:

Anti-definition: A function from N to N is computable if it can be 
computed without any invocation to any Gods.

So we have to find a more positive definition, and invoke *finite and 
humble* creature instead. Humble, because we have to be sure not 
attributing to them any magical and hard to define qualities like 
cleverness, intelligence, intuition or any god-like predicate.

So here is an informal "definition" of what is an (intuitively) 
computable function from N to N.

"Definition": a function f is computable if there is a finite set of 
instructions such that a complete asshole can, on each n compute in a 
finite time the result f(n).

OK. "complete asshole" is probably a bit popular, and I will use the 
adverb "unambiguously" instead.

Also, what are the instructions? Whatever they are, they have to be 
described in some language, which has to be unambiguous (understandable 
by that humble finite creature).

So here is a better "definition" of what is a computable function from 
N to N.

A function f from N to N is said (intuitively) computable if there is a 
language L in which it is possible to describe unambiguously through a 
finite expression in L how, for any n to compute f(n) in a finite time.

The finite expression are intended to express the instructions. A 
language is the given of a finite alphabet A, and a subset L of 
unambiguous expressions. If A is a finite or enumerable alphabet, then 
I will denote by A°, the set of finite expressions written with the 
alphabet A. I recall that If A is finite or enumerable, then A° is 
enumerable too. Indeed, you can put an alphabetical order on all 
sequences of length 1, and then of length 2, etc.
Exemple: A = {S, K, (, ) }
Ordering the finite expressions, using the order "K < S <  ( < )" on 
the alphabet:

finite expressions=
K, S, (, ),     [length one]
KK, KS, K(, K), SK, SS, S(, S), (K, (S, ((, (), )K, )S, )(, )),    
[length two]
KKK , ...  [length 3]
KKKK, ... [length 4]

Note that ")))KK))S())" is a finite expression on the alphabet. It is 
does not refer to a combinator, which are associated only to 
well-formed expressions, like, if you remember,  (K(SK)), or 
((S(KS))K), making a subset of the set of all (finite) expressions.

Now, two fundamental definitions:

Universal Language:  A language L is universal if all computable 
functions (from N to N) can be described in L.

Universal Machine: A machine M is universal if M understands L, and so 
M can actually compute the value f(n) of any computable function from 
its description in the universal language L and the input n.
(Note that  such a universal *machine*, should be describable itself by 
an expression in the universal language. We will come back on this 

Now the question is: Is there an universal language?  Is there a 
universal machine?

Is that an obvious question? Definitions like above are not proof of 

Traditionnaly here I do sometimes present a proof, by diagonalization, 
that there are no universal machine, and ask the student to find 
possible errors. Here I will NOT proceed like that and proceed directly 

For this I will first consider the problem of the cardinality of the 
set of computable functions, and then provide more definitions.

The cardinality of the set of computable functions.

Well, if L is a language, it has a finite alphabet A. Then, the subset 
of its unambiguous expressions (for the instruction) is a subset of the 
set of all its finite expressions, which we have seen to be enumerable. 
So the set of computable functions from N to N is enumerable. By 
Cantor, the set of functions from N to N is not enumerable: thus there 
are drastically more uncomputable functions than computable functions.

Definition: Perfect Universal Machine (or Language):  I will say that a 
universal machine (or language) is perfect, or secure, if the machine 
computes (or the language defines) only computable functions from N to 

By universality such a machine computes all computable functions from N 
to N.  By security or perfection, such machine computes thus all and 
only all computable functions from N to N. By the definition of a 
function from N to N (in a preceding post), this means that such a 
universal secure machine will, on any unambiguous expression 
representing its instructions, output a value f(n) for any n, after a 
finite time.
So a perfect universal machine, when following its instruction, never 
crash, by which I mean going in some loop or infinite task, well, that 
is, loosing the contact with the user or some neighborhood.

Fundamental Theorem 1 : there are no *secure* universal machine.  All 
universal machine, if there is ever one, have to be imperfect.

Proof (reductio ad absurdo)

Suppose there is a secure universal machine M. The set of expressions 
it can compute provide a secure universal language L. That set is not 
only enumerable (given that it is a subset of an enumerable set) but 
above all, it can be enumerated effectively (by the "ashole"). Indeed 
the set of all unambiguous expressions, which, by perfection, describes 
computable functions from N to N,  is enumerable  by the method 
described above. Assuming the existence of such an universal secure 
language, we can effectively enumerate all the computable functions 
from N to N: f_1 f_2  f_3  f_4  f_5  f_6  f_7  f_8 ... where f_i 
represents the function computed by the i-th expression.

But then the function g defined on each n by

g(n) = f_n (n) + 1

is  a computable function from N to N. To compute g on 777, for 
example, search the 777th expression in L by the method above, and 
apply it on 777, then add 1.

But g cannot be computed by the secure universal machine M: indeed, if 
M compute g, it means there is an expression in L explaining how to 
compute g, and thus there is a k such that g = f_k, but then, applying 
g on its number:

g(k) = f_k (k) on one hand, (presence of f_k in the list by 
universality) and

g(k) = f_k(k) + 1 on the other hand, by definition of g.

That is f_(k) = f_k (k) + 1

But the machine never crashes and computes all and only all functions 
from N to N, so f_k(k) is a number, so I can substract it on both 
sides, giving 0 = 1. Contradiction. QED.

Remarks: the proof looks like Cantor proof that N^N is not enumerable. 
Here we know at the start that N^N, once restricted to computable 
functions, is enumerable. So if we know that a machine is a secure 
machine, we know that (by definition) all its expression defines 
functions from N to N, so we know that the machine cannot be universal. 
If we believe that a machine is a universal, then we can deduce two 
things: it has to compute some other beats Bs. Then, no set of 
instruction can for sure distinguish the  ... instructions defining 
functions from N to N and the Bs.
Proof: from such a set of instruction you could securized the universal 
machine, and get a perfecr one, which is impossible by the 1.

Any machine M is left with a choice: security or universality, if that 
exists. But never both!

But does a universal language, and its corresponding universal (and 
thus insecure) machine, really exist?

We still don't know that!

That means: does it exist a machine computing all computable functions? 
Equivalently: does it exist a universal language in which all 
computable function can be described by an expression.

Of course now we know that if such a universal machine exists, it will 
be insecure and will compute, not just all computable functions from N 
to N, but also other sort of beast.

So, as you know, Church did *define* a computable function by a 
function computable by a lambda expression, in its conversion calculus.

Kleene tought it could refute Church's pretension of universality, by 
*diagonalising* against the set of lambda expressions.

Let us look what happens. We don't have to define the lambda 
expressions or any other candidate to universality to make the 
following reasoning, which is the same as above, yet in a different 
context again! We are now in the context of someone presenting us with 
a well specified language L and pretending it is universal: it does 
compute all computable functions from N to N, he says!

Now, the unambiguous expressions U_i of the language L * can* again be 
effectively enumerated:

U_1  U_2  U_3  U_4 U_5 ...

Each expression like that denotes now either a computable function from 
N to N, or as we have to expect something else. And we have to expect 
they are no computable means to distinguish which U_i represents 
functions from N to N, and which represents the other beast. Now, the 
only thing which can happen when following instruction and not giving a 
number as output, in this case, is that the process of computation run 
for ever.

Due to this, we have an argument for the consistency of Church thesis. 
Indeed, the diagonalisation above, where now the f_i are the *partial 
computable functions*, meaning they are from N to N, OR from a subset 
of N to N, does no more lead to a contradiction. That f_i is the 
perhaps total perhaps not, function computed by the U_i:

f_1 f_2  f_3  f_4  f_5  f_6  f_7  f_8

Yes the function g defined, (but no more necessarily on each n) by

g(n) = f_n (n) + 1

  can be represented by an expression in the language. So there is a k 
such that g = f_k indeed.

And thus g(k) = f_k(k),

and g(k) = f_k(k)+1

Right. So what happens if the universal machine compute g(k) ?

Well, in the computer jargon, the machine crash. The poor humble 
creature go in loop, or in some infinite task without ever any thought 
for the user until this one reboot the system. But thanks to that 
crashing, Church thesis remains consistent.

I have to go ...

Please ask questions. By experience I know this can be confusing: we do 
always the same diagonalisation, and get different results. Of course 
the premises are different. I let you think a bit, before resuming and 
proceeding trough. Please, ask questions if anything remains unclear.

The motivation is that a Lobian Machine will be mainly a sort of 
enlightened universal machine, i.e. a universal machine knowing that 
she is universal. "knowing" in a very weak and technical sense which 
will be made precise in due course.



You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To post to this group, send email to [EMAIL PROTECTED]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at 

Reply via email to