[FOM] Status of Quantum Computing - Omega Wellfoundedness
Hrant Marandjian
hrant.marandjian at unicad.am
Wed Oct 30 02:28:35 EST 2002
Dear colleagues,
It seems to me, that the problem under discussion has a longer history
and a wider area.
The first investigator who has proved the existence of non-constructive
limits
of (primitive) recursive monotonic&bounded sequences was E.Specker:
E.Specker, Nicht konstruktiv beweisbare S\"atze der Analysis,
J.Symbolic Logic, 14 (1949), 145-158.
For this reason that kind of sequences are called "Specker sequences".
Constructive analysis deals mainly with Specker sequences of constructive
real numbers, and their limits are called "Specker numbers".
Later a result concerning Specker numbers was obtained by H.G. Rice:
H.G. Rice, Recursive real numbers, Proc. Amer. Math. Soc., 5 (1954),
784-791.
In a book by B. Kushner (who has obtained a series of brilliant results on
that matter)
a big variety of results associated with Specker sequences can be found:
B. Kushner, Lectures on Constructive Mathematical Analysis, Providence RI:
Amer. Math. Soc. 1985, (Translation of Russian 1973
book).
Another good source is:
Per Martin-L\"of, Notes on Constructive Mathematics. Almqvist & Wiksell,
Stockholm, 1970.
A monotonically decreasing sequence of computable upper bounds of Kolmogorov
complexity
also can be considered as an example of functional Specker sequences:
H.B. Marandjian, On some properties of asymptotically optimal recursive
functions. Matematika, Izvestija Akademii
Nauk Armjanskoj SSR, 4(1): 3-22, 1969 (in
Russian).
English translation can be found in :
H.B. Marandjian, Selected Topics in Recursive
Function Theory in Computer Science.
Technical University of Denmark, Lyngby, 1990.
(See the section concerning upper and lower bounds).
Sincerely,
Hrant Marandjian
More information about the FOM
mailing list