[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