Weakly computable real numbers. (English) Zbl 0974.03054
The authors look at Cauchy sequences converging to real numbers and their effectiveness. If one has a computable sequence of rationals monotonically increasing to a real \(\alpha\) then the real is called left computable (or elsewhere, computably enumerable), (and similarly right computable). The real may not be computable as there is no guaranteed effective convergence ratio. If the sequence is not monotone then the real which is its limit is \(\Delta^0_2\). The authors show that if we define a real to be d.c.e. when it is the arithmetic difference of two left computable reals, then this set forms a field, and hence the “difference hierarchy” for reals stops at two. It is also shown that the class of left or right computable reals, the class of d.c.e. reals, and the class of \(\Delta^0_2\) reals are all distinct. In a later paper (Proceedings COCOON’01) functions based on the field of d.c.e reals are examined.
Reviewer: R.Downey (Wellington)
MSC:
| 03F60 | Constructive and recursive analysis |
Keywords:
computable reals; Cauchy sequences; computable sequence of rationals; effective convergence; field of d.c.e realsReferences:
| [1] | Carstens, H. G., \(Δ^0_2\)-Mengen, Arch. Math. Logik, 18, 55-65 (1976) · Zbl 0356.02039 |
| [2] | C. Calude, P. Hertling, B. Khoussainov, and Y. Wang, Recursively enumerable reals and Chaintin’s \(Ω\); C. Calude, P. Hertling, B. Khoussainov, and Y. Wang, Recursively enumerable reals and Chaintin’s \(Ω\) · Zbl 0894.68081 |
| [3] | Ceıtin, G. S., A pseudofundamental sequence that is not equivalent to a monotone one (Russian), Zap. Naučn. Sem. Leningrad. Otdel. Mat. Inst. Steklov (LOMI), 20, 263-271 (1971) · Zbl 0222.02046 |
| [4] | Cooper, S. B., Degrees of Unsolvability (1971), Leicester University: Leicester University Leicester · Zbl 0248.02045 |
| [5] | Ershov, Y., On a hierarchy of sets I; II and III, Algebra i Logika, 7, 47-73 (1968) |
| [6] | Friedberg, R. M., Three theorems on recursive enumeration: I. Decomposition, II. Maximal sets, III. Enumeration without duplication, J. Symbolic Logic, 23, 309-316 (1959) · Zbl 0088.01601 |
| [7] | Jockusch, C. G., Semirecursive sets and positive reducibility, Trans. Amer. Math. Soc., 131, 420-436 (1968) · Zbl 0198.32402 |
| [8] | Ko, Ker-I., On the definitions of some complexity classes of real numbers, Math. Systems Theory, 16, 95-100 (1983) · Zbl 0529.03016 |
| [9] | Lachlan, A. H., Recursive real numbers, J. Symbolic Logic, 28, 1-16 (1950) · Zbl 0207.31101 |
| [10] | Rice, H. G., Recursive real numbers, Proc. Amer. Math. Soc., 5, 784-791 (1954) · Zbl 0058.00602 |
| [11] | Robinson, R. M., Review of “R. Peter: ‘Rekursive Funktionen,’ Akad. Kiado. Budapest, 1951”, J. Symbolic Logic, 16, 280 (1951) · Zbl 0043.24802 |
| [12] | Rogers, H. Jr., Theory of Recursive Functions and Effective Computability (1967), McGraw-Hill: McGraw-Hill New York, p. 644-653 · Zbl 0183.01401 |
| [13] | Soare, R., Recursively Enumerable Sets and Degrees (1987), Springer-Verlag: Springer-Verlag Berlin/Heidelberg · Zbl 0667.03030 |
| [14] | Soare, R., Cohesive sets and recursively enumerable Dedekind cuts, Pacific J. Math., 31, 215-231 (1969) · Zbl 0172.00902 |
| [15] | Specker, E., Nicht konstruktiv beweisbare Sätze der Analysis, J. Symbolic Logic, 14, 145-158 (1949) · Zbl 0033.34102 |
| [16] | Weihrauch, K., Computable Analysis, An Introduction. Computable Analysis, An Introduction, Texts in Theoretical Computer Science. An EATCS Series (2000), Springer-Verlag: Springer-Verlag Berlin · Zbl 0956.68056 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
