[FOM] Status of Quantum Computing - Omega Wellfoundedness

[Hrant Marandjian]

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