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

On 3/8/2011 10:41 AM, Bruno Marchal wrote:
We could start with lambda terms, or combinators instead. A computation (of phi_4(5) is just a sequence

phi_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. Could you 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.



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 
For more options, visit this group at 

Reply via email to