Title: SUMMARY (was: OM = SIGMA_1) I send to David Nyman (the 06 Nov 2007) a little planning:
1) Cantor's diagonal 2) Does the universal digital machine exist? 3) Lobian machines, who and what are they? 4) The 1-person and the 3- machine. 5) Lobian machines' theology 6) Lobian machines' physics 7) Lobian machines' ethics Let me summarize what has been done and what remains to be done. 1) Cantor's diagonal I tend to consider that the point "1)" is finished. Cantor's argument is that if there is a bijection between natural numbers, that is: 0, 1, 2, 3, 4, ..., and sequences of numbers, that is a bijection like 0 ----------- 45, 7, 8976, 4, 32, ... 1 ----------- 0, 0, 67, 78, 0, ... 2 ----------- 27, 1, 24, 24, 23, ... 3 ----------- 1, 1, 1, 345, 7, ... ... then the "antidiagonal" sequence 46, 1, 25, 346, ... cannot be in the list, because by construction it differs from each sequence in the list. See below how to make explicit the contradiction. The reasoning does not depend on the particular sequences exhibited, and it shows that no enumerable set of sequences can be put in 1-1 correspondence with the natural numbers. The conclusion is that the set of all sequences of natural numbers is innumerable (not enumerable, not countable, uncountable, etc. Important concept have many synonym in math). Let me recall the same proof, but with usual mathematical notation. A sequence of numbers, like f_0 = 56, 7897876, 67, 89, 1, 1, 45, ... is really "just" a function from N to N: f_0(0), f_0(1) f_0(2), f_0(3), f_0(4), ... with here: f_0(0) = 56, f_0(1) = 7897876, f_0(2) = 67, f_0(3) = 89, f_0(4) = 1, etc. So the bijection above becomes: 0 ----------- f_0 = f_0(0), f_0(1) f_0(2), f_0(3), f_0(4), ... 1 ----------- f_1 = f_1(0), f_1(1) f_1(2), f_1(3), f_1(4), ... 2 ----------- f_2 = f_2(0), f_2(1) f_2(2), f_2(3), f_2(4), ... 3 ----------- f_3 = f_3(0), f_3(1) f_3(2), f_3(3), f_4(4), ... ... You can see that the diagonal sequence can be described by: f_0(0), f_1(1), f_2(2), .... f_n(n), ... Then the "antidiagonal" sequence (function) g is given by f_0(0)+1, f_1(1)+1, f_2(2)+1, .... f_n(n)+1, ... That is: g(n) = f_n(n)+1 (definition of g) Now we can make the contradiction explicit. Suppose that g is in the list f_i. Then it exists a number k such that g = f_k. This means of course that for all numbers n we have g(n) = f_k(n). In particular g(k) = f_k(k). But by the definition of g: g applied on k = g(k) = f_k(k)+1. Thus (by Leibniz identity rule): f_k(k) = f_k(k)+1 Now, all f_i are functions from N to N, so they are defined on all natural numbers, so f_k(k) is a number. We have seen in high school that identical numbers can be subtract on both sides of an equation leading to 0 = 1. (contradiction). Thus the f_i cannot enumerate all functions from N to N. We say: N^N is innumerable. This was point "1)". Hope it is ok for every one. Please be sure you get the point before proceeding. 2) Does the universal digital machine exist? I recall the informal notion of what is an (intuitively) computable function (from N to N). Def: A function f from N to N is computable if we can describe in some formal language L, in a finite way, how to compute, in a finite time, its value f(n) on each natural number n. Def. I will call "code of f" such a description of how to compute f. Def. A language L is said universal if all computable functions can be described in the language. Def. A machine is universal if she understands a universal language, (and thus can indeed compute all computable functions from N to N, at least in Platonia, where "Platonia" is defined by a place where you can always ask and get more time and more space/memory: we don't put deadline to the (universal) machine. Church thesis is the statement that a universal language (and machine) exists, and indeed that in particular lambda-calculus provides such a universal language. Church's thesis is not obvious. Indeed, when Church "defined" the computable functions by those capable of being computed by a lambda-expression (a symbolic expression or code written in the lambda-calculus), Stephen Cole Kleene thought at first that a reasoning similar to Cantor's proof of the non enumerability of N^N (see above) could be made against Church's pretension. Kleene's reasoning is the following, and works for any pretension that there is a universal language (so we have not to even define what lambda-calculus). Indeed, suppose that there is a universal machine and thus a universal language in which all computable functions from N to N can be given a code. Now the set of codes in the language L is enumerable, being a subset of all possible expression written in the language (which we have seen to be enumerable). Thus there is an enumeration of all computable functions from N to N f_1, f_2, f_3, f_4, f_5, f_6, f_7, f_8, f_9, ... but then the "antidiagonal" function g defined by g(n) = f_n(n) + 1 is computable, given that each f_n is computable, and that "+1" is a computable operation. But g cannot be in the list, for the same reason as above. Now this cannot be a proof that the set of computable functions is not enumerable, given that the set of codes is obviously enumerable. So this looks like a proof by absurdo that there is no universal language, and thus no universal machine. The proof, nevertheless is wrong. It did presuppose that the universal language compute all functions from N to N and only that !!!!!!!!!!!!!!!!!!!!!!!!!!!!!! Indeed to substract f_(k)(k) on both side of f_(k)(k) = f_(k)(k) + 1, f_k(k) has to be a number!!!!!!! If f_k(k) is undefined (for example the interpretation by the universal machine of the code makes the machine non stopping) then the argument just doesn't go through!!!! So the possibility that there is a universal language remains intact. But now we know that the codes written in the possible universal language could correspond to object which are NOT function from N to N, but from some subset of N to N. Such "function" are called strictly partial function: they are not defined on each natural number. Such function can make the computer crashing (looping, running forever, non stopping, etc.). So you have to accept the universal machine can crash if you want her to be able to be universal. As I said: you cannot have both security and universality. Later security will play a role for the notion of first person, and universality will play a role for the notion of third person. Experimentally, this is what happens for lambda-calculus, FORTRAN, JAVA, C++, Lisp, SK-combinators, game-of-life, etc. With those language each corresponding g functions, will indeed crash the corresponding universal machine (codes, expressions) when applied on their own code. All known universal language have been shown equivalent: they define always exactly the same class of computable functions. From this you can infer immediately unsolvability and incompleteness of any effective theory about machines (and numbers). Indeed if L is universal, then you can enumerate the codes (and thus the corresponding partial functions) written in L: f_1, f_2, f_3, f_4, f_5, f_6, f_7, f_8, f_9, ... But here the f_i denotes partial functions. That is a mixture of strictly partial function and of total functions (partial function where the domain-definition subset is N itself and thus total = defined on all n, or put in another way they belongs to N^N. Absolute unsolvability result: There is no machine capable of deciding when, given a description of a code in L, if that code is for a strictly partial functions or a total partial function. Proof. If such a code exists then you can used it to extract mechanically from the enumeration f_1, f_2, f_3, f_4, f_5, f_6, f_7, f_8, f_9, ... a "sub-enumeration" of the total partial functions. But then you obtain an enumeration of all total computable function and only those!!!!!!!!!!!! But this leads to a (always the same) contradiction (see above). QED. (Relative) Incompleteness result. There is no correct theories about machines in which all statements can be proved. Proof: if there was such a theory, you would be able to use it to construct a machine capable of deciding totality/strict-partiality of codes in L, contradicting the absolute unsolvability result. QED. Note in particular that this means that for *any* correct theory T there will be a particular true statement with the shape "the ith expression in language L does code a total partial function" which is undecidable in that theory. This explains why incompleteness is relative, because in the theory T', which is T'+ (as new axioms) the preceding true statement, obviously the statement becomes provable in one line (by a proof saying "see the axiom". There is no equivalent of Church's thesis for provability! So you see that the first incompleteness theorem of Gödel is a simple consequence of Church thesis. Incompleteness is proved by a direct Cantor diagonalization done in the realm of computable partial functions. A question: what if we want, for some reason, be sure the universal computer will not crash. After all we could ask for security. I will not answer that question now, but thinking on this question will lead to a notion of first person, and will give a notion of sub-universality. Sub-universality is somehow the nearer you can go near universality without loosing security. More remains to be said, here of course. In particular, both in this list and in a course I'm giving at ULB(*) I have begun to provide example of universal language. It seems to help a lot some students. - Cutland-Shepherdson-Sturgis coffee-bar language - SK-combinators - Diophantine Polynomials - Robinsonian (and Lobian) Machine - LISP Let me summarize roughly the other points: 3) Lobian machines, who and what are they? Here I have to explain the fundamental nuances between computability and provability. We have already seen, just above, a very big difference. For computability we have a "Church's thesis" and thus a notion of universality, but we have none for provability. Having a theory, we can always build a more powerful theory. No theories can be provability-universal. Now, nothing prevent *some* theory of being computability-universal, and indeed we can build such a theory from any formal logical specification of a universal language. Such specifications will give our "absolute ontic TOE", and defines the absolute measure on the Observer Moments from which we will derive the physical laws (just to test such theories with the empirical facts). But the physics will not belong to the "absolute ontic TOE". Physics will appears to belong to the "categorie de l'entendement"' would say Kant, I mean physics appears as a particular view by internal observers appearing in the "absolute ontic TOE". We thus need an observer notion (if only to get the "Observer Moments), and, as most of you already know, the observer will be the Lobian Machine. A lobian machine will be a universal machine knowing (in some weak sense) that she is universal. Such a machine will known to be incomplete and will (a bit like Hal Ruhl try to say currently to George) begin to build an (infinite path) toward completion. Much more on this later. BTW, Torkel Fraenkel's other book, on inexhaustibility, is a good introduction for those autonomous progressions (as they are called in the literature), but we will need only the fact that some modal logics (the hypostases) remains invariant in those progressions for making the comp-physics , and all hypostatses, stable and recoverable. More later ... 4) The 1-person and the 3- machine. They are not the same, and they will fight against each other "forever". In case you worry: they can make progress so that such fight is less and less painful, or more and more civilized, that is by discussing around a table instead than with bombs and bloody war, but the tension between those two different view is not eliminable. Never, unless comp is false. 5) Lobian machines' theology The 1-person and the 3-person (3-machine) are just two arithmetical interpretation of the Plotinian hypostases. Those who have followed older posts, or have read my Plotinus paper, knows that there is 8 hypostases. Later we will see that some of those hypostases (= points-of-view) will still be multiplied, indeed I expect some of them to lead to some graded algebra describing some quantum computer, ... For each machine, its arithmetical hypostases defines its theology. Propositional (self) "theology" is given primarily by the modal logic G*. Propositional (self) "science" is given primarily by the modal logic G. Pure propositional theology is given by G* minus G. 6) Lobian machines' physics Just particular hypostases corresponding intuitively to the way matter has to emerge as explained in the universal dovetailer argument. 7) Lobian machines' ethics Not so difficult, assuming comp. I will indeed only consider the ethics of the computationalist Lobian machine. One key is that the TRUTH of "yes doctor" entails the RIGHT of saying NO to the doctor. Computationalism *is* a religion somehow, and it can explain why it has to be a "religion", and why it just cannot be used coercively on people. Alas, some NON-comp people could not tolerate the comp-people, and this will give rise to future conflicts, ... Then computationalism is not (at all) an ethical panacea, and I will say some word of the type of conflicts occuring (in Platonia) between a large variety of comp-people. OK, I send this before putting it in the trash ... I expect to correct and complete this post slowly but surely, and your remarks could help, thanks. 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 [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~----------~----~----~----~------~----~------~--~---
