Hi,
Ok Tom, put your security belt because we will leave the constructive
area, because it is the price we need to pay, in front of machine, for
NOT leaving the finite area.
Let me recall the problem.
1) Obviously the set of all computable function from the set of natural
number N to the set of natural numbers N is countable (synonym:
enumerable, in bijection with N). The reason is that a computable
function, by definition, has a code (synonym: a description, a program,
a finite machine), that is any finite things which can be used by some
entity/machine for computing the functions, and (infinite) sets of
finite things are always (infinite and) countable.
Note that a (one) computable function is an infinite object, but giving
that that infinite set is computable and generable from a code, the set
of computable functions is in bijection with the set of their codes,
which itself is in bijection with N, and so the infinite set of
infinite objects which are the computable function is in bijection with
N.
2) Now it looks like we have already a contradiction. let us write f1
for the computable function having the least code, f2 the second one,
etc. So we get the sequence f1, f2, f3, f4, f5, ... fn, .... And let
us define the function g by
g(n) = fn(n) + 1
It looks like g is computable isn't it. All fn are computable and can
be computed on each n, and certainly adding one ("the + 1") is
computable too. Right?
Well, if you say "all right" here, we are in trouble. Because if g is
really computable, then g is in the sequence of all computable
functions fi. But then *there is* a k such that g = fk, and then g(k)
is equal to both fk(k) and fk(k)+1, and that gives 0 = 1, by
substracting the well-defined number fk(k).
So g just cannot be a computable!
How could g looks like being computable? It is true that all fn are
computable, and it is obviously true that "+ 1" is computable.
So, the only thing which is not computable is .... the bijection
itself, between N and the fi.
It is the correspondence:
1 --- f1
2 --- f2
3 --- f3
4 --- f4
....
which is NOT computable! There is just no algorithm which can generate
the sequence of codes of the computable functions from N to N. So,
although each fn is a computable function (from N to N), you cannot
diagonalize it for getting g, because to compute g on n, g(n) you need
to generate the n first programs corresponding to f1, f2, f3, ... fn,
and then apply it to n (and then add one), but you just will never been
able to give me a finite set of instructions for doing that. If {f1,
f2, f3, ...} are all computable function from N to N, and if the
sequence is complete (con,tains all such function) then g, although
mathematically well defined, is just not programmable.
BUT THEN .....
Saying this, it could look like the Universal Dovetailer is still in
peril. But I have given you the shape of the solution when I show you
the proof of the existence of a irrational number which exponentiated
to an irrational number gives a rational number. That precise problem
is irrelevant, but the non constructive reasoning I did to prove it is
very relevant here. I was telling that there exist some mathematical
object, but I was unable to give it. I was only able to give you a bow
with the shape
{ a b }
telling you the "solution" was in that box (but not saying if it was a
or if it was b).
The same here, but with an infinite box. I cannot generate mechanically
the set {f1, f2, f3, ...} of computable functions, but there is still
hope (Church Thesis CT will just express that hope) that I can generate
some BIGGER set, containing all computable functions AND MANY OTHER
THINGS TOO. The hope is that the OTHER THINGS will help us escaping the
diagonal contradiction.
Well, actually CT says more: it says not only that there is a universal
language/machine, but that fortran is such a one! And fortran programs
are fortran generable, so I can generate a sequence of all fortran
one-variable program F1 F2 F3 F4 F5 F6 F7 F8 .... ("all" means that
soon or later this sequence goes trough any fortran programs: it is of
course an infinite set)
So, given that the sequence F1, F2, F3, F4, F5, ... is generable, the
corresponding diagonal function G defined by
G(n) = Fn(n) + 1
*is* programmable in fortran. So there *is* a k such that G = Fk
And what will happen if I apply G on its own number-code k?
Just this: your machine will crash! The fortran interpreter will go in
loop or in an infinite computations.
Well, in some formal sense I will get G(k) = G(k) + 1. But I can no
more substract G(k) on both sides like we have always do at that stage,
because G(k) is just not a well-defined number.
It looks like the OTHER THINGS are the function from a subset of N to
N. Functions, now, if we want to associate them to the fortran
programs, can be only partially defined functions.
So I can still hope the sequence Fi of Fortran programs goes trough,
among OTHER THINGS, all computable functions everywhere defined, but
the price will be that I will got the undefined programmable functions
by the same token.
I give you an infinite box:
{F1 F2 F3 F4 F5 F6 F7 F8 F9 ...}
but then, I can no more use any algorithmic way to filter out the
"solutions" (the computable function from N to N) from the "non
solution" (the functions no more everywhere defined, or the function
defined on proper subset of N). Why? because if I could do that, I will
be able to build an algorithmically sequence of everywhere defined
computable functions, and from that, I hope you are convinced that I
*can* prove that 0 = 1.
The lesson is not yet Godel's incompleteness, but is very close: the
price of going through the whole controllable world of computable
functions is to accept, hidden among it, the whole uncontrollable world
of the undefined functions. They are hidden due to that impossibility
of filtering the code of the everywhere define functions from those who
are not.
Put in another way: all universal machine can crash. If someone want to
sell you a computer with a so clever operating system that the machine
never crash, then you know the machine is not universal, or the seller
says a falsity.
Hal and Jesse were close. For example:
> I was being a little sloppy...it's true that a non-halting program
> would not
> be equivalent to a computable function, but I think we can at least
> say that
> the set of all computable functions is a *subset* of the set of all
> programs.
>
> Jesse
The key point if, I may insist, is that
1) the superset (of programmable functions, not everywhere defined) is
MECHANICALLY enumerable. You can write a fortran program generating
their codes.
2) the subset of (computable function from N to N) is enumerable, but
is NOT MECHANICALLY enumerable. The bijection with N exists, but is not
programmable, in *any* programming language!
George ? Are you ok. Now that we have undefined functions; we will be
interested in the domain of definition of the programmable functions,
and those domain *are* Smullyan's reasoners (in FU). The godelized
universe is related with the functions F1 F2 F3 F4 F5 ..., and their
domains traditionally noted: W1 W2 W3 W4 W5 W6 W7 ....
What we have learned is that we have no algorithm to solve the Wn = N
question (you see that? saying Wn = N is the same as saying Fn is
defined everywhere or saying Fn is a computable function from N to N).
It is an insolubility result. It will be easy, once we get the notion
of "theory", or "chatting machine", or "recursively enumerable set" to
transform that into an incompleteness theorem.
Mmh... To get G and G*, more is needed to be honest, but not so much
more, just that some "theories" can follow, *in some sense*, all those
current posts. But this, is what Smullyan shows, albeit very concisely,
in his "heart of the matter".
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
-~----------~----~----~----~------~----~------~--~---
Received on Thu Jun 08 2006 - 12:04:43 PDT