Hi, We may be at a cross of the "seventh step" and "Why I am I?" thread.

## Advertising

Chose your favorite universal system. Like LISP, FORTRAN, the combinators, the diophantine equations, etc. Enumerate in lexicographical order the expressions corresponding to the algorithms of the partial computable function of one variable. (reread the math if necessary, or ask question). This enumerates, with repetition, all the partial (and thus the total) functions from N to N, usually described as the phi_i: phi_0, phi_1, phi_2, phi_3, .... phi_7 is the name of the 7th partial function in that enumeration. So the "official" definition of a universal number I am using, is, having fixed such an enumeration, a number u such that phi_u(<x, y>) = phi_x(y). Where <x,y> represent some coding of the couple (x, y). u is usually called the computer (hard version) or the interpreter (soft version). (Later, or before, for some, soft and hard will be shown to be more absolute than most people thought, and this as a consequence of comp; but in the present context it could help to think them as relative notion). In the definition of the universal number u, phi_u(<x, y>) = phi_x(y), u is called the computer, x is called the program, and y is called the data. phi_u itself is called the universal function, and u is just a program computing that universal function. From such a u, you can code easily a universal dovetailer. This is a program which generate all the programs i, and compute, by dovetailing of the phi_i executions, all those phi_i on all its different arguments, 0, 1, 2, ... I may come back to the seven step per se later. Having said what is a universal number, I may say what is a Löbian number. Or if you prefer, having said what is a universal machine, I may say what is a Löbian machine. A Löbian machine is a universal machine which knows, in a very weak and precise technical sense, that she is universal. I can prove that any of you are universal machine. And if you understand the proof, then I have a proof (for me!) that you are inhabited by a Löbian machine. It means also, that it is just a matter of some work, made by you, to convince yourself that a Löbian machine indeed inhabit your mind. Comp is the assumption that there is a level where you can hope your are such a Löbian machine. Now I tell you this. A formula like "phi_u(<x, y>) = phi_x(y)" (the definition of universal number) can be translated into an elementary formula of first order arithmetic (like Robinson Arithmetic, or Peano Aritmetic). It ease the things considerably to chose elementary arithmetic as initial universal system. It happens that classical logic makes the very weak theory, where 0, s(0), s(s(0)) ... represent the number 0 and its successors. For all x: x + 0 = x For all x and for all y: x + s(y) = s(x + y) For all x: x * 0 = 0 For all x and for all y: x * s(y) = (x * y) + x Those formula gives the usual recursive or inductive definition of addition and multiplication. Exercise: prove that 2 + 2 = 4. That is, prove that s(s(0)) + s(s(0)) = s(s(s(s(0)))). This theory is already universal, once we accept some coding of computations into proof in that theory (using classical logic). This is an amazing result, and actually is hard to prove. It is due mainly to Gödel, Hilbert & Bernays, Löb). It is easier to prove that the combinators equation Kxy = y, Sxyz = xz(yz) are Turing universal, than to show that addition and multiplication are Turing universal (and thus simply universal with Church thesis). If you know Matiyasevitch theorem, you can derive the universality of addition and multiplication). Well, if you know that Conway's game of life (2-dim cellular automata) is universal, you know universality is cheap (yet non trivial). But the theory, <<For all x: x + 0 = x For all x and for all y: x + s(y) = s(x + y) For all x: x * 0 = 0 For all x and for all y: x * s(y) = (x * y) + x>> although universal, is not Löbian. You get a Löbian machine by adding some axioms, like For all x and for all y: NOT(x = y) -> NOT(s(x) = s(y)) (different numbers have different successors) For all x: NOT(0 = s(x)) (0 is not a successor) And above all the following infinity of axioms, known as the "induction axioms". That is, for any first order logical formula A, you take the following formula as axiom: (A(0) & For all x: A(x) -> A(s(x))) -> For all x: A(x). This is enough to get a Löbian machine, (Peano Arithmetic) which, as AUDA will illustrate has already a stable and very complex theology, including its physical quanta and qualia. But before going to AUDA, I have to finish the seventh step properly, and probably come back to the Movie graph problems we have encountered. Why a movie of a computation is not a computation? What is the difference between a computation and a description of a computation? etc. I guess we could finish properly the seventh and the eight step. Ask *any* question. It is not easy. But obviously comp relies on theoretical computer science which is less known by the general public than the physical sciences. Bruno Marchal 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-l...@googlegroups.com. To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/everything-list?hl=en.