Switch to: References

Add citations

You must login to add citations.
  1. Real Computation with Least Discrete Advice: A Complexity Theory of Nonuniform Computability with Applications to Effective Linear Algebra.Martin Ziegler - 2012 - Annals of Pure and Applied Logic 163 (8):1108-1139.
  • On the (Semi)Lattices Induced by Continuous Reducibilities.Arno Pauly - 2010 - Mathematical Logic Quarterly 56 (5):488-502.
    Continuous reducibilities are a proven tool in Computable Analysis, and have applications in other fields such as Constructive Mathematics or Reverse Mathematics. We study the order-theoretic properties of several variants of the two most important definitions, and especially introduce suprema for them. The suprema are shown to commutate with several characteristic numbers.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  • Computing Links and Accessing Arcs.Timothy H. McNicholl - 2013 - Mathematical Logic Quarterly 59 (1-2):101-107.
    Sufficient conditions are given for the computation of an arc that accesses a point on the boundary of an open subset of the plane from a point within the set. The existence of a not-computably-accessible but computable point on a computably compact arc is also demonstrated.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  • The Open and Clopen Ramsey Theorems in the Weihrauch Lattice.Alberto Marcone & Manlio Valenti - 2021 - Journal of Symbolic Logic 86 (1):316-351.
    We investigate the uniform computational content of the open and clopen Ramsey theorems in the Weihrauch lattice. While they are known to be equivalent to $\mathrm {ATR_0}$ from the point of view of reverse mathematics, there is not a canonical way to phrase them as multivalued functions. We identify eight different multivalued functions and study their degree from the point of view of Weihrauch, strong Weihrauch, and arithmetic Weihrauch reducibility. In particular one of our functions turns out to be strictly (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  • Singular Coverings and Non‐Uniform Notions of Closed Set Computability.Stéphane Le Roux & Martin Ziegler - 2008 - Mathematical Logic Quarterly 54 (5):545-560.
    The empty set of course contains no computable point. On the other hand, surprising results due to Zaslavskiĭ, Tseĭtin, Kreisel, and Lacombe have asserted the existence of non-empty co-r. e. closed sets devoid of computable points: sets which are even “large” in the sense of positive Lebesgue measure.This leads us to investigate for various classes of computable real subsets whether they always contain a computable point.
    Direct download  
     
    Export citation  
     
    Bookmark   5 citations  
  • Finding Descending Sequences Through Ill-Founded Linear Orders.Jun le Goh, Arno Pauly & Manlio Valenti - 2021 - Journal of Symbolic Logic 86 (2):817-854.
    In this work we investigate the Weihrauch degree of the problem Decreasing Sequence of finding an infinite descending sequence through a given ill-founded linear order, which is shared by the problem Bad Sequence of finding a bad sequence through a given non-well quasi-order. We show that $\mathsf {DS}$, despite being hard to solve, is rather weak in terms of uniform computational strength. To make the latter precise, we introduce the notion of the deterministic part of a Weihrauch degree. We then (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  • Searching for an Analogue of Atr0 in the Weihrauch Lattice.Takayuki Kihara, Alberto Marcone & Arno Pauly - 2020 - Journal of Symbolic Logic 85 (3):1006-1043.
    There are close similarities between the Weihrauch lattice and the zoo of axiom systems in reverse mathematics. Following these similarities has often allowed researchers to translate results from one setting to the other. However, amongst the big five axiom systems from reverse mathematics, so far $\mathrm {ATR}_0$ has no identified counterpart in the Weihrauch degrees. We explore and evaluate several candidates, and conclude that the situation is complicated.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  • Universality, Optimality, and Randomness Deficiency.Rupert Hölzl & Paul Shafer - 2015 - Annals of Pure and Applied Logic 166 (10):1049-1069.
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark  
  • Inside the Muchnik Degrees I: Discontinuity, Learnability and Constructivism.K. Higuchi & T. Kihara - 2014 - Annals of Pure and Applied Logic 165 (5):1058-1114.
    Every computable function has to be continuous. To develop computability theory of discontinuous functions, we study low levels of the arithmetical hierarchy of nonuniformly computable functions on Baire space. First, we classify nonuniformly computable functions on Baire space from the viewpoint of learning theory and piecewise computability. For instance, we show that mind-change-bounded learnability is equivalent to finite View the MathML source2-piecewise computability 2 denotes the difference of two View the MathML sourceΠ10 sets), error-bounded learnability is equivalent to finite View (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  • Inside the Muchnik Degrees II: The Degree Structures Induced by the Arithmetical Hierarchy of Countably Continuous Functions.K. Higuchi & T. Kihara - 2014 - Annals of Pure and Applied Logic 165 (6):1201-1241.
    It is known that infinitely many Medvedev degrees exist inside the Muchnik degree of any nontrivial Π10 subset of Cantor space. We shed light on the fine structures inside these Muchnik degrees related to learnability and piecewise computability. As for nonempty Π10 subsets of Cantor space, we show the existence of a finite-Δ20-piecewise degree containing infinitely many finite-2-piecewise degrees, and a finite-2-piecewise degree containing infinitely many finite-Δ20-piecewise degrees 2 denotes the difference of two Πn0 sets), whereas the greatest degrees in (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Turing Degrees in Polish Spaces and Decomposability of Borel Functions.Vassilios Gregoriades, Takayuki Kihara & Keng Meng Ng - 2020 - Journal of Mathematical Logic 21 (1):2050021.
    We give a partial answer to an important open problem in descriptive set theory, the Decomposability Conjecture for Borel functions on an analytic subset of a Polish space to a separable metrizable space. Our techniques employ deep results from effective descriptive set theory and recursion theory. In fact it is essential to extend several prominent results in recursion theory (e.g. the Shore-Slaman Join Theorem) to the setting of Polish spaces. As a by-product we give both positive and negative results on (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • How Incomputable Is the Separable Hahn-Banach Theorem?Guido Gherardi & Alberto Marcone - 2009 - Notre Dame Journal of Formal Logic 50 (4):393-425.
    We determine the computational complexity of the Hahn-Banach Extension Theorem. To do so, we investigate some basic connections between reverse mathematics and computable analysis. In particular, we use Weak König's Lemma within the framework of computable analysis to classify incomputable functions of low complexity. By defining the multivalued function Sep and a natural notion of reducibility for multivalued functions, we obtain a computational counterpart of the subsystem of second-order arithmetic WKL0. We study analogies and differences between WKL0 and the class (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   13 citations  
  • Effective Borel Degrees of Some Topological Functions.Guido Gherardi - 2006 - Mathematical Logic Quarterly 52 (6):625-642.
    The focus of this paper is the incomputability of some topological functions using the tools of Borel computability theory, as introduced by V. Brattka in [3] and [4]. First, we analyze some basic topological functions on closed subsets of ℝn, like closure, border, intersection, and derivative, and we prove for such functions results of Σ02-completeness and Σ03-completeness in the effective Borel hierarchy. Then, following [13], we re-consider two well-known topological results: the lemmas of Urysohn and Urysohn-Tietze for generic metric spaces (...)
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  • 2007 European Summer Meeting of the Association for Symbolic Logic: Logic Colloquium '07.Steffen Lempp - 2008 - Bulletin of Symbolic Logic 14 (1):123-159.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  • Weihrauch Degrees, Omniscience Principles and Weak Computability.Vasco Brattka & Guido Gherardi - 2011 - Journal of Symbolic Logic 76 (1):143 - 176.
    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 (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   15 citations  
  • The Bolzano–Weierstrass Theorem is the Jump of Weak Kőnig’s Lemma.Vasco Brattka, Guido Gherardi & Alberto Marcone - 2012 - Annals of Pure and Applied Logic 163 (6):623-655.
  • On the Uniform Computational Content of Ramsey’s Theorem.Vasco Brattka & Tahina Rakotoniaina - 2017 - Journal of Symbolic Logic 82 (4):1278-1316.
    We study the uniform computational content of Ramsey’s theorem in the Weihrauch lattice. Our central results provide information on how Ramsey’s theorem behaves under product, parallelization, and jumps. From these results we can derive a number of important properties of Ramsey’s theorem. For one, the parallelization of Ramsey’s theorem for cardinalityn≥ 1 and an arbitrary finite number of colorsk≥ 2 is equivalent to then-th jump of weak Kőnig’s lemma. In particular, Ramsey’s theorem for cardinalityn≥ 1 is${\bf{\Sigma }}_{n + 2}^0$-measurable in (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  • On the Uniform Computational Content of the Baire Category Theorem.Vasco Brattka, Matthew Hendtlass & Alexander P. Kreuzer - 2018 - Notre Dame Journal of Formal Logic 59 (4):605-636.
    We study the uniform computational content of different versions of the Baire category theorem in the Weihrauch lattice. The Baire category theorem can be seen as a pigeonhole principle that states that a complete metric space cannot be decomposed into countably many nowhere dense pieces. The Baire category theorem is an illuminating example of a theorem that can be used to demonstrate that one classical theorem can have several different computational interpretations. For one, we distinguish two different logical versions of (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • Effective Choice and Boundedness Principles in Computable Analysis.Vasco Brattka & Guido Gherardi - 2011 - Bulletin of Symbolic Logic 17 (1):73-117.
    In this paper we study a new approach to classify mathematical theorems according to their computational content. Basically, we are asking the question which theorems can be continuously or computably transferred into each other? For this purpose theorems are considered via their realizers which are operations with certain input and output data. The technical tool to express continuous or computable relations between such operations is Weihrauch reducibility and the partially ordered degree structure induced by it. We have identified certain choice (...)
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   18 citations  
  • Closed Choice and a Uniform Low Basis Theorem.Vasco Brattka, Matthew de Brecht & Arno Pauly - 2012 - Annals of Pure and Applied Logic 163 (8):986-1008.
  • Connected Choice and the Brouwer Fixed Point Theorem.Vasco Brattka, Stéphane Le Roux, Joseph S. Miller & Arno Pauly - 2019 - Journal of Mathematical Logic 19 (1):1950004.
    We study the computational content of the Brouwer Fixed Point Theorem in the Weihrauch lattice. Connected choice is the operation that finds a point in a non-empty connected closed set given by negative information. One of our main results is that for any fixed dimension the Brouwer Fixed Point Theorem of that dimension is computably equivalent to connected choice of the Euclidean unit cube of the same dimension. Another main result is that connected choice is complete for dimension greater than (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Borel Complexity and Computability of the Hahn–Banach Theorem.Vasco Brattka - 2008 - Archive for Mathematical Logic 46 (7-8):547-564.
    The classical Hahn–Banach Theorem states that any linear bounded functional defined on a linear subspace of a normed space admits a norm-preserving linear bounded extension to the whole space. The constructive and computational content of this theorem has been studied by Bishop, Bridges, Metakides, Nerode, Shore, Kalantari Downey, Ishihara and others and it is known that the theorem does not admit a general computable version. We prove a new computable version of this theorem without unrolling the classical proof of the (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  • A Computable Version of Banach’s Inverse Mapping Theorem.Vasco Brattka - 2009 - Annals of Pure and Applied Logic 157 (2-3):85-96.
    Given a program of a linear bounded and bijective operator T, does there exist a program for the inverse operator T−1? And if this is the case, does there exist a general algorithm to transfer a program of T into a program of T−1? This is the inversion problem for computable linear operators on Banach spaces in its non-uniform and uniform formulation, respectively. We study this problem from the point of view of computable analysis which is the Turing machine based (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation