You are accessing PhilPapers from Open University (UK), an institution that is not subscribed to PhilPapers. Starting on July 1, 2014, we ask institutions that grant philosophy degrees and are based in high-GDP countries to contribute to PhilPapers' maintenance and development through a subscription. See this page for details. Please show your support by contacting your librarian.
17 found
Sort by:
  1. Rodney G. Downey, Carl G. Jockusch & Paul E. Schupp (2013). Asymptotic Density and Computably Enumerable Sets. Journal of Mathematical Logic 13 (2):1350005.
    No categories
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  2. 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  
  3. 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  
  4. 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  
  5. 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  
  6. 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  
  7. 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  
  8. 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  
  9. 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  
  10. 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  
  11. 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.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  12. 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.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  13. 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)  
     
    My bibliography  
     
    Export citation  
  14. 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.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  15. Rodney G. Downey & Steffen Lempp (1994). There is No Plus-Capping Degree. Archive for Mathematical Logic 33 (2):109-119.
    Answering a question of Per Lindström, we show that there is no “plus-capping” degree, i.e. that for any incomplete r.e. degreew, there is an incomplete r.e. degreea>w such that there is no r.e. degreev>w witha∩v=w.
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  16. Rodney G. Downey, Steffen Lempp & Richard A. Shore (1993). Highness and Bounding Minimal Pairs. Mathematical Logic Quarterly 39 (1):475-491.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  17. Rodney G. Downey & Michael F. Moses (1989). On Choice Sets and Strongly Non‐Trivial Self‐Embeddings of Recursive Linear Orders. Mathematical Logic Quarterly 35 (3):237-246.
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation