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@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at 
http://groups.google.com/group/everything-list
-~----------~----~----~----~------~----~------~--~---

Reply via email to