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