×

A Galois connection between Turing jumps and limits. (English) Zbl 1515.03187

Summary: Limit computable functions can be characterized by Turing jumps on the input side or limits on the output side. As a monad of this pair of adjoint operations we obtain a problem that characterizes the low functions and dually to this another problem that characterizes the functions that are computable relative to the halting problem. Correspondingly, these two classes are the largest classes of functions that can be pre or post composed to limit computable functions without leaving the class of limit computable functions. We transfer these observations to the lattice of represented spaces where it leads to a formal Galois connection. We also formulate a version of this result for computable metric spaces. Limit computability and computability relative to the halting problem are notions that coincide for points and sequences, but even restricted to continuous functions the former class is strictly larger than the latter. On computable metric spaces we can characterize the functions that are computable relative to the halting problem as those functions that are limit computable with a modulus of continuity that is computable relative to the halting problem. As a consequence of this result we obtain, for instance, that Lipschitz continuous functions that are limit computable are automatically computable relative to the halting problem. We also discuss 1-generic points as the canonical points of continuity of limit computable functions, and we prove that restricted to these points limit computable functions are computable relative to the halting problem. Finally, we demonstrate how these results can be applied in computable analysis.

MSC:

03D30 Other degrees and reducibilities in computability and recursion theory
03D20 Recursive functions and relations, subrecursive hierarchies
03D78 Computation over the reals, computable analysis
06A15 Galois correspondences, closure operators (in relation to ordered sets)

References:

