On 3/9/2011 9:14 AM, Bruno Marchal wrote:
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.
By "not intrinsic" I assume you refer to the fact that the Godel
numbering scheme that idenitfies a number u with a program is not
something intrinsic to arithmetic; it is a mapping we create. Right?
But then what does it mean to say "all universal numbers have to taken
into account"? If I understand correctly *every* natural number is a
universal number, in some numbering scheme or another. So what does
"taking into account" mean?
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 email@example.com.
To unsubscribe from this group, send email to
For more options, visit this group at