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 =
http://www.mail-archive.com/everything-list.domain.name.hidden/msg14063.html
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
function?
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
later).
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
existence.
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
instead.
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
N.
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.
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 Tue Dec 04 2007 - 09:56:11 PST