80 found
Sort by:
  1. Rod Downey (forthcoming). Twelfth Asian Logic Conference. Bulletin of Symbolic Logic.
    Direct download  
     
    My bibliography  
     
    Export citation  
  2. George Barmpalias, Vasco Brattka, Adam Day, Rod Downey, John Hitchcock, Michal Koucký, Andy Lewis, Jack Lutz, André Nies & Alexander Shen (2013). Isaac Newton Institute, Cambridge, UK July 2–6, 2012. Bulletin of Symbolic Logic 19 (1).
    Direct download  
     
    My bibliography  
     
    Export citation  
  3. 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)  
     
    My bibliography  
     
    Export citation  
  4. Rod Downey (2012). Randomness, Computation and Mathematics. In S. Barry Cooper (ed.), How the World Computes. 162--181.
    No categories
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  5. 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)  
     
    My bibliography  
     
    Export citation  
  6. 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)  
     
    My bibliography  
     
    Export citation  
  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.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  8. Rod Downey & Keng Meng Ng (2010). Effective Packing Dimension and Traceability. 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 (4 more)  
     
    My bibliography  
     
    Export citation  
  9. 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)  
     
    My bibliography  
     
    Export citation  
  10. 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)  
     
    My bibliography  
     
    Export citation  
  11. 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 (...)
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  12. 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)  
     
    My bibliography  
     
    Export citation  
  13. Verónica Becher, C. T. Chong, Rod Downey, Noam Greenberg, Antonin Kucera, Bjørn Kjos-Hanssen, Steffen Lempp, Antonio Montalbán, Jan Reimann & Stephen Simpson (2008). Conference on Computability, Complexity and Randomness. Bulletin of Symbolic Logic 14 (4).
    Direct download  
     
    My bibliography  
     
    Export citation  
  14. 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)  
     
    My bibliography  
     
    Export citation  
  15. Rod Downey, Noam Greenberg & Joseph S. Miller (2008). The Upward Closure of a Perfect Thin Class. Annals of Pure and Applied Logic 156 (1):51-58.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  16. Rod Downey, Jörg Flum, Martin Grohe & Mark Weyer (2007). Bounded Fixed-Parameter Tractability and Reducibility. Annals of Pure and Applied Logic 148 (1):1-19.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  17. Rod Downey, Noam Greenberg & Rebecca Weber (2007). Totally Ω-Computably Enumerable Degrees and Bounding Critical Triples. Journal of Mathematical Logic 7 (02):145-171.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  18. Rodney Downey, Ieke Moerdijk, Boban Velickovic, Samson Abramsky, Marat Arslanov, Harvey Friedman, Martin Goldstern, Ehud Hrushovski, Jochen Koenigsmann & Andy Lewis (2007). Nijmegen, The Netherlands July 27–August 2, 2006. Bulletin of Symbolic Logic 13 (2).
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  19. 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)  
     
    My bibliography  
     
    Export citation  
  20. Rod& Nies Downey, André Weber & Rebecca Yu (2006). Liang," Lowness and Π20 Nullsets. Journal of Symbolic Logic 71:3.
    No categories
     
    My bibliography  
     
    Export citation  
  21. Rod Downey & Rob Goldblatt (2006). Foreword. Annals of Pure and Applied Logic 138 (1-3):1.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  22. Rod Downey, Denis R. Hirschfeldt, André Nies & Sebastiaan A. Terwijn (2006). Calibrating Randomness. Bulletin of Symbolic Logic 12 (3):411-491.
    Direct download (10 more)  
     
    My bibliography  
     
    Export citation  
  23. Rod Downey, Andre Nies, Rebecca Weber & Liang Yu (2006). Lowness and Π₂⁰ Nullsets. Journal of Symbolic Logic 71 (3):1044-1052.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  24. 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.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  25. Rodney G. Downey, Carl Jockusch & Joseph S. Miller (2006). On Self-Embeddings of Computable Linear Orderings. Annals of Pure and Applied Logic 138 (1):52-76.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  26. 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)  
     
    My bibliography  
     
    Export citation  
  27. Rod Downey, Evan Griffiths & Geoffrey Laforte (2004). On Schnorr and Computable Randomness, Martingales, and Machines. Mathematical Logic Quarterly 50 (6):613-627.
    No categories
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  28. Rod Downey, Angsheng Li & Guohua Wu (2004). Complementing Cappable Degrees in the Difference Hierarchy. Annals of Pure and Applied Logic 125 (1-3):101-118.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  29. Rod Downey, Guohua Wu & Xizhong Zheng (2004). Degrees of D. C. E. Reals. Mathematical Logic Quarterly 50 (4‐5):345-350.
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  30. 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)  
     
    My bibliography  
     
    Export citation  
  31. Rodney& Griffiths Downey (2004). Evan," Schnorr Randomness. Journal of Symbolic Logic 69:2.
    No categories
     
    My bibliography  
     
    Export citation  
  32. Liang Yu, Decheng Ding & Rodney Downey (2004). The Kolmogorov Complexity of Random Reals. Annals of Pure and Applied Logic 129 (1-3):163-180.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  33. Liang Yu & Rod Downey (2004). There Are No Maximal Low D.C.E.~Degrees. Notre Dame Journal of Formal Logic 45 (3):147-159.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  34. 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)  
     
    My bibliography  
     
    Export citation  
  35. 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)  
     
    My bibliography  
     
    Export citation  
  36. Rod Downey (2002). Notice From the Editors. Journal of Symbolic Logic 67 (3).
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  37. Rod Downey (2002). Roman Murawski, Recursive Functions and Metamathematics. Studia Logica 70 (2):297-299.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  38. Rodney G. Downey & Steffen Lempp (2002). Contiguity and Distributivity in the Enumerable Turing Degrees: Corrigendum. Journal of Symbolic Logic 67 (4):1579-1580.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  39. Rodney G. Downey & Steffen Lempp (2002). Corrigendum: ``Contiguity and Distributivity in the Enumerable Turing Degrees''. Journal of Symbolic Logic 67 (4):1579-1580.
    Translate to English
    | Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  40. Itay Neeman, Alexander Leitsch, Toshiyasu Arai, Steve Awodey, James Cummings, Rod Downey & Harvey Friedman (2002). 2001 European Summer Meeting of the Association for Symbolic Logic Logic Colloquium'01. Bulletin of Symbolic Logic 8 (1).
    Direct download  
     
    My bibliography  
     
    Export citation  
  41. Peter Cholak, Rod Downey & Eberhard Herrmann (2001). Some Orbits For. Annals of Pure and Applied Logic 107 (1-3):193-226.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  42. 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)  
     
    My bibliography  
     
    Export citation  
  43. 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)  
     
    My bibliography  
     
    Export citation  
  44. 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)  
     
    My bibliography  
     
    Export citation  
  45. Rod Downey, Geoffrey Laforte & Steffen Lempp (1999). A $Delta^02$ Set with Barely $Sigma^02$ Degree. Journal of Symbolic Logic 64 (4):1700-1718.
    We construct a $\Delta^0_2$ degree which fails to be computably enumerable in any computably enumerable set strictly below $\emptyset'$.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  46. Rod Downey, Geoffrey Laforte & Steffen Lempp (1999). A Δ02 Set with Barely Σ02 Degree. Journal of Symbolic Logic 64 (4):1700 - 1718.
    We construct a Δ 0 2 degree which fails to be computably enumerable in any computably enumerable set strictly below $\emptyset'$.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  47. Klaus Ambos-Spies, Marat Arslanov, Douglas Cenzer, Peter Cholak, Chi Tat Chong, Decheng Ding, Rod Downey, Peter A. Fejer, Sergei S. Goncharov & Edward R. Griffor (1998). Participants and Titles of Lectures. Annals of Pure and Applied Logic 94:3-6.
    No categories
     
    My bibliography  
     
    Export citation  
  48. Rod Downey (1998). Computability Theory and Linear Orders. In I͡Uriĭ Leonidovich Ershov (ed.), Handbook of Recursive Mathematics. Elsevier. 138--823.
    No categories
     
    My bibliography  
     
    Export citation  
  49. Rod Downey, Zoltán Füredi, Carl G. Jockusch & Lee A. Rubel (1998). Difference Sets and Computability Theory. Annals of Pure and Applied Logic 93 (1-3):63-72.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  50. 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)  
     
    My bibliography  
     
    Export citation  
1 — 50 / 80