Switch to: References

Add citations

You must login to add citations.
  1. Expanding the Reals by Continuous Functions Adds No Computational Power.Uri Andrews, Julia F. Knight, Rutger Kuyper, Joseph S. Miller & Mariya I. Soskova - 2023 - Journal of Symbolic Logic 88 (3):1083-1102.
    We study the relative computational power of structures related to the ordered field of reals, specifically using the notion of generic Muchnik reducibility. We show that any expansion of the reals by a continuous function has no more computing power than the reals, answering a question of Igusa, Knight, and Schweber [7]. On the other hand, we show that there is a certain Borel expansion of the reals that is strictly more powerful than the reals and such that any Borel (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Finitely generated groups are universal among finitely generated structures.Matthew Harrison-Trainor & Meng-Che “Turbo” Ho - 2021 - Annals of Pure and Applied Logic 172 (1):102855.
    Universality has been an important concept in computable structure theory. A class C of structures is universal if, informally, for any structure of any kind there is a structure in C with the same computability-theoretic properties as the given structure. Many classes such as graphs, groups, and fields are known to be universal. This paper is about the class of finitely generated groups. Because finitely generated structures are relatively simple, the class of finitely generated groups has no hope of being (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation