157 found
Order:
Disambiguations
Rod Downey [81]R. G. Downey [29]Rodney G. Downey [27]R. Downey [15]
Rodney Downey [7]Rod G. Downey [4]Rod& Nies Downey [1]Rodney Graham Downey [1]

Not all matches are shown. Search with initial or firstname to single out others.

  1.  89
    Calibrating randomness.Rod Downey, Denis R. Hirschfeldt, André Nies & Sebastiaan A. Terwijn - 2006 - Bulletin of Symbolic Logic 12 (3):411-491.
    We report on some recent work centered on attempts to understand when one set is more random than another. We look at various methods of calibration by initial segment complexity, such as those introduced by Solovay [125], Downey, Hirschfeldt, and Nies [39], Downey, Hirschfeldt, and LaForte [36], and Downey [31]; as well as other methods such as lowness notions of Kučera and Terwijn [71], Terwijn and Zambella [133], Nies [101, 100], and Downey, Griffiths, and Reid [34]; higher level randomness notions (...)
    Direct download (11 more)  
     
    Export citation  
     
    Bookmark   29 citations  
  2.  19
    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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  3.  27
    Foundations of online structure theory.Nikolay Bazhenov, Rod Downey, Iskander Kalimullin & Alexander Melnikov - 2019 - Bulletin of Symbolic Logic 25 (2):141-181.
    The survey contains a detailed discussion of methods and results in the new emerging area of online “punctual” structure theory. We also state several open problems.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  4.  11
    [Omnibus Review].Rod Downey - 1997 - Journal of Symbolic Logic 62 (3):1048-1055.
    Robert I. Soare, Automorphisms of the Lattice of Recursively Enumerable Sets. Part I: Maximal Sets.Manuel Lerman, Robert I. Soare, $d$-Simple Sets, Small Sets, and Degree Classes.Peter Cholak, Automorphisms of the Lattice of Recursively Enumerable Sets.Leo Harrington, Robert I. Soare, The $\Delta^0_3$-Automorphism Method and Noninvariant Classes of Degrees.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   24 citations  
  5.  41
    Relativizing chaitin's halting probability.Rod Downey, Denis R. Hirschfeldt, Joseph S. Miller & André Nies - 2005 - Journal of Mathematical Logic 5 (02):167-192.
    As a natural example of a 1-random real, Chaitin proposed the halting probability Ω of a universal prefix-free machine. We can relativize this example by considering a universal prefix-free oracle machine U. Let [Formula: see text] be the halting probability of UA; this gives a natural uniform way of producing an A-random real for every A ∈ 2ω. It is this operator which is our primary object of study. We can draw an analogy between the jump operator from computability theory (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   19 citations  
  6.  31
    Splitting theorems in recursion theory.Rod Downey & Michael Stob - 1993 - Annals of Pure and Applied Logic 65 (1):1-106.
    A splitting of an r.e. set A is a pair A1, A2 of disjoint r.e. sets such that A1 A2 = A. Theorems about splittings have played an important role in recursion theory. One of the main reasons for this is that a splitting of A is a decomposition of A in both the lattice, , of recursively enumerable sets and in the uppersemilattice, R, of recursively enumerable degrees . Thus splitting theor ems have been used to obtain results about (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   18 citations  
  7.  8
    Lattice nonembeddings and initial segments of the recursively enumerable degrees.Rod Downey - 1990 - Annals of Pure and Applied Logic 49 (2):97-119.
  8.  32
    Countable thin Π01 classes.Douglas Cenzer, Rodney Downey, Carl Jockusch & Richard A. Shore - 1993 - Annals of Pure and Applied Logic 59 (2):79-139.
    Cenzer, D., R. Downey, C. Jockusch and R.A. Shore, Countable thin Π01 classes, Annals of Pure and Applied Logic 59 79–139. A Π01 class P {0, 1}ω is thin if every Π01 subclass of P is the intersection of P with some clopen set. Countable thin Π01 classes are constructed having arbitrary recursive Cantor- Bendixson rank. A thin Π01 class P is constructed with a unique nonisolated point A and furthermore A is of degree 0’. It is shown that no (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   13 citations  
  9.  26
    Computably enumerable sets and quasi-reducibility.R. Downey, G. LaForte & A. Nies - 1998 - Annals of Pure and Applied Logic 95 (1-3):1-35.
    We consider the computably enumerable sets under the relation of Q-reducibility. We first give several results comparing the upper semilattice of c.e. Q-degrees, RQ, Q, under this reducibility with the more familiar structure of the c.e. Turing degrees. In our final section, we use coding methods to show that the elementary theory of RQ, Q is undecidable.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   13 citations  
  10. Computability theory and linear orders.Rod Downey - 1998 - In IUrii Leonidovich Ershov (ed.), Handbook of recursive mathematics. New York: Elsevier. pp. 138--823.
     
    Export citation  
     
    Bookmark   13 citations  
  11.  22
    On Schnorr and computable randomness, martingales, and machines.Rod Downey, Evan Griffiths & Geoffrey Laforte - 2004 - Mathematical Logic Quarterly 50 (6):613-627.
    We examine the randomness and triviality of reals using notions arising from martingales and prefix-free machines.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark   13 citations  
  12.  44
    Asymptotic density and computably enumerable sets.Rodney G. Downey, Carl G. Jockusch & Paul E. Schupp - 2013 - Journal of Mathematical Logic 13 (2):1350005.
    We study connections between classical asymptotic density, computability and computable enumerability. In an earlier paper, the second two authors proved that there is a computably enumerable set A of density 1 with no computable subset of density 1. In the current paper, we extend this result in three different ways: The degrees of such sets A are precisely the nonlow c.e. degrees. There is a c.e. set A of density 1 with no computable subset of nonzero density. There is a (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  13.  46
    On the C.E. Degrees Realizable in Classes.Barbara F. Csima, Rod Downey & N. G. Keng Meng - forthcoming - Journal of Symbolic Logic:1-26.
    We study for each computably bounded $\Pi ^0_1$ class P the set of degrees of c.e. paths in P. We show, amongst other results, that for every c.e. degree a there is a perfect $\Pi ^0_1$ class where all c.e. members have degree a. We also show that every $\Pi ^0_1$ set of c.e. indices is realized in some perfect $\Pi ^0_1$ class, and classify the sets of c.e. degrees which can be realized in some $\Pi ^0_1$ class as exactly (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  14.  61
    Highness and bounding minimal pairs.Rodney G. Downey, Steffen Lempp & Richard A. Shore - 1993 - Mathematical Logic Quarterly 39 (1):475-491.
  15.  24
    Structural interactions of the recursively enumerable T- and W-degrees.R. G. Downey & M. Stob - 1986 - Annals of Pure and Applied Logic 31:205-236.
  16.  67
    A Δ20 set with no infinite low subset in either it or its complement.Rod Downey, Denis R. Hirschfeldt, Steffen Lempp & Reed Solomon - 2001 - Journal of Symbolic Logic 66 (3):1371-1381.
    We construct the set of the title, answering a question of Cholak, Jockusch, and Slaman [1], and discuss its connections with the study of the proof-theoretic strength and effective content of versions of Ramsey's Theorem. In particular, our result implies that every ω-model of RCA 0 + SRT 2 2 must contain a nonlow set.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  17.  22
    A Hierarchy of Computably Enumerable Degrees.Rod Downey & Noam Greenberg - 2018 - Bulletin of Symbolic Logic 24 (1):53-89.
    We introduce a new hierarchy of computably enumerable degrees. This hierarchy is based on computable ordinal notations measuring complexity of approximation of${\rm{\Delta }}_2^0$functions. The hierarchy unifies and classifies the combinatorics of a number of diverse constructions in computability theory. It does so along the lines of the high degrees (Martin) and the array noncomputable degrees (Downey, Jockusch, and Stob). The hierarchy also gives a number of natural definability results in the c.e. degrees, including a definable antichain.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  18.  86
    Completely mitotic R.E. degrees.R. G. Downey & T. A. Slaman - 1989 - Annals of Pure and Applied Logic 41 (2):119-152.
  19.  37
    Jumps of Hemimaximal Sets.Rod Downey & Mike Stob - 1991 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 37 (8):113-120.
  20.  19
    Punctual Categoricity and Universality.Rod Downey, Noam Greenberg, Alexander Melnikov, Keng Meng Ng & Daniel Turetsky - 2020 - Journal of Symbolic Logic 85 (4):1427-1466.
    We describe punctual categoricity in several natural classes, including binary relational structures and mono-unary functional structures. We prove that every punctually categorical structure in a finite unary language is${\text {PA}}(0')$-categorical, and we show that this upper bound is tight. We also construct an example of a punctually categorical structure whose degree of categoricity is$0''$. We also prove that, with a bit of work, the latter result can be pushed beyond$\Delta ^1_1$, thus showing that punctually categorical structures can possess arbitrarily complex (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  21.  20
    Relationships between computability-theoretic properties of problems.Rod Downey, Noam Greenberg, Matthew Harrison-Trainor, Ludovic Patey & Dan Turetsky - 2022 - Journal of Symbolic Logic 87 (1):47-71.
    A problem is a multivalued function from a set of instances to a set of solutions. We consider only instances and solutions coded by sets of integers. A problem admits preservation of some computability-theoretic weakness property if every computable instance of the problem admits a solution relative to which the property holds. For example, cone avoidance is the ability, given a noncomputable set A and a computable instance of a problem ${\mathsf {P}}$, to find a solution relative to which A (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  22.  29
    Recursion theory and ordered groups.R. G. Downey & Stuart A. Kurtz - 1986 - Annals of Pure and Applied Logic 32:137-151.
  23.  85
    Lowness and Π₂⁰ nullsets.Rod Downey, Andre Nies, Rebecca Weber & Liang Yu - 2006 - Journal of Symbolic Logic 71 (3):1044-1052.
    We prove that there exists a noncomputable c.e. real which is low for weak 2-randomness, a definition of randomness due to Kurtz, and that all reals which are low for weak 2-randomness are low for Martin-Löf randomness.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  24.  33
    Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.
    Schnorr randomness is a notion of algorithmic randomness for real numbers closely related to Martin-Löf randomness. After its initial development in the 1970s the notion received considerably less attention than Martin-Löf randomness, but recently interest has increased in a range of randomness concepts. In this article, we explore the properties of Schnorr random reals, and in particular the c.e. Schnorr random reals. We show that there are c.e. reals that are Schnorr random but not Martin-Löf random, and provide a new (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  25.  28
    Jumps of Hemimaximal Sets.Rod Downey & Mike Stob - 1991 - Mathematical Logic Quarterly 37 (8):113-120.
  26.  97
    Totally ω-computably enumerable degrees and bounding critical triples.Rod Downey, Noam Greenberg & Rebecca Weber - 2007 - Journal of Mathematical Logic 7 (2):145-171.
    We characterize the class of c.e. degrees that bound a critical triple as those degrees that compute a function that has no ω-c.e. approximation.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  27.  19
    On a question of A. Retzlaff.Rod Downey - 1983 - Mathematical Logic Quarterly 29 (6):379-384.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark   9 citations  
  28.  36
    Minimal degrees recursive in 1-generic degrees.C. T. Chong & R. G. Downey - 1990 - Annals of Pure and Applied Logic 48 (3):215-225.
  29.  57
    Classifications of degree classes associated with r.e. subspaces.R. G. Downey & J. B. Remmel - 1989 - Annals of Pure and Applied Logic 42 (2):105-124.
    In this article we show that it is possible to completely classify the degrees of r.e. bases of r.e. vector spaces in terms of weak truth table degrees. The ideas extend to classify the degrees of complements and splittings. Several ramifications of the classification are discussed, together with an analysis of the structure of the degrees of pairs of r.e. summands of r.e. spaces.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  30.  30
    On $\Pi^0_1$ classes and their ranked points.Rod Downey - 1991 - Notre Dame Journal of Formal Logic 32 (4):499-512.
  31.  23
    On Δ 2 0 -categoricity of equivalence relations.Rod Downey, Alexander G. Melnikov & Keng Meng Ng - 2015 - Annals of Pure and Applied Logic 166 (9):851-880.
  32.  33
    Maximal theories.R. G. Downey - 1987 - Annals of Pure and Applied Logic 33 (C):245-282.
  33.  37
    Undecidability of L(F∞) and other lattices of r.e. substructures.R. G. Downey - 1986 - Annals of Pure and Applied Logic 32:17-26.
  34.  25
    Abelian p-groups and the Halting problem.Rodney Downey, Alexander G. Melnikov & Keng Meng Ng - 2016 - Annals of Pure and Applied Logic 167 (11):1123-1138.
  35.  56
    Automorphisms of supermaximal subspaces.R. G. Downey & G. R. Hird - 1985 - Journal of Symbolic Logic 50 (1):1-9.
  36.  20
    There is no fat orbit.Rod Downey & Leo Harrington - 1996 - Annals of Pure and Applied Logic 80 (3):277-289.
    We give a proof of a theorem of Harrington that there is no orbit of the lattice of recursively enumerable sets containing elements of each nonzero recursively enumerable degree. We also establish some degree theoretical extensions.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  37.  24
    Asymptotic density and the Ershov hierarchy.Rod Downey, Carl Jockusch, Timothy H. McNicholl & Paul Schupp - 2015 - Mathematical Logic Quarterly 61 (3):189-195.
    We classify the asymptotic densities of the sets according to their level in the Ershov hierarchy. In particular, it is shown that for, a real is the density of an n‐c.e. set if and only if it is a difference of left‐ reals. Further, we show that the densities of the ω‐c.e. sets coincide with the densities of the sets, and there are ω‐c.e. sets whose density is not the density of an n‐c.e. set for any.
    No categories
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  38.  16
    Splitting into degrees with low computational strength.Rod Downey & Keng Meng Ng - 2018 - Annals of Pure and Applied Logic 169 (8):803-834.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  39.  58
    Limits on jump inversion for strong reducibilities.Barbara F. Csima, Rod Downey & Keng Meng Ng - 2011 - Journal of Symbolic Logic 76 (4):1287-1296.
    We show that Sacks' and Shoenfield's analogs of jump inversion fail for both tt- and wtt-reducibilities in a strong way. In particular we show that there is a ${\mathrm{\Delta }}_{2}^{0}$ set B > tt ∅′ such that there is no c.e. set A with A′ ≡ wtt B. We also show that there is a ${\mathrm{\Sigma }}_{2}^{0}$ set C > tt ∅′ such that there is no ${\mathrm{\Delta }}_{2}^{0}$ set D with D′ ≡ wtt C.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  40.  73
    Decidable subspaces and recursively enumerable subspaces.C. J. Ash & R. G. Downey - 1984 - Journal of Symbolic Logic 49 (4):1137-1145.
    A subspace V of an infinite dimensional fully effective vector space V ∞ is called decidable if V is r.e. and there exists an r.e. W such that $V \oplus W = V_\infty$ . These subspaces of V ∞ are natural analogues of recursive subsets of ω. The set of r.e. subspaces forms a lattice L(V ∞ ) and the set of decidable subspaces forms a lower semilattice S(V ∞ ). We analyse S(V ∞ ) and its relationship with L(V (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  41.  65
    Co-immune subspaces and complementation in V∞.R. Downey - 1984 - Journal of Symbolic Logic 49 (2):528 - 538.
    We examine the multiplicity of complementation amongst subspaces of V ∞ . A subspace V is a complement of a subspace W if V ∩ W = {0} and (V ∪ W) * = V ∞ . A subspace is called fully co-r.e. if it is generated by a co-r.e. subset of a recursive basis of V ∞ . We observe that every r.e. subspace has a fully co-r.e. complement. Theorem. If S is any fully co-r.e. subspace then S has (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  42.  69
    Degree theoretic definitions of the low2 recursively enumerable sets.Rod Downey & Richard A. Shore - 1995 - Journal of Symbolic Logic 60 (3):727 - 756.
  43.  17
    Every recursive boolean algebra is isomorphic to one with incomplete atoms.Rod Downey - 1993 - Annals of Pure and Applied Logic 60 (3):193-206.
    The theorem of the title is proven, solving an old question of Remmel. The method of proof uses an algebraic technique of Remmel-Vaught combined with a complex tree of strategies argument where the true path is needed to figure out the final isomorphism.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  44.  31
    Friedberg splittings of recursively enumerable sets.Rod Downey & Michael Stob - 1993 - Annals of Pure and Applied Logic 59 (3):175-199.
    A splitting A1A2 = A of an r.e. set A is called a Friedberg splitting if for any r.e. set W with W — A not r.e., W — Ai≠0 for I = 1,2. In an earlier paper, the authors investigated Friedberg splittings of maximal sets and showed that they formed an orbit with very interesting degree-theoretical properties. In the present paper we continue our investigations, this time analyzing Friedberg splittings and in particular their orbits and degrees for various classes (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  45.  51
    Splitting properties of R. E. sets and degrees.R. G. Downey & L. V. Welch - 1986 - Journal of Symbolic Logic 51 (1):88-109.
  46.  39
    The Kolmogorov complexity of random reals.Liang Yu, Decheng Ding & Rodney Downey - 2004 - Annals of Pure and Applied Logic 129 (1-3):163-180.
    We investigate the initial segment complexity of random reals. Let K denote prefix-free Kolmogorov complexity. A natural measure of the relative randomness of two reals α and β is to compare complexity K and K. It is well-known that a real α is 1-random iff there is a constant c such that for all n, Kn−c. We ask the question, what else can be said about the initial segment complexity of random reals. Thus, we study the fine behaviour of K (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  47.  37
    A Friedberg enumeration of equivalence structures.Rodney G. Downey, Alexander G. Melnikov & Keng Meng Ng - 2017 - Journal of Mathematical Logic 17 (2):1750008.
    We solve a problem posed by Goncharov and Knight 639–681, 757]). More specifically, we produce an effective Friedberg enumeration of computable equivalence structures, up to isomorphism. We also prove that there exists an effective Friedberg enumeration of all isomorphism types of infinite computable equivalence structures.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  48.  37
    Some orbits for E.Peter Cholak, Rod Downey & Eberhard Herrmann - 2001 - Annals of Pure and Applied Logic 107 (1-3):193-226.
    In this article we establish the existence of a number of new orbits in the automorphism group of the computably enumerable sets. The degree theoretical aspects of these orbits also are examined.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  49.  10
    Some remarks on a theorem of Iraj Kalantari concerning convexity and recursion theory.R. Downey - 1984 - Mathematical Logic Quarterly 30 (19‐24):295-302.
  50.  31
    Some Remarks on a Theorem of Iraj Kalantari Concerning Convexity and Recursion Theory.R. Downey - 1984 - Mathematical Logic Quarterly 30 (19-24):295-302.
1 — 50 / 157