103 found
Order:
  1.  60
    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   25 citations  
  2.  7
    [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 (3 more)  
     
    Export citation  
     
    Bookmark   23 citations  
  3.  11
    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 (5 more)  
     
    Export citation  
     
    Bookmark   14 citations  
  4.  20
    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 (8 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  5.  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 (5 more)  
     
    Export citation  
     
    Bookmark   13 citations  
  6.  32
    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   7 citations  
  7.  68
    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   7 citations  
  8.  12
    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.
  9.  11
    Asymptotic Density and the Ershov Hierarchy.Rod Downey, Carl Jockusch, Timothy H. McNicholl & Paul Schupp - 2015 - Mathematical Logic Quarterly 61 (3):189-195.
    No categories
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  10.  18
    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   9 citations  
  11. Computability Theory and Linear Orders.Rod Downey - 1998 - In I͡Uriĭ Leonidovich Ershov (ed.), Handbook of Recursive Mathematics. Elsevier. pp. 138--823.
     
    Export citation  
     
    Bookmark   13 citations  
  12.  10
    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   15 citations  
  13. Bases of Supermaximal Subspaces and Steinitz Systems. I.Rod Downey - 1984 - Journal of Symbolic Logic 49 (4):1146-1159.
  14.  2
    Lattice Nonembeddings and Initial Segments of the Recursively Enumerable Degrees.Rod Downey - 1990 - Annals of Pure and Applied Logic 49 (2):97-119.
  15.  18
    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   11 citations  
  16.  74
    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   4 citations  
  17.  37
    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   3 citations  
  18.  29
    Highness and Bounding Minimal Pairs.Rodney G. Downey, Steffen Lempp & Richard A. Shore - 1993 - Mathematical Logic Quarterly 39 (1):475-491.
  19.  11
    Characterizing Lowness for Demuth Randomness.Laurent Bienvenu, Rod Downey, Noam Greenberg, André Nies & Dan Turetsky - 2014 - Journal of Symbolic Logic 79 (2):526-560.
    We show the existence of noncomputable oracles which are low for Demuth randomness, answering a question in [15]. We fully characterize lowness for Demuth randomness using an appropriate notion of traceability. Central to this characterization is a partial relativization of Demuth randomness, which may be more natural than the fully relativized version. We also show that an oracle is low for weak Demuth randomness if and only if it is computable.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  20.  20
    Jumps of Hemimaximal Sets.Rod Downey & Mike Stob - 1991 - Mathematical Logic Quarterly 37 (8):113-120.
  21.  30
    Jumps of Hemimaximal Sets.Rod Downey & Mike Stob - 1991 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 37 (8):113-120.
  22. Decomposition and Infima in the Computably Enumerable Degrees.Rodney G. Downey, Geoffrey L. Laforte & Richard A. Shore - 2003 - Journal of Symbolic Logic 68 (2):551-579.
    Given two incomparable c.e. Turing degrees a and b, we show that there exists a c.e. degree c such that c = (a ⋃ c) ⋂ (b ⋃ c), a ⋃ c | b ⋃ c, and c < a ⋃ b.
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  23.  17
    On $\Pi^0_1$ Classes and Their Ranked Points.Rod Downey - 1991 - Notre Dame Journal of Formal Logic 32 (4):499-512.
  24.  1
    Exact Pairs for the Ideal of the K-Trivial Sequences in the Turing Degrees.George Barmpalias & Rod G. Downey - 2014 - Journal of Symbolic Logic 79 (3):676-692.
    TheK-trivial sets form an ideal in the Turing degrees, which is generated by its computably enumerable members and has an exact pair below the degree of the halting problem. The question of whether it has an exact pair in the c.e. degrees was first raised in [22, Question 4.2] and later in [25, Problem 5.5.8].We give a negative answer to this question. In fact, we show the following stronger statement in the c.e. degrees. There exists aK-trivial degreedsuch that for all (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  25.  19
    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 (6 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  26.  44
    Degree Theoretic Definitions of the Low2 Recursively Enumerable Sets.Rod Downey & Richard A. Shore - 1995 - Journal of Symbolic Logic 60 (3):727 - 756.
  27.  36
    Decidability and Computability of Certain Torsion-Free Abelian Groups.Rodney G. Downey, Sergei S. Goncharov, Asher M. Kach, Julia F. Knight, Oleg V. Kudinov, Alexander G. Melnikov & Daniel Turetsky - 2010 - Notre Dame Journal of Formal Logic 51 (1):85-96.
    We study completely decomposable torsion-free abelian groups of the form $\mathcal{G}_S := \oplus_{n \in S} \mathbb{Q}_{p_n}$ for sets $S \subseteq \omega$. We show that $\mathcal{G}_S$has a decidable copy if and only if S is $\Sigma^0_2$and has a computable copy if and only if S is $\Sigma^0_3$.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  28.  10
    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.
  29.  29
    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   4 citations  
  30.  15
    Categorical Linearly Ordered Structures.Rod Downey, Alexander Melnikov & Keng Meng Ng - 2019 - Annals of Pure and Applied Logic 170 (10):1243-1255.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  31.  8
    On a Question of A. Retzlaff.Rod Downey - 1983 - Mathematical Logic Quarterly 29 (6):379-384.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  32.  28
    On the Complexity of the Successivity Relation in Computable Linear Orderings.Rod Downey, Steffen Lempp & Guohua Wu - 2010 - Journal of Mathematical Logic 10 (1):83-99.
    In this paper, we solve a long-standing open question, about the spectrum of the successivity relation on a computable linear ordering. We show that if a computable linear ordering [Formula: see text] has infinitely many successivities, then the spectrum of the successivity relation is closed upwards in the computably enumerable Turing degrees. To do this, we use a new method of constructing [Formula: see text]-isomorphisms, which has already found other applications such as Downey, Kastermans and Lempp [9] and is of (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  33.  17
    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  
  34.  38
    The Complexity of Orbits of Computably Enumerable Sets.Peter A. Cholak, Rodney Downey & Leo A. Harrington - 2008 - Bulletin of Symbolic Logic 14 (1):69 - 87.
    The goal of this paper is to announce there is a single orbit of the c.e. sets with inclusion, ε, such that the question of membership in this orbit is ${\Sigma _1^1 }$ -complete. This result and proof have a number of nice corollaries: the Scott rank of ε is $\omega _1^{{\rm{CK}}}$ + 1; not all orbits are elementarily definable; there is no arithmetic description of all orbits of ε; for all finite α ≥ 9, there is a properly $\Delta (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  35.  9
    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  
  36.  19
    Effective Packing Dimension and Traceability.Rod Downey & Keng Meng Ng - 2010 - Notre Dame Journal of Formal Logic 51 (2):279-290.
    We study the Turing degrees which contain a real of effective packing dimension one. Downey and Greenberg showed that a c.e. degree has effective packing dimension one if and only if it is not c.e. traceable. In this paper, we show that this characterization fails in general. We construct a real $A\leq_T\emptyset''$ which is hyperimmune-free and not c.e. traceable such that every real $\alpha\leq_T A$ has effective packing dimension 0. We construct a real $B\leq_T\emptyset'$ which is not c.e. traceable such (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  37.  9
    The Members of Thin and Minimal Π 1 0 Classes, Their Ranks and Turing Degrees.Rodney G. Downey, Guohua Wu & Yue Yang - 2015 - Annals of Pure and Applied Logic 166 (7-8):755-766.
  38.  14
    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  
  39.  18
    Soare Robert I.. Automorphisms of the Lattice of Recursively Enumerable Sets. Part I: Maximal Sets. Annals of Mathematics, Ser. 2 Vol. 100 , Pp. 80–120. - Lerman Manuel and Soare Robert I.. D-Simple Sets, Small Sets, and Degree Classes. Pacific Journal of Mathematics, Vol. 87 , Pp. 135–155. - Cholak Peter. Automorphisms of the Lattice of Recursively Enumerable Sets. Memoirs of the American Mathematical Society, No. 541. American Mathematical Society, Providence1995, Viii + 151 Pp. - Harrington Leo and Soare Robert I.. The Δ30-Automorphism Method and Noninvariant Classes of Degrees. Journal of the American Mathematical Society, Vol. 9 , Pp. 617–666. [REVIEW]Rod Downey - 1997 - Journal of Symbolic Logic 62 (3):1048-1055.
  40.  2
    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   5 citations  
  41.  56
    Space Complexity of Abelian Groups.Douglas Cenzer, Rodney G. Downey, Jeffrey B. Remmel & Zia Uddin - 2008 - Archive for Mathematical Logic 48 (1):115-140.
    We develop a theory of LOGSPACE structures and apply it to construct a number of examples of Abelian Groups which have LOGSPACE presentations. We show that all computable torsion Abelian groups have LOGSPACE presentations and we show that the groups ${\mathbb {Z}, Z(p^{\infty})}$ , and the additive group of the rationals have LOGSPACE presentations over a standard universe such as the tally representation and the binary representation of the natural numbers. We also study the effective categoricity of such groups. For (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  42.  48
    On Computable Self-Embeddings of Computable Linear Orderings.Rodney G. Downey, Bart Kastermans & Steffen Lempp - 2009 - Journal of Symbolic Logic 74 (4):1352 - 1366.
    We solve a longstanding question of Rosenstein, and make progress toward solving a longstanding open problem in the area of computable linear orderings by showing that every computable ƞ-like linear ordering without an infinite strongly ƞ-like interval has a computable copy without nontrivial computable self-embedding. The precise characterization of those computable linear orderings which have computable copies without nontrivial computable self-embedding remains open.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  43.  11
    Fixed-Parameter Tractability and Completeness IV: On Completeness for W[P] and PSPACE Analogues.Karl A. Abrahamson, Rodney G. Downey & Michael R. Fellows - 1995 - Annals of Pure and Applied Logic 73 (3):235-276.
    We describe new results in parametrized complexity theory. In particular, we prove a number of concrete hardness results for W[P], the top level of the hardness hierarchy introduced by Downey and Fellows in a series of earlier papers. We also study the parametrized complexity of analogues of PSPACE via certain natural problems concerning k-move games. Finally, we examine several aspects of the structural complexity of W [P] and related classes. For instance, we show that W[P] can be characterized in terms (...)
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  44.  25
    On the Cantor-Bendixon Rank of Recursively Enumerable Sets.Peter Cholak & Rod Downey - 1993 - Journal of Symbolic Logic 58 (2):629-640.
    The main result of this paper is to show that for every recursive ordinal α ≠ 0 and for every nonrecursive r.e. degree d there is a r.e. set of rank α and degree d.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  45.  18
    Jump Inversions Inside Effectively Closed Sets and Applications to Randomness.George Barmpalias, Rod Downey & Keng Meng Ng - 2011 - Journal of Symbolic Logic 76 (2):491 - 518.
    We study inversions of the jump operator on ${\mathrm{\Pi }}_{1}^{0}$ classes, combined with certain basis theorems. These jump inversions have implications for the study of the jump operator on the random degrees—for various notions of randomness. For example, we characterize the jumps of the weakly 2-random sets which are not 2-random, and the jumps of the weakly 1-random relative to 0′ sets which are not 2-random. Both of the classes coincide with the degrees above 0′ which are not 0′-dominated. A (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  46.  29
    Arithmetical Sacks Forcing.Rod Downey & Liang Yu - 2006 - Archive for Mathematical Logic 45 (6):715-720.
    We answer a question of Jockusch by constructing a hyperimmune-free minimal degree below a 1-generic one. To do this we introduce a new forcing notion called arithmetical Sacks forcing. Some other applications are presented.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  47.  23
    On Choice Sets and Strongly Non-Trivial Self-Embeddings of Recursive Linear Orders.Rodney G. Downey & Michael F. Moses - 1989 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 35 (3):237-246.
  48.  26
    Corrigendum: "On the Complexity of the Successivity Relation in Computable Linear Orderings".Rodney G. Downey, Steffen Lempp & Guohua Wu - 2017 - Journal of Mathematical Logic 17 (2):1792002.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  49.  31
    On the Parameterized Complexity of Short Computation and Factorization.Liming Cai, Jianer Chen, Rodney G. Downey & Michael R. Fellows - 1997 - Archive for Mathematical Logic 36 (4-5):321-337.
    . A completeness theory for parameterized computational complexity has been studied in a series of recent papers, and has been shown to have many applications in diverse problem domains including familiar graph-theoretic problems, VLSI layout, games, computational biology, cryptography, and computational learning [ADF,BDHW,BFH, DEF,DF1-7,FHW,FK]. We here study the parameterized complexity of two kinds of problems: problems concerning parameterized computations of Turing machines, such as determining whether a nondeterministic machine can reach an accept state in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  50.  5
    Correction to “Undecidability of L(F∞) and Other Lattices of R.E. Substructures”.Rod Downey - 1990 - Annals of Pure and Applied Logic 48 (3):299-301.
1 — 50 / 103