[1] Spiros A. Argyros and Stevo Todorcevic. Ramsey methods in analysis. Advanced Courses in Mathematics. CRM Barcelona. Birkh¨auser Verlag, Basel, 2005. · Zbl 1092.46002
[2] A. V. Arkhangel’ki˘ı and L. S. Pontryagin, editors. General Topology I, volume 17 of Encyclopaedia of Mathematical Sciences. Springer-Verlag, Berlin, 1990. · Zbl 0778.00007
[3] Vasco Brattka. Recursive and Computable Operations over Topological Structures. PhD thesis, Department of Computer Science, University of Hagen, Hagen, Germany, 1998. · Zbl 0871.68028
[4] Vasco Brattka. Computable invariance. Theoretical Computer Science, 210:3–20, 1999. · Zbl 0915.68047
[5] Vasco Brattka. Computable versions of Baire’s category theorem. In Jiˇr´ı Sgall, Aleˇs Pultr, and Petr Kolman, editors, Mathematical Foundations of Computer Science 2001, volume 2136 of Lecture Notes in Computer Science, pages 224–235, Berlin, 2001. Springer. 26th International Symposium, MFCS 2001, Mari´ansk´e L´aznˇe, Czech Republic, August 27-31, 2001. · Zbl 0999.03057
[6] Vasco Brattka. Effective Borel measurability and reducibility of functions. Mathematical Logic Quarterly, 51(1):19–44, 2005. · Zbl 1059.03074
[7] Vasco Brattka, Matthew de Brecht, and Arno Pauly. Closed choice and a uniform low basis theorem. Annals of Pure and Applied Logic, 163:986–1008, 2012. · Zbl 1251.03082
[8] Vasco Brattka and Guido Gherardi. Effective choice and boundedness principles in computable analysis. The Bulletin of Symbolic Logic, 17(1):73–117, 2011. · Zbl 1226.03062
[9] Vasco Brattka, Guido Gherardi, and Alberto Marcone. The Bolzano-Weierstrass theorem is the jump of weak K˝onig’s lemma. Annals of Pure and Applied Logic, 163:623–655, 2012. · Zbl 1245.03097
[10] Vasco Brattka, Matthew Hendtlass, and Alexander P. Kreuzer. On the uniform computational content of the Baire category theorem. Notre Dame Journal of Formal Logic, (accepted for publication), 2016. · Zbl 1420.03110
[11] Vasco Brattka, Matthew Hendtlass, and Alexander P. Kreuzer. On the uniform computational content of computability theory. Theory of Computing Systems, 61(4):1376–1426, 2017. · Zbl 1420.03110
[12] Vasco Brattka and Peter Hertling. Topological properties of real number representations. Theoretical Computer Science, 284(2):241–257, 2002. · Zbl 1039.03036
[13] R. I. ˇCikvaˇsvili. On a certain problem of Kuznecov and Trahtenbrot. Sakharth. SSR Mecn. Akad. Moambe, 79(2):309–312, 1975. · Zbl 0337.04003
[14] Matthew de Brecht. Levels of discontinuity, limit-computability, and jump operators. In Vasco Brattka, Hannes Diener, and Dieter Spreen, editors, Logic, Computation, Hierarchies, Ontos Mathematical Logic, pages 93–122. Walter de Gruyter, Boston, 2014. · Zbl 1344.03037
[15] Rodney G. Downey and Denis R. Hirschfeldt. Algorithmic randomness and complexity. Theory and Applications of Computability. Springer, New York, 2010. · Zbl 1221.68005
[16] M. Ern´e, J. Koslowski, A. Melton, and G. E. Strecker. A primer on Galois connections. In Papers on general topology and applications (Madison, WI, 1991), volume 704 of Ann. New York Acad. Sci., pages 103–125. New York Acad. Sci., New York, 1993. · Zbl 0809.06006
[17] R. V. Fre˘ıvald. Limiting computable functions and functionals. Latvi˘ısk. Gos. Univ. Uˇcen. Zap., 210(Teorija Algoritmov i Programm 1):6–19, 1974.
[18] Rudolf Freund. Real functions and numbers defined by Turing machines. Theoretical Computer Science, 23:287–304, 1983. · Zbl 0512.68064
[19] Rudolf Freund and Ludwig Staiger. Numbers defined by Turing machines. Collegium Logicum, Annals of the Kurt-G¨odel-Society, 2:118–137, 1996. · Zbl 0851.03012
[20] Richard Friedberg. A criterion for completeness of degrees of unsolvability. J. Symb. Logic, 22:159–160, 1957. · Zbl 0078.00602
[21] Mark E. Gold. Limiting recursion. The Journal of Symbolic Logic, 30(1):28–48, 1965. · Zbl 0203.01201
[22] Andrzej Grzegorczyk. Computable functionals. Fundamenta Mathematicae, 42:168–202, 1955. · Zbl 0066.26001
[23] Peter Hertling. Is the Mandelbrot set computable? Mathematical Logic Quarterly, 51(1):5–18, 2005. · Zbl 1065.03045
[24] Chun-Kuen Ho. Beyond recursive real functions. Information and Computation, 124(2):113–126, 1996. · Zbl 0853.68089
[25] Chun-Kuen Ho. Relatively recursive reals and real functions. Theoretical Computer Science, 210(1):99–120, 1999. · Zbl 0912.68034
[26] Mathieu Hoyrup. Genericity of weakly computable objects. Theory of Computing Systems, 60(3):396–420, 2017. · Zbl 1366.68056
[27] Carl G. Jockusch, Jr. Simple proofs of some theorems on high degrees of unsolvability. Canadian Journal of Mathematics, 29(5):1072–1080, 1977. · Zbl 0355.02032
[28] Alexander S. Kechris. Classical Descriptive Set Theory, volume 156 of Graduate Texts in Mathematics. Springer, Berlin, 1995. · Zbl 0819.04002
[29] Rutger Kuyper and Sebastiaan A. Terwijn. Effective genericity and differentiability. J. Log. Anal., 6:Paper 4, 14, 2014. · Zbl 1345.03085
[30] A.V. Kuzn´ecov and B.A. Traht´enbrot. Investigation of partially recursive operators by means of the theory of Baire space (Russian). Dokl. Akad. Nauk SSSR, 105:897–900, 1955. · Zbl 0066.26102
[31] Alain Louveau. A separation theorem for Σ11sets. Transactions of the American Mathematical Society, 260(2):363–378, 1980. · Zbl 0455.03021
[32] Yiannis N. Moschovakis. Descriptive Set Theory, volume 155 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, Rhode Island, second edition, 2009. · Zbl 1172.03026
[33] John Myhill. A recursive function defined on a compact interval and having a continuous derivative that is not recursive. Michigan Math. J., 18:97–98, 1971. · Zbl 0218.02029
[34] Andr´e Nies. Computability and Randomness, volume 51 of Oxford Logic Guides. Oxford University Press, New York, 2009. · Zbl 1169.03034
[35] Piergiorgio Odifreddi. Classical Recursion Theory, volume 125 of Studies in Logic and the Foundations of Mathematics. North-Holland, Amsterdam, 1989. · Zbl 0661.03029
[36] Arno Pauly. On the topological aspects of the theory of represented spaces. Computability, 5(2):159–180, 2016. · Zbl 1401.03087
[37] Arno Pauly and Matthew de Brecht. Towards synthetic descriptive set theory: An instantiation with represented spaces. arXiv 1307.1850, 2013. · Zbl 1395.03021
[38] Arno Pauly and Matthew de Brecht. Non-deterministic computation and the Jayne-Rogers theorem. In Benedikt L¨owe and Glynn Winskel, editors, Proceedings 8th International Workshop on Developments in Computational Models, DCM 2012, Cambridge, United Kingdom, 17 June 2012., volume 143 of Electronic Proceedings in Theoretical Computer Science, pages 87–96, 2014. · Zbl 1464.03042
[39] Arno Pauly and Matthew de Brecht. Descriptive set theory in the category of represented spaces. In · Zbl 1395.03021
[40] Hartley Rogers, Jr. Theory of Recursive Functions and Effective Computability. MIT Press, Cambridge, second edition, 1987.
[41] Matthias Schr¨oder. Topological spaces allowing type 2 complexity theory. In Ker-I Ko and Klaus Weihrauch, editors, Computability and Complexity in Analysis, volume 190 of Informatik Berichte, pages 41–53. FernUniversit¨at Hagen, September 1995. CCA Workshop, Hagen, August 19–20, 1995.
[42] Matthias Schr¨oder. Extended admissibility. Theoretical Computer Science, 284(2):519–538, 2002. · Zbl 1042.68050
[43] Laurent Schwartz. Sur le th´eor‘eme du graphe ferm´e. C. R. Acad. Sci. Paris S´er. A-B, 263:A602–A605, 1966. · Zbl 0151.19202
[44] J.R. Shoenfield. On degrees of unsolvability. Ann. of Math., 69(2):644–653, 1959. · Zbl 0119.25105
[45] Robert I. Soare. Turing Computability. Theory and Applications of Computability. Springer, Berlin, Heidelberg, 2016. · Zbl 1350.03001
[46] C. Spector. On degrees of recursive unsolvability. Annals of Mathematics (2), 64:581–592, 1956. · Zbl 0074.01302
[47] Thorsten von Stein. Vergleich nicht konstruktiv l¨osbarer Probleme in der Analysis. PhD thesis, Fachbereich Informatik, FernUniversit¨at Hagen, 1989. Diplomarbeit.
[48] Klaus Wagner. Arithmetische Operatoren. Zeitschrift f¨ur Mathematische Logik und Grundlagen der Mathematik, 22:553–570, 1976. · Zbl 0352.02031
[49] Klaus Wagner. Arithmetische und Bairesche Operatoren. Zeitschrift f¨ur Mathematische Logik und Grundlagen der Mathematik, 23:181–191, 1977. · Zbl 0359.02038
[50] Klaus Weihrauch. Computable Analysis. Springer, Berlin, 2000. · Zbl 0956.68056
[51] Xizhong Zheng and Klaus Weihrauch. The arithmetical hierarchy of real numbers. Mathematical Logic Quarterly, 47(1):51–65, 2001. · Zbl 0968.03075
[52] Martin Ziegler. Real Computability and Hypercomputation. PhD thesis, Department of Computer Science, University of Paderborn, Paderborn, Germany, 2007. Habilitation Thesis. · Zbl 1122.03039
[53] Martin Ziegler. Real hypercomputation and continuity. Theory of Computing Systems, 41(1):177–206, 2007. · Zbl 1122.03039
[54] Martin Ziegler. Revising type-2 computation and degrees of discontinuity. In Douglas Cenzer, Ruth Dillhage, Tanja Grubba, and Klaus Weihrauch, editors, Proceedings of the Third International Conference on Computability and Complexity in Analysis, volume 167 of Electronic Notes in Theoretical Computer Science, pages 255–274, Amsterdam, 2007. Elsevier. CCA 2006, Gainesville, Florida, USA, November 1–5, 2006. · Zbl 1262.03150
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.