Order-free recursion on the real numbers. (English) Zbl 0876.03022
Author’s summary: We investigate operations, computable in the sense of Recursive Analysis, which can be generated recursively from the arithmetic operations and the limit operation without using any tests on the real numbers. These functions, called order-free recursive, can be shown to include a large class of computable functions. As main tools we provide an effective version of the Stone-Weierstraß Approximation Theorem, as well as recursive partitions of unity.
Reviewer: R.Downey (Wellington)
MSC:
| 03D45 | Theory of numerations, effectively presented structures |
| 03F60 | Constructive and recursive analysis |
| 41A99 | Approximations and expansions |
| 68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |
Keywords:
recursive analysis; effective version of the Stone-Weierstraß approximation theorem; approximation without a test on the real numbers; models of computability on the real numbers; computable functions; recursive partitions of unityReferences:
| [1] | Domain representability of metric spaces. In: Proc. of the Workshop on Computability and Complexity in Analysis ( and , eds.), Informatik Berichte, Fern Universität Hagen 190 (1995), pp. 1–10. |
| [2] | Blum, Bull. Amer. Math. Soc. 21 pp 1– (1989) |
| [3] | General Topology, Part 1 and 2. Addison-Wesley, Reading, Mass., 1966. |
| [4] | Brattka, Theoret. Comp. Science 162 pp 45– (1996) |
| [5] | Computable selection in analysis. In: Proc. of the Workshop on Computability and Complexity in Analysis ( and , eds.), Informatik Berichte, Fern Universität Hagen 190 (1995), pp. 125–138. |
| [6] | and , Feasible real random access machines. Informatik Berichte. FernUniversitat Hagen 193 (1995). |
| [7] | Computable invariance. In: Proc. of the Workshop on Computability and Complexity in Analysis (, and , eds.), Universität Trier 1996, pp. 5–22. |
| [8] | and , On the extreme points of compact convex Turing located sets. In: Logical Foundation of Computer Science ( and , eds.), Springer-Verlag, Berlin-Heidelberg-New York 1994, pp. 114–128. · doi:10.1007/3-540-58140-5_12 |
| [9] | Grzegorczyk, Fund. Math. 44 pp 61– (1957) |
| [10] | Hauck, Zeitschrift Math. Logik Grundlagen Math. 19 pp 121– (1973) |
| [11] | Hauck, Zeitschrift Math. Logik Grundlagen Math. 22 pp 265– (1976) |
| [12] | Topologie II. Heldermann, Berlin 1988. |
| [13] | Ko, Theoret. Comp. Science 20 pp 323– (1982) |
| [14] | Complexity Theory of Real Functions. Birkhauser, Boston 1991. · doi:10.1007/978-1-4684-6802-1 |
| [15] | and , A unified approach to constructive and recursive analysis. In: Computation and Proof Theory ( et al., eds.), Lecture Notes in Mathematics 1104, Springer-Verlag, Berlin-Heidelberg-New York 1984, pp. 259–278. |
| [16] | Kreitz, Annals Pure Appl. Logic 36 pp 29– (1987) |
| [17] | Lacombe, Comptes Rendus 240/241 pp 2478– (1955) |
| [18] | Moore, Theoret. Comp. Science 162 pp 23– (1996) |
| [19] | and , Computability in Analysis and Physics. Springer-Verlag, Berlin-Heidelberg-New York 1989. · Zbl 0678.03027 · doi:10.1007/978-3-662-21717-7 |
| [20] | Pour-El, Zeitschrift Math. Logik Grundlagen Math. 21 pp 1– (1975) · Zbl 0323.02049 · doi:10.1002/malq.19750210102 |
| [21] | Shepherdson, Zeitschrift Math. Logik Grundlagen Math. 22 pp 391– (1976) |
| [22] | , and , Information-Based Complexity. Academic Press, New York 1988. · Zbl 0654.94004 |
| [23] | Weihrauch, Theoret. Comp. Science 113 pp 191– (1993) |
| [24] | Grundlagen der Effektiven Analysis. Correspondence Course 1681, Fern Universität Hagen 1994. |
| [25] | A Simple Introduction to Computable Analysis. Informatik Berichte 171, Fern Universität Hagen 1995. |
| [26] | Weihrauch, Annals Pure Appl. Logic 35 pp 247– (1987) |
| [27] | Zhou, Math. Logic Quart. 42 pp 379– (1996) |
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.
