35 found
Sort by:
  1. David E. Diamondstone, Damir D. Dzhafarov & Robert I. Soare (2010). $\Pi^0_1$ Classes, Peano Arithmetic, Randomness, and Computable Domination. Notre Dame Journal of Formal Logic 51 (1):127-159.
    We present an overview of the topics in the title and of some of the key results pertaining to them. These have historically been topics of interest in computability theory and continue to be a rich source of problems and ideas. In particular, we draw attention to the links and connections between these topics and explore their significance to modern research in the field.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  2. Robert I. Soare (2009). Turing Oracle Machines, Online Computing, and Three Displacements in Computability Theory. Annals of Pure and Applied Logic 160 (3):368-399.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  3. Barbara F. Csima, Valentina S. Harizanov, Denis R. Hirschfeldt & Robert I. Soare (2007). Bounding Homogeneous Models. Journal of Symbolic Logic 72 (1):305 - 323.
    A Turing degree d is homogeneous bounding if every complete decidable (CD) theory has a d-decidable homogeneous model A, i.e., the elementary diagram De (A) has degree d. It follows from results of Macintyre and Marker that every PA degree (i.e., every degree of a complete extension of Peano Arithmetic) is homogeneous bounding. We prove that in fact a degree is homogeneous bounding if and only if it is a PA degree. We do this by showing that there is a (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  4. Karen Lange & Robert I. Soare (2007). Computability of Homogeneous Models. Notre Dame Journal of Formal Logic 48 (1):143-170.
  5. Barbara F. Csima & Robert I. Soare (2006). Computability Results Used in Differential Geometry. Journal of Symbolic Logic 71 (4):1394 - 1410.
    Topologists Nabutovsky and Weinberger discovered how to embed computably enumerable (c.e.) sets into the geometry of Riemannian metrics modulo diffeomorphisms. They used the complexity of the settling times of the c.e. sets to exhibit a much greater complexity of the depth and density of local minima for the diameter function than previously imagined. Their results depended on the existence of certain sequences of c.e. sets, constructed at their request by Csima and Soare, whose settling times had the necessary dominating properties. (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  6. Barbara F. Csima, Denis R. Hirschfeldt, Julia F. Knight & Robert I. Soare (2004). Bounding Prime Models. Journal of Symbolic Logic 69 (4):1117 - 1142.
    A set X is prime bounding if for every complete atomic decidable (CAD) theory T there is a prime model U of T decidable in X. It is easy to see that $X = 0\prime$ is prime bounding. Denisov claimed that every $X <_{T} 0\prime$ is not prime bounding, but we discovered this to be incorrect. Here we give the correct characterization that the prime bounding sets $X \leq_{T} 0\prime$ are exactly the sets which are not $low_2$ . Recall that (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  7. Robert I. Soare (2004). Computability Theory and Differential Geometry. Bulletin of Symbolic Logic 10 (4):457-486.
    Let M be a smooth, compact manifold of dimension n ≥ 5 and sectional curvature | K | ≤ 1. Let Met (M) = Riem(M)/Diff(M) be the space of Riemannian metrics on M modulo isometries. Nabutovsky and Weinberger studied the connected components of sublevel sets (and local minima) for certain functions on Met (M) such as the diameter. They showed that for every Turing machine T e , e ∈ ω, there is a sequence (uniformly effective in e) of homology (...)
    Direct download (9 more)  
     
    My bibliography  
     
    Export citation  
  8. Klaus Ambos-Spies, Theodore A. Slaman & Robert I. Soare (1998). Preface. Annals of Pure and Applied Logic 94 (1-3):1.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  9. Leo Harrington & Robert I. Soare (1998). Codable Sets and Orbits of Computably Enumerable Sets. Journal of Symbolic Logic 63 (1):1-28.
    A set X of nonnegative integers is computably enumerable (c.e.), also called recursively enumerable (r.e.), if there is a computable method to list its elements. Let ε denote the structure of the computably enumerable sets under inclusion, $\varepsilon = (\{W_e\}_{e\in \omega}, \subseteq)$ . We previously exhibited a first order ε-definable property Q(X) such that Q(X) guarantees that X is not Turing complete (i.e., does not code complete information about c.e. sets). Here we show first that Q(X) implies that X has (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  10. Leo Harrington & Robert I. Soare (1998). Definable Properties of the Computably Enumerable Sets. Annals of Pure and Applied Logic 94 (1-3):97-125.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  11. Alistair H. Lachlan & Robert I. Soare (1998). Models of Arithmetic and Subuniform Bounds for the Arithmetic Sets. Journal of Symbolic Logic 63 (1):59-72.
    It has been known for more than thirty years that the degree of a non-standard model of true arithmetic is a subuniform upper bound for the arithmetic sets (suub). Here a notion of generic enumeration is presented with the property that the degree of such an enumeration is an suub but not the degree of a non-standard model of true arithmetic. This answers a question posed in the literature.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  12. Leo Harrington & Robert I. Soare (1996). Definability, Automorphisms, and Dynamic Properties of Computably Enumerable Sets. Bulletin of Symbolic Logic 2 (2):199-213.
    We announce and explain recent results on the computably enumerable (c.e.) sets, especially their definability properties (as sets in the spirit of Cantor), their automorphisms (in the spirit of Felix Klein's Erlanger Programm), their dynamic properties, expressed in terms of how quickly elements enter them relative to elements entering other sets, and the Martin Invariance Conjecture on their Turing degrees, i.e., their information content with respect to relative computability (Turing reducibility).
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  13. Robert I. Soare (1996). Computability and Recursion. Bulletin of Symbolic Logic 2 (3):284-321.
    We consider the informal concept of "computability" or "effective calculability" and two of the formalisms commonly used to define it, "(Turing) computability" and "(general) recursiveness". We consider their origin, exact technical definition, concepts, history, general English meanings, how they became fixed in their present roles, how they were first and are now used, their impact on nonspecialists, how their use will affect the future content of the subject of computability theory, and its connection to other related areas. After a careful (...)
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  14. Robert I. Soare (1996). Dynamic Properties of Computably Enumerable Sets. In S. B. Cooper, T. A. Slaman & S. S. Wainer (eds.), Computability, Enumerability, Unsolvability: Directions in Recursion Theory. Cambridge University Press. 224--105.
    No categories
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  15. Carl G. Jockusch Jr & Robert I. Soare (1994). Boolean Algebras, Stone Spaces, and the Iterated Turing Jump. Journal of Symbolic Logic 59 (4):1121 - 1138.
    We show, roughly speaking, that it requires ω iterations of the Turing jump to decode nontrivial information from Boolean algebras in an isomorphism invariant fashion. More precisely, if α is a recursive ordinal, A is a countable structure with finite signature, and d is a degree, we say that A has αth-jump degree d if d is the least degree which is the αth jump of some degree c such there is an isomorphic copy of A with universe ω in (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  16. Alistair H. Lachlan & Robert I. Soare (1994). Models of Arithmetic and Upper Bounds for Arithmetic Sets. Journal of Symbolic Logic 59 (3):977-983.
    We settle a question in the literature about degrees of models of true arithmetic and upper bounds for the arithmetic sets. We prove that there is a model of true arithmetic whose degree is not a uniform upper bound for the arithmetic sets. The proof involves two forcing constructions.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  17. Klaus Ambos-Spies, Alistair H. Lachlan & Robert I. Soare (1993). The Continuity of Cupping to 0'. Annals of Pure and Applied Logic 64 (3):195-209.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  18. Carl G. Jockusch & Robert I. Soare (1991). Degrees of Orderings Not Isomorphic to Recursive Linear Orderings. Annals of Pure and Applied Logic 52 (1-2):39-64.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  19. Klaus Ambos-Spies & Robert I. Soare (1989). The Recursively Enumerable Degrees Have Infinitely Many One-Types. Annals of Pure and Applied Logic 44 (1-2):1-23.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  20. Douglas Cenzer, Peter Clote, Rick L. Smith, Robert I. Soare & Stanley S. Wainer (1986). Members of Countable Π10 Classes. Annals of Pure and Applied Logic 31:145-163.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  21. Julia Knight, Alistair H. Lachlan & Robert I. Soare (1984). Two Theorems on Degrees of Models of True Arithmetic. Journal of Symbolic Logic 49 (2):425-436.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  22. Robert I. Soare (1982). Automorphisms of the Lattice of Recursively Enumerable Sets. Part II: Low Sets. Annals of Mathematical Logic 22 (1):69-107.
    No categories
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  23. Carl G. Jockusch Jr, Robert I. Soare, William Tait & Gaisi Takeuti (1978). Meeting of the Association for Symbolic Logic: Chicago, 1977. Journal of Symbolic Logic 43 (3):614 - 619.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  24. Robert I. Soare (1977). Computational Complexity, Speedable and Levelable Sets. Journal of Symbolic Logic 42 (4):545-563.
  25. John Baldwin, D. A. Martin, Robert I. Soare & W. W. Tait (1976). Meeting of the Association for Symbolic Logic. Journal of Symbolic Logic 41 (2):551-560.
  26. Robert I. Soare (1976). The Infinite Injury Priority Method. Journal of Symbolic Logic 41 (2):513-530.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  27. Carl G. Jockusch Jr & Robert I. Soare (1973). Encodability of Kleene's O. Journal of Symbolic Logic 38 (3):437 - 440.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  28. Carl G. Jockusch Jr & Robert I. Soare (1973). Post's Problem and His Hypersimple Set. Journal of Symbolic Logic 38 (3):446 - 452.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  29. Carl G. Jockusch Jr & Robert I. Soare (1971). A Minimal Pair of Π0 1 Classes. Journal of Symbolic Logic 36 (1):66 - 78.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  30. Robin O. Gandy & Robert I. Soare (1970). A Problem in the Theory of Constructive Order Types. Journal of Symbolic Logic 35 (1):119-121.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  31. Robert I. Soare (1969). A Note on Degrees of Subsets. Journal of Symbolic Logic 34 (2):256.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  32. Robert I. Soare (1969). Constructive Order Types on Cuts. Journal of Symbolic Logic 34 (2):285-289.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  33. Robert I. Soare (1969). Sets with No Subset of Higher Degrees. Journal of Symbolic Logic 34 (1):53-56.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation