On 08 Mar 2011, at 20:11, Brent Meeker wrote:

## Advertising

On 3/8/2011 10:41 AM, Bruno Marchal wrote:We could start with lambda terms, or combinators instead. Acomputation (of phi_4(5) is just a sequencephi_4^0 (5) phi_4^1 (5) phi_4^2 (5) phi_4^3 (5) phi_4^4 (5)phi_4^5 (5) phi_4^6 (5) ..._4 is the program. 5 is the input. ^i is the ith step (i = 0, 1,2, ...), and phi refers implicitly to a universal number.Bruno, I don't think I understand what a universal number is. Couldyou point me to an explication.

`The expression "universal numbers" is mine, but the idea is implicit`

`in any textbook on theoretical computer science, or of recursion`

`theory (like books by Cutland, or Rogers, or Boolos and Jeffrey, ...).`

`Fix any universal system, for example numbers+addition+multiplication,`

`or LISP programs.`

You can enumerate the programs: P_0, P_1, P_2, ... So that you can enumerate the corresponding phi_i phi_0, phi_1, phi_2, ...

`Take a computable bijection between NXN and N, so that couples of`

`numbers <x,y> are code by numbers, and you can mechanically extract x`

`and y from <x,y>`

`Then u is a universal number if for all x and y you have that`

`phi_u(<x,y>) = phi_x(y).`

In practice x is called program, and y is called the input.

`Now, I use, as fixed initial universal system, a Robinson Arithmetic`

`prover. I will say that a number u is universal if RA can prove the`

`(purely arithmetical) relation phi_u(<x,y>) = phi_x(y).`

`The notion is not entirely intrinsic (so to be universal is not like`

`to be prime), but this is not important because from the machine's`

`point of view, all universal numbers have to be taken into account.`

`With that respect, here, mind theorist have an easier work than`

`computer scientist which search intrinsic notion of universality. We`

`don't need that, because the personal Löbian machine and their`

`hypostases does not depend on the initial choice, neither of the`

`computable bijection, nor of the "first universal" system.`

`To put it more simply: a universal number is the Gödel number of the`

`code of a universal system (a computer, or a general purpose computer`

`(in french: an 'ordinateur'), or a 'programming language interpreter').`

OK? Ask for more if needed. 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 everything-list@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.