Hi,

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

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.


Reply via email to