33 found
Order:
Disambiguations
Robert I. Soare [38]Robert Irving Soare [1]
  1. Computability and recursion.Robert I. Soare - 1996 - 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 (9 more)  
     
    Export citation  
     
    Bookmark   52 citations  
  2.  66
    Turing oracle machines, online computing, and three displacements in computability theory.Robert I. Soare - 2009 - Annals of Pure and Applied Logic 160 (3):368-399.
    We begin with the history of the discovery of computability in the 1930’s, the roles of Gödel, Church, and Turing, and the formalisms of recursive functions and Turing automatic machines . To whom did Gödel credit the definition of a computable function? We present Turing’s notion [1939, §4] of an oracle machine and Post’s development of it in [1944, §11], [1948], and finally Kleene-Post [1954] into its present form. A number of topics arose from Turing functionals including continuous functionals on (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   18 citations  
  3.  41
    Degrees of orderings not isomorphic to recursive linear orderings.Carl G. Jockusch & Robert I. Soare - 1991 - Annals of Pure and Applied Logic 52 (1-2):39-64.
    It is shown that for every nonzero r.e. degree c there is a linear ordering of degree c which is not isomorphic to any recursive linear ordering. It follows that there is a linear ordering of low degree which is not isomorphic to any recursive linear ordering. It is shown further that there is a linear ordering L such that L is not isomorphic to any recursive linear ordering, and L together with its ‘infinitely far apart’ relation is of low (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   23 citations  
  4.  52
    Members of countable π10 classes.Douglas Cenzer, Peter Clote, Rick L. Smith, Robert I. Soare & Stanley S. Wainer - 1986 - Annals of Pure and Applied Logic 31:145-163.
  5. The infinite injury priority method.Robert I. Soare - 1976 - Journal of Symbolic Logic 41 (2):513-530.
  6.  62
    Computational complexity, speedable and levelable sets.Robert I. Soare - 1977 - Journal of Symbolic Logic 42 (4):545-563.
  7.  21
    The recursively enumerable degrees have infinitely many one-types.Klaus Ambos-Spies & Robert I. Soare - 1989 - Annals of Pure and Applied Logic 44 (1-2):1-23.
  8. Computability theory and differential geometry.Robert I. Soare - 2004 - 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 (12 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  9. (1 other version)Definability, automorphisms, and dynamic properties of computably enumerable sets.Leo Harrington & Robert I. Soare - 1996 - 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 (8 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  10.  51
    Π 1 0 Classes, Peano Arithmetic, Randomness, and Computable Domination.David E. Diamondstone, Damir D. Dzhafarov & Robert I. Soare - 2010 - 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 (6 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  11.  23
    The continuity of cupping to 0'.Klaus Ambos-Spies, Alistair H. Lachlan & Robert I. Soare - 1993 - Annals of Pure and Applied Logic 64 (3):195-209.
    It is shown that, if a, b are recursively enumerable degrees such that 0
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  12.  95
    Bounding Prime Models.Barbara F. Csima, Denis R. Hirschfeldt, Julia F. Knight & Robert I. Soare - 2004 - 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 (6 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  13.  36
    Boolean Algebras, Stone Spaces, and the Iterated Turing Jump.Carl G. Jockusch & Robert I. Soare - 1994 - 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 (6 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  14. Sets with no subset of higher degrees.Robert I. Soare - 1969 - Journal of Symbolic Logic 34 (1):53-56.
  15.  18
    Degrees of Models of True Arithmetic.David Marker, J. Stern, Julia Knight, Alistair H. Lachlan & Robert I. Soare - 1987 - Journal of Symbolic Logic 52 (2):562-563.
  16.  60
    Definable properties of the computably enumerable sets.Leo Harrington & Robert I. Soare - 1998 - Annals of Pure and Applied Logic 94 (1-3):97-125.
    Post in 1944 began studying properties of a computably enumerable set A such as simple, h-simple, and hh-simple, with the intent of finding a property guaranteeing incompleteness of A . From the observations of Post and Myhill , attention focused by the 1950s on properties definable in the inclusion ordering of c.e. subsets of ω, namely E = . In the 1950s and 1960s Tennenbaum, Martin, Yates, Sacks, Lachlan, Shoenfield and others produced a number of elegant results relating ∄-definable properties (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  17.  74
    Dynamic properties of computably enumerable sets.Robert I. Soare - 1996 - In S. B. Cooper, T. A. Slaman & S. S. Wainer (eds.), Computability, enumerability, unsolvability: directions in recursion theory. New York: Cambridge University Press. pp. 224--105.
  18.  38
    Computability of Homogeneous Models.Karen Lange & Robert I. Soare - 2007 - Notre Dame Journal of Formal Logic 48 (1):143-170.
    In the last five years there have been a number of results about the computable content of the prime, saturated, or homogeneous models of a complete decidable theory T in the spirit of Vaught's "Denumerable models of complete theories" combined with computability methods for degrees d ≤ 0′. First we recast older results by Goncharov, Peretyat'kin, and Millar in a more modern framework which we then apply. Then we survey recent results by Lange, "The degree spectra of homogeneous models," which (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  19.  50
    Encodability of Kleene's O.Carl G. Jockusch & Robert I. Soare - 1973 - Journal of Symbolic Logic 38 (3):437 - 440.
  20.  60
    Models of arithmetic and upper Bounds for arithmetic sets.Alistair H. Lachlan & Robert I. Soare - 1994 - 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 (8 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  21.  52
    Bounding Homogeneous Models.Barbara F. Csima, Valentina S. Harizanov, Denis R. Hirschfeldt & Robert I. Soare - 2007 - 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)  
     
    Export citation  
     
    Bookmark   2 citations  
  22.  95
    Computability Results Used in Differential Geometry.Barbara F. Csima & Robert I. Soare - 2006 - 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 (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  23.  29
    Post's Problem and His Hypersimple Set.Carl G. Jockusch & Robert I. Soare - 1973 - Journal of Symbolic Logic 38 (3):446 - 452.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  24.  23
    A minimal pair of Π1 0 classes.Carl G. Jockusch & Robert I. Soare - 1971 - Journal of Symbolic Logic 36 (1):66-78.
  25.  32
    Two theorems on degrees of models of true arithmetic.Julia Knight, Alistair H. Lachlan & Robert I. Soare - 1984 - Journal of Symbolic Logic 49 (2):425-436.
  26. (1 other version)Meeting of the association for symbolic logic.John Baldwin, D. A. Martin, Robert I. Soare & W. W. Tait - 1976 - Journal of Symbolic Logic 41 (2):551-560.
  27. A note on degrees of subsets.Robert I. Soare - 1969 - Journal of Symbolic Logic 34 (2):256.
    In [2] we constructed an infinite set of natural numbers containing no subset of higher (Turing) degree. Since it is well known that there are nonrecursive sets (e.g. sets of minimal degree) containing no nonrecursive subset of lower degree, it is natural to suppose that these arguments may be combined, but this is false. We prove that every infinite set must contain a nonrecursive subset of either higher or lower degree.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  28.  29
    Preface.Klaus Ambos-Spies, Theodore A. Slaman & Robert I. Soare - 1998 - Annals of Pure and Applied Logic 94 (1-3):1.
  29.  16
    Corrigendum to “The d.r.e. degrees are not dense” [Ann. Pure Appl. Logic 55 (1991) 125–151].S. Barry Cooper, Leo Harrington, Alistair H. Lachlan, Steffen Lempp & Robert I. Soare - 2017 - Annals of Pure and Applied Logic 168 (12):2164-2165.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  30.  44
    Meeting of the Association for Symbolic Logic, Chicago, 1977.Carl G. Jockusch, Robert I. Soare, William Tait & Gaisi Takeuti - 1978 - Journal of Symbolic Logic 43 (3):614 - 619.
  31.  95
    A problem in the theory of constructive order types.Robin O. Gandy & Robert I. Soare - 1970 - Journal of Symbolic Logic 35 (1):119-121.
    J. N. Crossley [1] raised the question of whether the implication 2 + A = A ⇒ 1 + A = A is true for constructive order types (C.O.T.'s). Using an earlier definition of constructive order type, A. G. Hamilton [2] presented a counterexample. Hamilton left open the general question, however, since he pointed out that Crossley considers only orderings which can be embedded in a standard dense r.e. ordering by a partial recursive function, and that his counterexample fails to (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark  
  32.  7
    Logic year 1979-80, the University of Connecticut, USA.Manuel Lerman, James Henry Schmerl & Robert Irving Soare (eds.) - 1981 - New York: Springer Verlag.
  33.  32
    Constructive order types on cuts.Robert I. Soare - 1969 - Journal of Symbolic Logic 34 (2):285-289.
    If A and B are subsets of natural numbers we say that A is recursively equivalent to B (denoted A ≃ B) if there is a one-one partial recursive function which maps A onto B, and that A is recursively isomorphic to B (denoted A ≅ B) if there is a one-one total recursive function which maps A onto B and Ā (the complement of A) onto B#x00AF;.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark