Hi,

## Advertising

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 -~----------~----~----~----~------~----~------~--~---