Hi,
I said:
<<
> Exercise:
> What is wrong with the following argument. (I recall that by
> definition a function from N to N is defined on all natural numbers).
>
> (false) theorem: the set of computable functions from N to N is not
> enumerable.
> (erroneous) proof: let us suppose (by absurdum) that the set of
> computable functions from N to N is enumerable. Thus there exist an
> enumeration f_1, f_2, f_3, ... f_i, .... of the computable functions
> from N to N. But then I can define the following computable function
> g, from N to N, by:
>
> g(n) = f_n(n) + 1
>
> g is computable: to compute it just search in the enumeration the
> function f_n, which is computable, and then apply it on n, and then
> add 1.
> But then g has to be in that enumeration f_i of the computable
> function. Thus there is a k such that g = f_k. In particular g(k) =
> f_k(k). But g(k) = f_k(k) + 1, by definition of g. Thus f_k(k) =
> f_k(k)+1. And the f_i are computable functions, so f_k(k) is a well
> defined number, which I can subtract on the left and the right side of
> f_k(k) = f_k(k)+1, giving 0 = 1. Contradiction. So the set of
> computable functions from N to N is not enumerable.
>
> What is wrong? We know that the set of computable function has to be
> enumerable, because "computable" means we can describe how to compute
> the function in a finite expression in some language, and the set of
> all finite expressions has been shown enumerable. So what happens?
>>
Answer :
> > (false) theorem: the set of computable
> > functions from N to N is not enumerable.
Yes that is wrong. The set of computable functions from N to N is
enumerable.
> > (erroneous) proof:
OK, let us see where we are wrong.
> > let us suppose (by absurdum) that the set of
> > computable functions from N to N is enumerable.
OK. (although we already know that the set of computable functions from
N to N is enumerable, here it is the intended absurd hypothesis).
> > Thus there exist an
> > enumeration f_1, f_2, f_3, ... f_i, .... of
> > the computable functions from N to N.
Yes, sure. That is what is meant by enumerable.
> > But then I can define the following
> > computable function g, from N to N, by:
>
> > g(n) = f_n(n) + 1
>
> > g is computable: to compute it just search
> >in the enumeration the function f_n, which is
> >computable, and then apply it on n, and then add 1.
Here is the error. From the existence of an enumeration f_0, f_1, ....
of the computable functions from N to N, the existence of a mechanical,
algorithmic, computable enumeration of those f_i does not follow. And
this is needed for making g computable from N to N.
Although each f_i is a computable function, it is the correspondence i
----- f_i which is not computable, making g NOT computable either.
There is indeed a bijection between N and the set of computable
functions from N to N, but that bijection is not computable. It has to
be!
All right?
GENERAL COMMENT:
What are the lessons of those diagonalizations?
First I will assume a weak form of Church thesis WCT:
WCT: There exist a universal language (machine)
By definition, in such language, all computable functions have an
expression understandable by the corresponding universal machine.
We can then enumerate the expressions in the universal language: F_1
F_2 F_3, ..., but, by the theorem above, the list of those expressions
has to enumerate a larger set than the set of computable functions from
N to N. We get actually an enumeration of all computable functions
from some subset of N to N. The so-called computable partial functions
from N to N. A function from N to N is a particular case of a function
from some subset of N to N, given that N is a subset of N (!), so the
class of the functions from N to N is included in the class of the
partial functions from N to N.
If the domain of definition of f is different from N I will say that f
is strictly partial.
To emphasize that f is not strictly partial, I will say that f is
total: it just means f is defined on all n.
We learn more: there is no expression in the universal language capable
of deciding if n is the code of a f_n being total or strictly partial.
For if that would exist then we would have a procedure for extracting
from the F_i the f_i, making the function g above computable, and we
know it can't.
We also get a very strong incompleness theorem: for all effective
theory there are statement, like "n codes a total function" which are
undecidable in the theory.
Indeed, if there was an effective theory capable of deciding all
statements of the type :"n codes a total function" then such a theory
would provide a way to build an expression in the language making
possible to enumerate the total computable functions, which can't be.
So, at a fundamental level, it shows that any machine, capable of
changing itself, has to choose between universality and security. If
you want all the total computable functions, not only your machine can
not stop on some inputs, but it does it sometimes in a non effectively
provable of verifiable way.
Giving the enumerabilty of the (total or not) computable functions,
which follows directly from CT, Cantor diagonalization already shows
the existence of non computable functions from N to N. Indeed most of
them are not computable. The set of computable functions is enumerable
but the set of all functions is not enumerable, making the set of
uncomputable functions from N to N not enumerable. In that sense there
are far more non computable functions from N to N than computable one.
But the effective diagonalization, made on the partial computable
functions shows, with CT, that the function TOT, from N to N, such
that TOT(n) = 1 if F_n is total, and 0 if not, is not computable. That,
is, we get the uncomputability of precise functions and predicates
bearing in computer science (and by Godel's arithmetization, already in
number theory).
...
IS WCT true? Well CT -> WCT, and there are many evidences for CT. (ASAP
...)
Hope this provide some help.
Happy new year,
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 Mon Dec 31 2007 - 08:38:48 PST