[FOM] Status of Quantum Computing - Omega Wellfoundedness
hrant.marandjian at unicad.am
Wed Oct 30 02:28:35 EST 2002
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
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),
In a book by B. Kushner (who has obtained a series of brilliant results on
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
Another good source is:
Per Martin-L\"of, Notes on Constructive Mathematics. Almqvist & Wiksell,
A monotonically decreasing sequence of computable upper bounds of Kolmogorov
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
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).
More information about the FOM