88 found
Order:
  1. Rod Downey (1984). Bases of Supermaximal Subspaces and Steinitz Systems. I. Journal of Symbolic Logic 49 (4):1146-1159.
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  2.  44
    Rod Downey, Andre Nies, Rebecca Weber & Liang Yu (2006). Lowness and Π₂⁰ Nullsets. 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 (3 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  3.  3
    Rod Downey, Denis R. Hirschfeldt, Joseph S. Miller & André Nies (2005). Relativizing Chaitin's Halting Probability. Journal of Mathematical Logic 5 (02):167-192.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   7 citations  
  4.  1
    Rodney G. Downey, Carl G. Jockusch & Paul E. Schupp (2013). Asymptotic Density and Computably Enumerable Sets. Journal of Mathematical Logic 13 (2):1350005.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  5.  17
    Rod Downey & Christine Haught (1994). Embedding Lattices Into the Wtt-Degrees Below 0'. Journal of Symbolic Logic 59 (4):1360-1382.
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  6. Rodney G. Downey, Geoffrey L. Laforte & Richard A. Shore (2003). Decomposition and Infima in the Computably Enumerable Degrees. 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 (7 more)  
     
    Export citation  
     
    My bibliography  
  7.  11
    Rod Downey, Denis R. Hirschfeldt, André Nies & Sebastiaan A. Terwijn (2006). Calibrating Randomness. Bulletin of Symbolic Logic 12 (3):411-491.
    Direct download (9 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  8.  14
    Rod Downey (1997). On the Universal Splitting Property. Mathematical Logic Quarterly 43 (3):311-320.
    We prove that if an incomplete computably enumerable set has the the universal splitting property then it is low2. This solves a question from Ambos-Spies and Fejer [1] and Downey and Stob [7]. Some technical improvements are discussed.
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  9.  8
    Rodney G. Downey, Sergei S. Goncharov, Asher M. Kach, Julia F. Knight, Oleg V. Kudinov, Alexander G. Melnikov & Daniel Turetsky (2010). Decidability and Computability of Certain Torsion-Free Abelian Groups. 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 (4 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  10.  15
    Rod Downey & Richard A. Shore (1995). Degree Theoretic Definitions of the Low2 Recursively Enumerable Sets. Journal of Symbolic Logic 60 (3):727 - 756.
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  11.  3
    Rodney G. Downey & Evan J. Griffiths (2004). Schnorr Randomness. 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 (4 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  12.  24
    Rodney G. Downey, Bart Kastermans & Steffen Lempp (2009). On Computable Self-Embeddings of Computable Linear Orderings. 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 (5 more)  
     
    Export citation  
     
    My bibliography  
  13.  2
    Rodney G. Downey, Steffen Lempp & Richard A. Shore (1993). Highness and Bounding Minimal Pairs. Mathematical Logic Quarterly 39 (1):475-491.
  14. Rod Downey (1998). Computability Theory and Linear Orders. In I͡Uriĭ Leonidovich Ershov (ed.), Handbook of Recursive Mathematics. Elsevier 138--823.
     
    Export citation  
     
    My bibliography   4 citations  
  15.  12
    Rod Downey, Evan Griffiths & Geoffrey Laforte (2004). On Schnorr and Computable Randomness, Martingales, and Machines. 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 (6 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  16. Rod Downey & Mike Stob (1991). Jumps of Hemimaximal Sets. Mathematical Logic Quarterly 37 (8):113-120.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   5 citations  
  17. Rod Downey (1990). Lattice Nonembeddings and Initial Segments of the Recursively Enumerable Degrees. Annals of Pure and Applied Logic 49 (2):97-119.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   5 citations  
  18.  2
    Karl A. Abrahamson, Rodney G. Downey & Michael R. Fellows (1995). Fixed-Parameter Tractability and Completeness IV: On Completeness for W[P] and PSPACE Analogues. 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 (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  19. Douglas Cenzer, Rodney Downey, Carl Jockusch & Richard A. Shore (1993). Countable Thin Π01 Classes. 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 (3 more)  
     
    Export citation  
     
    My bibliography   4 citations  
  20. Rod Downey & Michael Stob (1993). Splitting Theorems in Recursion Theory. 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 (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   4 citations  
  21.  5
    Rod Downey (1991). On $\Pi^0_1$ Classes and Their Ranked Points. Notre Dame Journal of Formal Logic 32 (4):499-512.
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  22.  7
    Rod Downey (2012). Randomness, Computation and Mathematics. In S. Barry Cooper (ed.), How the World Computes. 162--181.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  23.  4
    Peter A. Cholak, Rodney Downey & Leo A. Harrington (2008). The Complexity of Orbits of Computably Enumerable Sets. 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 (6 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  24.  6
    Rod Downey & Liang Yu (2006). Arithmetical Sacks Forcing. 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  
     
    My bibliography  
  25.  14
    Douglas Cenzer, Rodney G. Downey, Jeffrey B. Remmel & Zia Uddin (2009). Space Complexity of Abelian Groups. 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 (4 more)  
     
    Export citation  
     
    My bibliography  
  26.  17
    Rodney G. Downey & Steffen Lempp (1997). Contiguity and Distributivity in the Enumerable Turing Degrees. Journal of Symbolic Logic 62 (4):1215-1240.
    We prove that a (recursively) enumerable degree is contiguous iff it is locally distributive. This settles a twenty-year old question going back to Ladner and Sasso. We also prove that strong contiguity and contiguity coincide, settling a question of the first author, and prove that no m-topped degree is contiguous, settling a question of the first author and Carl Jockusch [11]. Finally, we prove some results concerning local distributivity and relativized weak truth table reducibility.
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  27.  6
    Liming Cai, Jianer Chen, Rodney G. Downey & Michael R. Fellows (1997). On the Parameterized Complexity of Short Computation and Factorization. Archive for Mathematical Logic 36 (4-5):321-337.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  28. Rod Downey (1993). Every Recursive Boolean Algebra is Isomorphic to One with Incomplete Atoms. 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 (3 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  29.  6
    Rod Downey, Denis R. Hirschfeldt, Steffen Lempp & Reed Solomon (2001). A Δ02 Set with No Infinite Low Subset in Either It or its Complement. 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 (6 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  30.  12
    Barbara F. Csima, Rod Downey, Noam Greenberg, Denis R. Hirschfeldt & Joseph S. Miller (2006). Every 1-Generic Computes a Properly 1-Generic. Journal of Symbolic Logic 71 (4):1385 - 1393.
    A real is called properly n-generic if it is n-generic but not n+1-generic. We show that every 1-generic real computes a properly 1-generic real. On the other hand, if m > n ≥ 2 then an m-generic real cannot compute a properly n-generic real.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  31.  9
    Peter Cholak & Rod Downey (1993). On the Cantor-Bendixon Rank of Recursively Enumerable Sets. 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 (6 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  32.  5
    Rod Downey (1989). On Hyper-Torre Isols. Journal of Symbolic Logic 54 (4):1160-1166.
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  33.  2
    Rod Downey (1983). On a Question of A. Retzlaff. Mathematical Logic Quarterly 29 (6):379-384.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  34.  9
    Liang Yu & Rod Downey (2004). There Are No Maximal Low D.C.E.~Degrees. Notre Dame Journal of Formal Logic 45 (3):147-159.
    We prove that there is no maximal low d.c.e degree.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  35.  9
    Rich Blaylock, Rod Downey & Steffen Lempp (1997). Infima in the Recursively Enumerable Weak Truth Table Degrees. Notre Dame Journal of Formal Logic 38 (3):406-418.
    We show that for every nontrivial r.e. wtt-degree a, there are r.e. wtt-degrees b and c incomparable to a such that the infimum of a and b exists but the infimum of a and c fails to exist. This shows in particular that there are no strongly noncappable r.e. wtt-degrees, in contrast to the situation in the r.e. Turing degrees.
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  36.  1
    Peter Cholak, Rod Downey & Eberhard Herrmann (2001). Some Orbits for E. 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 (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  37.  7
    Rod Downey, Steffen Lempp & Guohua Wu (2010). On the Complexity of the Successivity Relation in Computable Linear Orderings. Journal of Mathematical Logic 10 (01n02):83-99.
  38.  4
    Liming Cai, Jianer Chen, Rodney G. Downey & Michael R. Fellows (1997). Advice Classes of Parameterized Tractability. Annals of Pure and Applied Logic 84 (1):119-138.
    Many natural computational problems have input consisting of two or more parts, one of which may be considered a parameter. For example, there are many problems for which the input consists of a graph and a positive integer. A number of results are presented concerning parameterized problems that can be solved in complexity classes below P, given a single word of advice for each parameter value. Different ways in which the word of advice can be employed are considered, and it (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  39.  6
    Rod Downey, Guohua Wu & Xizhong Zheng (2004). Degrees of D. C. E. Reals. Mathematical Logic Quarterly 50 (4‐5):345-350.
    A real α is called a c. e. real if it is the halting probability of a prefix free Turing machine. Equivalently, α is c. e. if it is left computable in the sense that L = {q ∈ ℚ : q ≤ α} is a computably enumerable set. The natural field formed by the c. e. reals turns out to be the field formed by the collection of the d. c. e. reals, which are of the form α—β, where (...)
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography  
  40.  2
    Rod Downey & Michael Stob (1993). Friedberg Splittings of Recursively Enumerable Sets. 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 (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  41.  6
    Rodney G. Downey & Asher M. Kach (2010). Euclidean Functions of Computable Euclidean Domains. Notre Dame Journal of Formal Logic 52 (2):163-172.
    We study the complexity of (finitely-valued and transfinitely-valued) Euclidean functions for computable Euclidean domains. We examine both the complexity of the minimal Euclidean function and any Euclidean function. Additionally, we draw some conclusions about the proof-theoretical strength of minimal Euclidean functions in terms of reverse mathematics.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  42.  6
    Rodney G. Downey & Steffen Lempp (2002). Contiguity and Distributivity in the Enumerable Turing Degrees: Corrigendum. Journal of Symbolic Logic 67 (4):1579-1580.
  43.  14
    Peter Cholak, Rod Downey & Stephen Walk (2002). Maximal Contiguous Degrees. Journal of Symbolic Logic 67 (1):409-437.
    A computably enumerable (c.e.) degree is a maximal contiguous degree if it is contiguous and no c.e. degree strictly above it is contiguous. We show that there are infinitely many maximal contiguous degrees. Since the contiguous degrees are definable, the class of maximal contiguous degrees provides the first example of a definable infinite anti-chain in the c.e. degrees. In addition, we show that the class of maximal contiguous degrees forms an automorphism base for the c.e. degrees and therefore for the (...)
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography  
  44. Rod Downey & Leo Harrington (1996). There is No Fat Orbit. 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 (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  45.  2
    Rod Downey & Carl G. Jockusch Jr (1999). Effective Presentability of Boolean Algebras of Cantor-Bendixson Rank. Journal of Symbolic Logic 64 (1):45-52.
    We show that there is a computable Boolean algebra B and a computably enumerable ideal I of B such that the quotient algebra B/I is of Cantor-Bendixson rank 1 and is not isomorphic to any computable Boolean algebra. This extends a result of L. Feiner and is deduced from Feiner's result even though Feiner's construction yields a Boolean algebra of infinite Cantor-Bendixson rank.
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  46.  2
    George Barmpalias, Rod Downey & Keng Meng Ng (2011). Jump Inversions Inside Effectively Closed Sets and Applications to Randomness. 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 (4 more)  
     
    Export citation  
     
    My bibliography  
  47.  4
    Rod G. Downey & Michael R. Fellows (2001). Index Sets and Parametric Reductions. Archive for Mathematical Logic 40 (5):329-348.
    We investigate the index sets associated with the degree structures of computable sets under the parameterized reducibilities introduced by the authors. We solve a question of Peter Cholakand the first author by proving the fundamental index sets associated with a computable set A, {e : W e ≤ q u A} for q∈ {m, T} are Σ4 0 complete. We also show hat FPT(≤ q n ), that is {e : W e computable and ≡ q n ?}, is Σ4 (...)
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  48.  10
    Barbara F. Csima, Rod Downey & Keng Meng Ng (2011). Limits on Jump Inversion for Strong Reducibilities. 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 (5 more)  
     
    Export citation  
     
    My bibliography  
  49.  2
    Rod Downey (forthcoming). Twelfth Asian Logic Conference. Bulletin of Symbolic Logic.
    Direct download  
     
    Export citation  
     
    My bibliography  
  50.  10
    Rod Downey, Noam Greenberg & Rebecca Weber (2007). Totally Ω-Computably Enumerable Degrees and Bounding Critical Triples. Journal of Mathematical Logic 7 (2):145-171.
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography  
1 — 50 / 88