Switch to: Citations

Add references

You must login to add references.
  1. Degree spectra and computable dimensions in algebraic structures.Denis R. Hirschfeldt, Bakhadyr Khoussainov, Richard A. Shore & Arkadii M. Slinko - 2002 - Annals of Pure and Applied Logic 115 (1-3):71-113.
    Whenever a structure with a particularly interesting computability-theoretic property is found, it is natural to ask whether similar examples can be found within well-known classes of algebraic structures, such as groups, rings, lattices, and so forth. One way to give positive answers to this question is to adapt the original proof to the new setting. However, this can be an unnecessary duplication of effort, and lacks generality. Another method is to code the original structure into a structure in the given (...)
    Download  
     
    Export citation  
     
    Bookmark   53 citations  
  • Computably Compact Metric Spaces.Rodney G. Downey & Alexander G. Melnikov - 2023 - Bulletin of Symbolic Logic 29 (2):170-263.
    We give a systematic technical exposition of the foundations of the theory of computably compact metric spaces. We discover several new characterizations of computable compactness and apply these characterizations to prove new results in computable analysis and effective topology. We also apply the technique of computable compactness to give new and less combinatorially involved proofs of known results from the literature. Some of these results do not have computable compactness or compact spaces in their statements, and thus these applications are (...)
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • Degree Spectra of Homeomorphism Type of Compact Polish Spaces.Mathieu Hoyrup, Takayuki Kihara & Victor Selivanov - forthcoming - Journal of Symbolic Logic:1-32.
    A Polish space is not always homeomorphic to a computably presented Polish space. In this article, we examine degrees of non-computability of presenting homeomorphic copies of compact Polish spaces. We show that there exists a $\mathbf {0}'$ -computable low $_3$ compact Polish space which is not homeomorphic to a computable one, and that, for any natural number $n\geq 2$, there exists a Polish space $X_n$ such that exactly the high $_{n}$ -degrees are required to present the homeomorphism type of $X_n$. (...)
    Download  
     
    Export citation  
     
    Bookmark   3 citations