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 are code by numbers, and you can mechanically extract x
and y from
Then u is a universal number if for all x and y you have that
phi_u() = 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() = 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.
