Hostname: page-component-78c5997874-v9fdk Total loading time: 0 Render date: 2024-11-07T23:29:57.881Z Has data issue: false hasContentIssue false
  • English
  • Français

Weihrauch degrees, omniscience principles and weak computability

Published online by Cambridge University Press:  12 March 2014

Vasco Brattka  and
Guido Gherardi
Vasco Brattka
Affiliation:
Laboratory of Foundational Aspects of Computer Science, Department of Mathematics & Applied Mathematics, University of Cape Town, Rondebosch 7701, South Africa, E-mail: [email protected]
Guido Gherardi
Affiliation:
Dipartimento di Filosofia, Università di Bologna, Italy, E-mail: [email protected], URL: http://cca-net.de/
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we study a reducibility that has been introduced by Klaus Weihrauch or, more precisely, a natural extension for multi-valued functions on represented spaces. We call the corresponding equivalence classes Weihrauch degrees and we show that the corresponding partial order induces a lower semi-lattice. It turns out that parallelization is a closure operator for this semi-lattice and that the parallelized Weihrauch degrees even form a lattice into which the Medvedev lattice and the Turing degrees can be embedded. The importance of Weihrauch degrees is based on the fact that multi-valued functions on represented spaces can be considered as realizers of mathematical theorems in a very natural way and studying the Weihrauch reductions between theorems in this sense means to ask which theorems can be transformed continuously or computably into each other. As crucial corner points of this classification scheme the limited principle of omniscience LPO, the lesser limited principle of omniscience LLPO and their parallelizations are studied. It is proved that parallelized LLPO is equivalent to Weak Kőnig's Lemma and hence to the Hahn–Banach Theorem in this new and very strong sense. We call a multi-valued function weakly computable if it is reducible to the Weihrauch degree of parallelized LLPO and we present a new proof, based on a computational version of Kleene's ternary logic, that the class of weakly computable operations is closed under composition. Moreover, weakly computable operations on computable metric spaces are characterized as operations that admit upper semi-computable compact-valued selectors and it is proved that any single-valued weakly computable operation is already computable in the ordinary sense.

Keywords

03F6003D30O3B30O3E15Computable analysisconstructive analysisreverse mathematicseffective descriptive set theory
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 76 , Issue 1 , March 2011 , pp. 143 - 176
Copyright
Copyright © Association for Symbolic Logic 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Bishop, Errett and Bridges, Douglas S., Constructive analysis, Grundlehren der Mathematischen Wissenschaften, vol. 279, Springer, Berlin, 1985.CrossRefGoogle Scholar
[2]Brattka, Vasco, Computable invariance, Theoretical Computer Science, vol. 210 (1999), pp. 3–20.CrossRefGoogle Scholar
[3]Brattka, Vasco, Computable versions of Baire's category theorem, Proceedings of the 26th international symposium on Mathematical Foundations of Computer Science 2001, Mariánské Lázné, Czech Republic, August 27–31, 2001 (Sgall, Jiří, Pultr, Aleš, and Kolman, Petr, editors), Lecture Notes in Computer Science, vol. 2136, Springer, Berlin, 2001, pp. 224–235.Google Scholar
[4]Brattka, Vasco, Effective Borel measurability and reducibility of functions, Mathematical Logic Quarterly, vol. 51 (2005), no. 1, pp. 19–44.CrossRefGoogle Scholar
[5]Brattka, Vasco, Plottable real number functions and the computable graph theorem, SIAM Journal on Computing, vol. 38 (2008), no. 1, pp. 303–328.CrossRefGoogle Scholar
[6]Brattka, Vasco and Gherardi, Guido, Weihrauch degrees, omniscience principles and weak computability, Proceedings of the sixth international conference on Computability and Complexity in Analysis, CCA 2009 (Bauer, Andrej, Hertling, Peter, and Ko, Ker-I, editors), Leibniz-Zentrum für Informatik, Schloss Dagstuhl, Germany, 2009, pp. 83–94.Google Scholar
[7]Brattka, Vasco and Gherardi, Guido, Effective choice and boundedness principles in computable analysis, The Bulletin of Symbolic Logic, vol. 17 (2011), no. 1, pp. 73–117.CrossRefGoogle Scholar
[8]Brattka, Vasco and Presser, Gero, Computability on subsets of metric spaces, Theoretical Computer Science, vol. 305 (2003), pp. 43–76.CrossRefGoogle Scholar
[9]Bridges, Douglas and Richman, Fred, Varieties of constructive mathematics, London Mathematical Society Lecture Note Series, vol. 97, Cambridge University Press, Cambridge, 1987.CrossRefGoogle Scholar
[10]Gherardi, Guido and Marcone, Alberto, HOW incomputable is the separable Hahn–Banach theorem?, Notre Dame Journal of Formal Logic, vol. 50 (2009), pp. 393–425.CrossRefGoogle Scholar
[11]Hertling, Peter, Unstetigkeitsgrade von Funktionen in der effektiven Analysis, Dissertation, FernUniversität Hagen, Hagen, 11 1996.Google Scholar
[12]Hirsch, Michael D., Applications of topology to lower bound estimates in computer science, From topology to computation: Proceedings of the Smalefest (New York) (Hirsch, M. W., Marsden, J. E., and Shub, M., editors), Springer, 1993, pp. 395–418.CrossRefGoogle Scholar
[13]Ishihara, Hajime, Unique existence and computability in constructive reverse mathematics, Computation and logic in the real world, CiE 2007 (Cooper, S. Barry, Löwe, Benedikt, and Sorbi, Andrea, editors), Lecture Notes in Computer Science, vol. 4497, Springer, Berlin, 2007, pp. 368–377.CrossRefGoogle Scholar
[14]Kohlenbach, Ulrich, Effective moduli from ineffective uniqueness proofs. An unwinding of de La Vallé Poussin's prooffor Chebycheff approximation, Annals of Pure and Applied Logic, vol. 64 (1993), pp. 27–94.CrossRefGoogle Scholar
[15]Michael, Ernest, Topologies on spaces of subsets, Transactions of the American Mathematical Society, vol. 71 (1951), no. 1, pp. 152–182.CrossRefGoogle Scholar
[16]Mylatz, Uwe, Vergleich unstetiger Funktionen in der Analysis, Diplomarbeit, FernUniversität Hagen, 1992.Google Scholar
[17]Mylatz, Uwe, Vergleich unstetiger Funktionen: “Principle of Omniscience” und Vollständigkeit in der C–hierarchic, Ph.D. thesis, Faculty for Mathematics and Computer Science, University Hägen, Germany, 2006.Google Scholar
[18]Odifreddi, Piergiorgio, Classical recursion theory, Studies in Logic and the Foundations of Mathematics, vol. 125, North-Holland, Amsterdam, 1989.Google Scholar
[19]Pauly, Arno, On the (semi)lattices induced by continuous reducibilities, Mathematical Logic Quarterly, (to appear), preliminary version: http://arxiv.org/abs/0903.2177.Google Scholar
[20]Rogers, Hartley, Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[21]Schröder, Matthias, Extended admissibility, Theoretical Computer Science, vol. 284 (2002), no. 2, pp. 519–538.CrossRefGoogle Scholar
[22]Schuster, Peter, Unique solutions, Mathematical Logic Quarterly, vol. 52 (2006), no. 6, pp. 534–539.CrossRefGoogle Scholar
[23]Schuster, Peter, Corrigendum to “unique solutions”, Mathematical Logic Quarterly, vol. 53 (2007), no. 2, pp. 214–214.CrossRefGoogle Scholar
[24]Simpson, Stephen, Tanaka, Kazuyuki, and Yamazaki, Takeshi, Some conservation results on weak König's lemma, Annals of Pure and Applied Logic, vol. 118 (2002), no. 1–2, pp. 87–114.CrossRefGoogle Scholar
[25]Simpson, Stephen G., Subsystems of second order arithmetic, Perspectives in Mathematical Logic, Springer, Berlin, 1999.CrossRefGoogle Scholar
[26]Soare, Robert I., Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer, Berlin, 1987.CrossRefGoogle Scholar
[27]von Stein, Thorsten, Vergleich nicht konstruktiv lösbarer Probleme in der Analysis, Diplomarbeit, FernUniversität Hagen, 1989.Google Scholar
[28]Weihrauch, Klaus, The degrees of discontinuity of some translators between representations of the real numbers, Technical report TR-92-050, International Computer Science Institute, Berkeley, 07 1992.Google Scholar
[29]Weihrauch, Klaus, The TTE-interpretation of three hierarchies of omniscience principles, Informatik Berichte, vol. 130, FernUniversität Hagen, Hagen, 09 1992.Google Scholar
[30]Weihrauch, Klaus, Computable analysis, Springer, Berlin, 2000.CrossRefGoogle Scholar
[31]Weihrauch, Klaus, Computational complexity on computable metric spaces, Mathematical Logic Quarterly, vol. 49 (2003), no. 1, pp. 3–21.CrossRefGoogle Scholar