×

zbMATH — the first resource for mathematics

Effectively closed sets and graphs of computable real functions. (English) Zbl 1039.03033
Summary: In this paper, we compare the computability and complexity of a continuous real function \(F\) with the computability and complexity of the graph \(G\) of the function \(F.\) A similar analysis will be carried out for functions on subspaces of the real line such as the Cantor space, the Baire space and the unit interval. In particular, we define four basic types of effectively closed sets \(C\) depending on whether (i) the set of closed intervals which with nonempty intersection with \(C\) is recursively enumerable (r.e.), (ii) the set of closed intervals with empty intersection with \(C\) is r.e., (iii) the set of open intervals which with nonempty intersection with \(C\) is r.e., and (iv) the set of open intervals with empty intersection with \(C\) is r.e. We study the relationships between these four types of effectively closed sets in general and the relationships between these four types of effectively closed sets for closed sets which are graphs of continuous functions.

MSC:
03D45 Theory of numerations, effectively presented structures
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Blum, L.; Shub, M.; Smale, S., On a theory of computation and complexity over the real numbers, Bull. amer. math. soc., 21, 1-46, (1989) · Zbl 0681.03020
[2] Brattka, V.; Weihrauch, K., Computability on subsets of Euclidean space I: closed and compact subsets, Theoret. comput. sci., 219, 65-93, (1999) · Zbl 0916.68042
[3] Cenzer, D., Effective dynamics, (), 162-177 · Zbl 0823.03034
[4] Cenzer, D., π01 classes in computability theory, (), 37-85 · Zbl 0939.03047
[5] Cenzer, D.; Remmel, J.B., Recursively presented games and strategies, Math. soc. sci., 24, 117-139, (1992) · Zbl 0786.90103
[6] Cenzer, D.; Remmel, J.B., Index sets for π10 classes, Ann. pure appl. logic, 93, 3-61, (1998) · Zbl 0926.03042
[7] Cenzer, D.; Remmel, J.B., π10 classes in mathematics, (), 623-821 · Zbl 0941.03044
[8] Cenzer, D.; Remmel, J.B., Index sets in computable analysis, Theoret. comput. sci., 219, 111-150, (1999) · Zbl 0916.68052
[9] Cohen, R.S.; Gold, A.Y., ω-computations on Turing machines, Theoret. comput. sci., 6, 1-23, (1978) · Zbl 0368.68057
[10] Friedman, H., The computational complexity of maximization and integration, Adv. in math., 53, 80-98, (1984) · Zbl 0563.03023
[11] Grzegorczyk, A., Computable functionals, Fund. math., 42, 186-202, (1955) · Zbl 0066.26001
[12] Grzegorczyk, A., On the definition of computable real continuous functions, Fund. math., 44, 61-71, (1957) · Zbl 0079.24801
[13] Hinman, P.G., Recursion-theoretic hierarchies, (1978), Springer Berlin · Zbl 0371.02017
[14] Jockusch, C.G.; Soare, R.I., π10 classes and degrees of theories, Trans. amer. math. soc., 173, 33-56, (1972) · Zbl 0262.02041
[15] Jockusch, C.G.; Soare, R.I., Degrees of members of π10 classes, Pacific J. math., 40, 605-616, (1972) · Zbl 0209.02201
[16] N. Klarlund, Progress measures and finite arguments for infinite computation, Ph.D. Thesis, Cornell University, 1990.
[17] Kleene, S.C., Hierarchies of number-theoretic predicates, Bull. amer. math. soc., 61, 193-213, (1955) · Zbl 0066.25901
[18] Ko, K., Complexity theory of real functions, (1991), Birkhauser Basel
[19] Ko, K., On the computability of fractal dimensions and Julia sets, Ann. pure appl. logic, 93, 195-216, (1998) · Zbl 0926.03049
[20] Ko, K.; Friedman, H., Computational complexity of real functions, Theoret. comput. sci., 20, 323-352, (1982) · Zbl 0498.03047
[21] D. Lacombe, Classes récursivement fermés et fonctions majorantes, C.R. Acad. Sci. Paris 240 (1955) 716-718, Théorie des fonctions. · Zbl 0067.00206
[22] D. Lacombe, Les ensembles récursivement ouverts ou fermés et leurs applications à l’Analyse récursive, C.R. Acad. Sci. Paris 246 (1958) 28-31, Logique. · Zbl 0080.24402
[23] Landweber, L.H., Decision problems for ω-automata, Math. systems theory, 3, 376-384, (1969) · Zbl 0182.02402
[24] Lempp, S., Hyperarithmetical index sets in recursion theory, Trans. amer. math. soc., 303, 559-583, (1987) · Zbl 0652.03030
[25] Metakides, G.; Nerode, A., The introduction of non-recursive methods into mathematics, (), 319-355
[26] A. Nerode, W. Huang, Applications of pure recursion theory to recursive analysis, Acta Sinica 28 (1985) 625-636 (in Chinese). · Zbl 0638.03058
[27] Odifreddi, P., Classical recursion theory, (1989), North-Holland Amsterdam · Zbl 0931.03057
[28] Pour-El, M.B.; Richards, J.I., Computability in analysis and physics, perspectives in mathematical logic, (1989), Springer Berlin · Zbl 0678.03027
[29] Soare, R., Recursively enumerable sets and degrees, (1987), Springer Berlin
[30] Staiger, L., Hierarchies of recursive ω-languages, J. inform. process. cybernet. EIK, 22, 5/6, 219-241, (1986) · Zbl 0627.03024
[31] L. Staiger, Recursive automata on infinite words, Proc. STACS ’93, Lecture Notes in Computer Science, vol. 665, Springer, Berlin, 1993, pp. 629-639. · Zbl 0799.68139
[32] L. Staiger, ω-languages, in: G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, vol. 3, Springer, Berlin, 1997, pp. 339-387.
[33] L. Staiger, K. Wagner, Recursive ω-languages, Proc. Fundamentals of Computation Theory, Lecture Notes in Computer Science, vol. 56, Springer, Berlin, 1977, pp. 532-537.
[34] Weihrauch, K., Computability, (1987), Springer Berlin
[35] Weihrauch, K., A foundation of computable analysis, (), 66-89 · Zbl 0923.03057
[36] Weihrauch, K., An introduction to computable analysis, (2000), Springer 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.