More comments on George Levy + *THE PUZZLE*.

## Advertising

Le 30-mai-06, à 20:42, George Levy a écrit : > > To speak only for myself, I think I have a sufficient understanding of > the thread. Essentially you have shown that one cannot form a set of > all > numbers/functions because given any set of numbers/functions it is > always possible, using diagonalization, to generate new > numbers/functions: the Plenitude is too large to be a set. The first person plenitude will be too large or too complex to be a mechanically generable set. Just to give the exact wording of the conclusion. The explanation will follow. I am glad you describe the tranfinite extensions of the set of (growing or not) computable functions as a plenitude, and it models indeed well the notion of first person plenitude on which we will converge with Church thesis, and which describes a quasi solipsistic transfinitely self-extending self, building from "controllable sets" to bigger one. But the sequel should show how Church thesis will force us to accept a third person comp realm which will somehow transcend the limitation of the first person, but then with *the* big price. > This leads to > a problem with the assumption of the existence of a Universal > Dovetailer > whose purpose is to generate all functions. I hope this summary is > accurate. Completely. Let me give you *the puzzle*. What is wrong with the following "refutation" of Church thesis: Let me just recall what is a computable function from N to N. It is function from N to N which is such that it is exist a finite way to explain how to compute it in a finite number of steps on any natural numbers. More precisely: f is computable if there is a language L such that f admits a finite code/program/description/number explaining how to compute f(n), in a finite time on any number natural n. I will say that that a language L is universal, if all computable functions from N to N admit a code in L. A weak form of Church thesis can be put in this way: there exists a universal language. I will say a digital (or finitely describable) machine M is universal if M can "understand" a universal language L, in the sense of being able to compute any computable functions described in L (and thus all given that L is universal) . In term of digital machine, Church thesis becomes: there exists a universal digital machine. Now what is wrong with the following argument: if there is an universal language or machine, the computable functions can be described by finite description in that language, or program for that machine. Such a set is obviously enumerable. There is a bijection between N and the set of those descriptions: 1 f1 2 f2 3 f3 4 f4 etc. So the following function g is well-defined by: g(n) = fn(n) + 1 Then, to compute it on the number n (439 say), just generate the description/program of f1 f2 f3 ... until fn, that is f439, apply it on n to get fn(n), f439(439), and add 1 to get g(n) = fn(n)+1, that is here: f439(439)+1. But then g cannot be described in the language L! Why? Suppose g is described by a code in the language L: then g belongs somewhere in the list f1, f2, f3, f4, f5, .... Thus there would exist a number k such that g = fk, and thus g(k) = fk(k); but g(k) = fk(k)+1. And thus fK(k) = fk(k)+1 (*) And fk(k) is a well defined number given that the fi are all computable functions from N to N. So I can substract fk(k) on both sides of (*) just above, and I get 0 = 1 (contradiction). So there is no universal language, we cannot generate all computable functions, still less, then, to dovetail on them. Where is the error? How could Church still assert that its "lambda-conversion calculus" (an ancestor of Lisp) is universal? What about Fortran, Lisp, Python or other Rational Unitary Matrices? I (re)assure you (?), I will keep Church thesis, without which there is no just no UD. What does the above reasoning really prove then? What price will be asked upon us for keeping consistently our belief in universal language and universal machine? It is not important to find the answer, but it will be capital to understand it, and for that, it is capital to get the question, to see the problem. I think that you, George, have seen the problem, and I am just making higher the probability that others see as clearly as possible the problem too. Hal and Jesse made big hints toward the solution but I am not sure they have put the fingers on the very very pricy consequence (?). Bruno PS Rereading some recent mails I wrote, I am ashamed of my style (when I complete a sentences!) and by my enduring mishandling of the singular/plural (the "s" problem). Please accept my apologies, and don't hesitate to correct me or to ask questions in front of ambiguities. Thanks for the interest anyway. 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 -~----------~----~----~----~------~----~------~--~---