Switch to: References

Add citations

You must login to add citations.
  1. 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 (...)
    Download  
     
    Export citation  
     
    Bookmark   15 citations  
  • On a metric generalization of the tt-degrees and effective dimension theory.Takayuki Kihara - 2019 - Journal of Symbolic Logic 84 (2):726-749.
    In this article, we study an analogue of tt-reducibility for points in computable metric spaces. We characterize the notion of the metric tt-degree in the context of first-level Borel isomorphism. Then, we study this concept from the perspectives of effective topological dimension theory and of effective fractal dimension theory.
    Download  
     
    Export citation  
     
    Bookmark  
  • Algorithmic randomness over general spaces.Kenshi Miyabe - 2014 - Mathematical Logic Quarterly 60 (3):184-204.
    The study of Martin‐Löf randomness on a computable metric space with a computable measure has seen much progress recently. In this paper we study Martin‐Löf randomness on a more general space, that is, a computable topological space with a computable measure. On such a space, Martin‐Löf randomness may not be a natural notion because there is no universal test, and Martin‐Löf randomness and complexity randomness (defined in this paper) do not coincide in general. We show that SCT3 is a sufficient (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Computable de Finetti measures.Cameron E. Freer & Daniel M. Roy - 2012 - Annals of Pure and Applied Logic 163 (5):530-546.
    Download  
     
    Export citation  
     
    Bookmark   1 citation