Results for 'Rodney Downey'

784 found
Order:
  1.  12
    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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  2.  10
    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   3 citations  
  3.  5
    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 (...)
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  4.  6
    Degrees Containing Members of Thin Π10 Classes Are Dense and Co-Dense.Rodney G. Downey, Guohua Wu & Yue Yang - 2018 - Journal of Mathematical Logic 18 (1):1850001.
    In [Countable thin Π10 classes, Ann. Pure Appl. Logic 59 79–139], Cenzer, Downey, Jockusch and Shore proved the density of degrees containing members of countable thin Π10 classes. In the same paper, Cenzer et al. also proved the existence of degrees containing no members of thin Π10 classes. We will prove in this paper that the c.e. degrees containing no members of thin Π10 classes are dense in the c.e. degrees. We will also prove that the c.e. degrees containing (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  5.  9
    Asymptotic Density and Computably Enumerable Sets.Rodney G. Downey, Carl G. Jockusch & Paul E. Schupp - 2013 - Journal of Mathematical Logic 13 (2):1350005.
  6.  15
    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   6 citations  
  7.  8
    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.
  8.  20
    Highness and Bounding Minimal Pairs.Rodney G. Downey, Steffen Lempp & Richard A. Shore - 1993 - Mathematical Logic Quarterly 39 (1):475-491.
  9. 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  
  10.  27
    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  
  11.  7
    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.
  12.  37
    Contiguity and Distributivity in the Enumerable Turing Degrees.Rodney G. Downey & Steffen Lempp - 1997 - 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 (9 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  13.  24
    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  
  14.  22
    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   1 citation  
  15.  17
    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.
  16.  24
    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.
  17.  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  
  18.  7
    On Self-Embeddings of Computable Linear Orderings.Rodney G. Downey, Carl Jockusch & Joseph S. Miller - 2006 - Annals of Pure and Applied Logic 138 (1):52-76.
    The Dushnik–Miller Theorem states that every infinite countable linear ordering has a nontrivial self-embedding. We examine computability-theoretical aspects of this classical theorem.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  19.  6
    On Choice Sets and Strongly Non‐Trivial Self‐Embeddings of Recursive Linear Orders.Rodney G. Downey & Michael F. Moses - 1989 - Mathematical Logic Quarterly 35 (3):237-246.
  20.  24
    Space Complexity of Abelian Groups.Douglas Cenzer, Rodney G. Downey, Jeffrey B. Remmel & Zia Uddin - 2009 - 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  
  21.  21
    Contiguity and Distributivity in the Enumerable Turing Degrees: Corrigendum.Rodney G. Downey & Steffen Lempp - 2002 - Journal of Symbolic Logic 67 (4):1579-1580.
  22.  20
    There is No Plus-Capping Degree.Rodney G. Downey & Steffen Lempp - 1994 - 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.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  23.  18
    Euclidean Functions of Computable Euclidean Domains.Rodney G. Downey & Asher M. Kach - 2011 - 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 (6 more)  
     
    Export citation  
     
    Bookmark  
  24.  4
    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  
  25.  11
    Advice Classes of Parameterized Tractability.Liming Cai, Jianer Chen, Rodney G. Downey & Michael R. Fellows - 1997 - 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 (4 more)  
     
    Export citation  
     
    Bookmark  
  26.  16
    Corrigendum: ``Contiguity and Distributivity in the Enumerable Turing Degrees''.Rodney G. Downey & Steffen Lempp - 2002 - Journal of Symbolic Logic 67 (4):1579-1580.
  27.  6
    Soare Robert I.. Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, Heidelberg, New York, Etc., 1987, Xviii + 437 Pp. [REVIEW]Eberhard Herrmann & Rodney Downey - 1990 - Journal of Symbolic Logic 55 (1):356-357.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  28. Review: Robert I. Soare, Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets. [REVIEW]Eberhard Herrmann & Rodney Downey - 1990 - Journal of Symbolic Logic 55 (1):356-357.
  29.  2
    Nijmegen, The Netherlands July 27–August 2, 2006.Rodney Downey, Ieke Moerdijk, Boban Velickovic, Samson Abramsky, Marat Arslanov, Harvey Friedman, Martin Goldstern, Ehud Hrushovski, Jochen Koenigsmann & Andy Lewis - 2007 - Bulletin of Symbolic Logic 13 (2).
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  30. Evan," Schnorr Randomness.Rodney& Griffiths Downey - 2004 - Journal of Symbolic Logic 69:2.
    No categories
     
    Export citation  
     
    Bookmark  
  31. Rodney G. Downey and Denis R. Hirschfeldt. Algorithmic Randomness and Complexity. Theory and Applications of Computability. Springer, 2010, Xxviii + 855 Pp. [REVIEW]Laurent Bienvenu - 2012 - Bulletin of Symbolic Logic 18 (1):126-128.
  32.  11
    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 (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  33.  16
    On the Universal Splitting Property.Rod Downey - 1997 - 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.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  34.  8
    Tabular Degrees in \Ga-Recursion Theory.Colin Bailey & Rod Downey - 1992 - Annals of Pure and Applied Logic 55 (3):205-236.
    Bailey, C. and R. Downey, Tabular degrees in \Ga-recursion theory, Annals of Pure and Applied Logic 55 205–236. We introduce several generalizations of the truth-table and weak-truth-table reducibilities to \Ga-recursion theory. A number of examples are given of theorems that lift from \Gw-recursion theory, and of theorems that do not. In particular it is shown that the regular sets theorem fails and that not all natural generalizations of wtt are the same.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  35.  6
    Serious Comedy: The Philosophical and Theological Significance of Tragic and Comic Writing in the Western Tradition.Patrick Downey - 2000 - Lexington Books.
    Patrick Downey finds comedy at the heart of the Western philosophical and theological tradition. In Serious Comedy Downey tracks tragedy and comedy from the beginning of Western thought to the twentieth century, beginning with an in-depth examination of Aristotle and three Platonic dialogues: the Republic, the Phaedrus, and the Symposium. In the book's second section Downey argues that the Bible is at heart a comedic narrative and analyzes the philosophical and theological implications of this comedy. In the (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  36. Concepts and Cases in Nursing Ethics, Third Edition.Michael Yeo, Anne Moorhouse, Pamela Kahn & Patricia Rodney (eds.) - 2010 - Broadview Press.
    Concepts and Cases in Nursing Ethics is a case-based exploration of the core principles of health care ethics applied to nursing. The book is a collaboration between philosopher-ethicist Michael Yeo and nurse-ethicist and educators Anne Moorhouse, Pamela Khan, and Patricia Rodney. It thus combines philosophical and ethical analysis with extensive knowledge and experience in nursing and health care. The book is organized around six main concepts in health care ethics: beneficence, autonomy, truthfulness, confidentiality, justice, and integrity. A chapter is (...)
     
    Export citation  
     
    Bookmark  
  37. Concepts and Cases in Nursing Ethics - Third Edition.Michael Yeo, Anne Moorhouse, Pamela Kahn & Patricia Rodney (eds.) - 2010 - Broadview Press.
    _Concepts and Cases in Nursing Ethics_ is a case-based exploration of the core principles of health care ethics applied to nursing. The book is a collaboration between philosopher-ethicist Michael Yeo and nurse-ethicist and educators Anne Moorhouse, Pamela Khan, and Patricia Rodney. It thus combines philosophical and ethical analysis with extensive knowledge and experience in nursing and health care. The book is organized around six main concepts in health care ethics: beneficence, autonomy, truthfulness, confidentiality, justice, and integrity. A chapter is (...)
     
    Export citation  
     
    Bookmark  
  38.  21
    Toward Interventions to Address Moral Distress: Navigating Structure and Agency.L. C. Musto, P. A. Rodney & R. Vanderheide - 2015 - Nursing Ethics 22 (1):91-102.
  39.  47
    Calibrating Randomness.Rod Downey, Denis R. Hirschfeldt, André Nies & Sebastiaan A. Terwijn - 2006 - Bulletin of Symbolic Logic 12 (3):411-491.
  40.  28
    Predictive Processing and the Representation Wars: A Victory for the Eliminativist.Adrian Downey - 2018 - Synthese 195 (12):5115-5139.
    In this paper I argue that, by combining eliminativist and fictionalist approaches toward the sub-personal representational posits of predictive processing, we arrive at an empirically robust and yet metaphysically innocuous cognitive scientific framework. I begin the paper by providing a non-representational account of the five key posits of predictive processing. Then, I motivate a fictionalist approach toward the remaining indispensable representational posits of predictive processing, and explain how representation can play an epistemologically indispensable role within predictive processing explanations without thereby (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  41.  26
    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  
  42.  24
    Evolving Trends in Nurse Regulation: What Are the Policy Impacts for Nursing's Social Mandate?Susan Duncan, Sally Thorne & Patricia Rodney - 2015 - Nursing Inquiry 22 (1):27-38.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  43.  13
    Head Transplantation: The Immune System, Phantom Sensations, and the Integrated Mind.Jocelyn Downey - 2018 - The New Bioethics 24 (3):228-239.
    The principal focus of this paper is to consider the implications of head and neck transplantation surgery on the issue of personal identity. To this end, it is noted that the immune system has not only been established to impose a level of self-identity on bodily cells, it has also been implicated in mental development and the regulation of mental state. In this it serves as a paradigm for the mind as the product of cephalic and extracephalic systems. The importance (...)
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  44.  9
    Relativizing Chaitin's Halting Probability.Rod Downey, Denis R. Hirschfeldt, Joseph S. Miller & André Nies - 2005 - Journal of Mathematical Logic 5 (02):167-192.
  45.  20
    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   12 citations  
  46.  6
    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.
  47.  12
    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.
  48.  3
    Atomic-Scale Study of Dislocation–Stacking Fault Tetrahedron Interactions. Part I: Mechanisms.Y. N. Osetsky, D. Rodney & D. J. Bacon - 2006 - Philosophical Magazine 86 (16):2295-2313.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  49. Bases of Supermaximal Subspaces and Steinitz Systems. I.Rod Downey - 1984 - Journal of Symbolic Logic 49 (4):1146-1159.
  50.  8
    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   13 citations  
1 — 50 / 784