To all victims of certainties.
Hi all,
Thanks for those who makes out-of-line comments of
Diagonalisation 1.
I give the two promised solutions.
If you have forget the problem, please reread
http://www.escribe.com/science/theory/m3079.html
The long term goal of this thread is G*, I recall.
Apology for those who would know those things.
The others can take their time (it's a long post)
for being sure everything is clear.
Any questions and/or remarks are welcome, 'course.
***
I rewrite the paradox (quoting myself):
>I will say that a function f is computable if there is
>a well defined formal language FL in which I can explained
>non ambiguously how to compute f on arbitrary input (number).
I recall the functions are supposed to be functions whith
inputs in N and outputs in N. The functions are supposed to be
defined on *any* natural numbers.
>I must be able to recognise if an expression in my language
>is a grammaticaly correct definition of a function, that is
>syntax error must be recoverable.
>All expression in the language must be of finite length, and
>the alphabet (the set of symbols) of the language is asked to
>be finite.
>Now all finite strings, a fortiori the grammatically correct
>one, form a countable set. Just use the lexicographic order
>defined above.
>
>So the set of function computable with FL is countable.
>A synonym of countable is *enumerable*, and is used by
>computer scientist, so I will also use it.
>
>So I can enumerate the functions computable with FL, that is
>I can put them in sequence like f_0, f_1, f_2, f_3, ...
>going through all functions computable in or with FL.
Sure.
>Let us consider the function g defined again by
>
> g(n) = f_n(n) + 1
>
>Now, g is not only well defined, but is even computable.
Because each f_i are. It follows from our hypothesis. Of course
adding one is a computable operation.
>To compute it on n, just search in the enumeration f_i the nth
>function, apply it to n (this gives an answer because the f_i
>are computable) and add 1.
So g is indeed computable.
>So, there is a number k such that g = f_k, but then, again
>
> g(k) = f_k(k) = f_k(k) + 1
>
>But f_k(k) is a well defined number (f_k is computable), and
>no numbers can be equal to "itself + 1". Contradiction.
>Could the set of computable functions in FL be uncountable, after
>all, or is g not expressible in FL, or what?
The expression "computable functions in FL" is an abbreviation
for the "computable functions *definissable* by an expression (a
string, a list, a number) in FL".
So, obviously, through the lexical ordering, the set of functions
computable in FL is countable, (enumerable, bijective with N).
By the same token the function g is obviously computable.
Yet, we have not prove that this set is uncountable.
So what?
For g being computable, it was important that the f_i could
be enumerated (unlike the f_i in Cantor proof which rely in
arbitrary order in Plato heaven).
THE FIRST WAY TO AVOID THE PARADOX
1 The first way to avoid the paradox consist in
precising our definition of LF: a formal language
defining computable function from N to N, and defining
*only* computable function.
That is we suppose all expressions in LF computes only
functions defined on all their arguments, the programs or
the machines computing them stop for any arguments. LF
defines only so called *total* computable functions.
In that case, (unless you believe 1 = 0), you are forced
to believe that the reasoning above shows only that the
function g, although total computable, is not LF expressible.
You cannot defined it in LF. LF has failed to capture the set
of *all* total computable functions. There is no k such that
the diagonal function g = f_k, f_k enumerating the LF-computable
functions. This gives:
THEOREM 1 there is no universal language capable of defining
all and only all total computable functions.
In term of the machine computing the functions described in
a language:
THEOREM 1 there is no universal machine computing all and only
all total computable functions.
In term of the enumeration of the f_i, the THEOREM 1, looks
like CANTOR theorem:
THEOREM 1 the set of machines (programs, expressions),
computing (programming, defining), total computable function
is not algorithmically countable. The logician say: not
recursively enumerable.
You cannot generate all and only all names of the total computable
functions.
Algebraist like to say a set is *closed* for an operation defined
in that set when the operation never leads ouside the set.
So an algebraic version of THEOREM 1 is
THEOREM 1 The set of (expression computing) all and only all
total computable function is not closed for the diagonalisation
operation.
CONSEQUENCES If you have a language L computing only total
computable functions, then you can build a new total computable
function outside the class defined by L.
This gives a tool for the refutation of all naive Pythagorian
School, believing that they can capture formally the set
of all and only all total computable functions.
Exemple: Suppose a naive Pythagorician believe that all
computable functions can be put into the form of the class of
functions defined by a positive polynomial: like "5x^3 + 2x^2 + 3".
The set of those polynomes is obviously recursively enumerable.
Let p_i be an enumeration of the polynomes. So the function
g such that g(n) = p_n(n) + 1 gives a non positive polynomial
computable function. Refuting the naive Pythagorician.
You can add g to the list of polynoms, of course, and you get
a new class of total computable functions, so that you can
diagonalise it again, and again, and again ..., and then
again again, ... iterating in the transfinite, for better
sub-approximations of the set of the everywhere defined machines.
THE SECOND WAY TO AVOID THE PARADOX
The THEOREM 1 says that you cannot find a universal language
capable of defining all and only all total computable functions.
A question remains: would it be possible that there exists a
universal language capable of defining all total computable
functions? (dropping the "and *only* all").
Well, there is a thesis for that effect. Indeed all attempt
of defining all computable functions leads to the same
class of computable functions (from Babbage, Post, Church, Turing,
... to Java, C++, ... to Deutsch Universal Quantum Machines).
So a version of Church thesis is that FORTRAN (let us say) is
a language defining all total computable functions (but then
by theorem 1, computing not only those total functions).
CHURCH THESIS There exists a universal language.
(and FORTRAN is the one).
In term of machine : There exits a universal machine
(and the interpreter LISP is the one).
As a consequence of theorem 1, we can expect that if such
a universal language exists (i.e. Church thesis) then it will
defined all total functions, but certainly not all *and only*
all total functions.
That is, it will defined all total functions *and other sort
of beast* as a necessary gift.
So the second way to avoid the paradox consist in dropping the
"and only" in "language capable of defining all and only all
total computable functions". We precise our formal system in
a more liberal way by dropping the totality constraint.
What does happen with the diagonalisation, with such a universal
language? (Let us take FORTRAN for fixing the idea).
Well, you certainly can generate mechanically (recursively enumerate)
the list of all programs FORTRAN, still by lexicographical order.
So let F_i be an enumeration of the fortran programs.
The diagonal function g, such that g(n) = F_n(n) + 1, is certainly
programmable, just because you can write a generator of the F_i,
and an applicator of the F_i on an input i, and you have an adder
for the "+ 1".
So there is certainly a F_k such that g = F_k.
So what? What will happen when you run g_k(k)?
One thing is sure, if the machine stop on g_k(k), then
g_k(k) = g_k(k) + 1. So the machine will simply not stop!
In the computer scientist jargon we say that the universal
machine crash. The machine get on his/her/it way, remain
silent, and simply does not stop.
This proves g is undefined on k, its own number in the
enumeration of the programs. g is not a total computable
functions (being not defined everywhere
So we get
THEOREM 2 All languages (machines) defining (computing)
all total computable functions, defined automatically
a vaster set containing *partial* computable functions.
In particular all diagonal functions g are undefined
on their own code.
We get immediately (with Church Thesis), the insolubility
result:
THEOREM 3 there is no program (machines) capable of deciding if
the code of F_i correspond to a total function or not.
Proof: Because, if that was the case, you could mechanically
extract a recursive enumeration of the total computable
function by deleting the code of the non total functions in
the enumeration of the F_i. (contradicting theorem 1).
THEOREM 4 (Incompleteness):
Any theory in which you can represent the (total or partial)
computable functions cannot be complete.
That is for any such theory you can find true proposition which
cannot be proved in the theory.
Proof:
If the theory was complete, that is capable of proving all
true propositions expressible in its language (supposed being
enough rich for representing the partial recursive functions),
then you could use the theory again for extracting a recursive
enumeration
of the total computable functions (by deleting again the code of
the non total functions in the enumeration of the F_i (and this
you do by testing the proposition "F_i is not-total" in your
complete theory))).
(Peano Arithmetic or Zermelo Fraenkel Set Theory are exemples of such
theories, i.e. rich enough for representing the F_i. But showing
this, although easy, is tedious, a little like programming in assembly
language). Any axiomatisable extension of those theories succumb
the same godelian incompleteness fate.
Bruno
Received on Thu Oct 18 2001 - 10:27:38 PDT