Results for 'Rod G. Downey'

1000+ found
Order:
  1.  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  
  2.  21
    Index Sets and Parametric Reductions.Rod G. Downey & Michael R. Fellows - 2001 - 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 (5 more)  
     
    Export citation  
     
    Bookmark  
  3.  11
    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.
  4.  7
    Difference Sets and Computability Theory.Rod Downey, Zoltán Füredi, Carl G. Jockusch & Lee A. Rubel - 1998 - Annals of Pure and Applied Logic 93 (1-3):63-72.
    For a set A of non-negative integers, let D be the set of non-negative differences of elements of A. Clearly, if A is computable, then D is computably enumerable. We show that every simple set which contains 0 is the difference set of some computable set and that every computably enumerable set is computably isomorphic to the difference set of some computable set. Also, we prove that there is a computable set which is the difference set of the complement of (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  5.  14
    Effective Presentability of Boolean Algebras of Cantor-Bendixson Rank 1.Rod Downey & Carl G. Jockusch - 1999 - Journal of Symbolic Logic 64 (1):45-52.
    We show that there is a computable Boolean algebra $\mathscr{B}$ and a computably enumerable ideal I of $\mathscr{B}$ such that the quotient algebra $\mathscr{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 (8 more)  
     
    Export citation  
     
    Bookmark  
  6. A Weakly 2-Generic Which Bounds a Minimal Degree.Rodney G. Downey & Satyadev Nandakumar - forthcoming - Journal of Symbolic Logic:1-22.
    Jockusch showed that 2-generic degrees are downward dense below a 2-generic degree. That is, if a is 2-generic, and $0 < {\bf{b}} < {\bf{a}}$, then there is a 2-generic g with $0 < {\bf{g}} < {\bf{b}}.$ In the case of 1-generic degrees Kumabe, and independently Chong and Downey, constructed a minimal degree computable from a 1-generic degree. We explore the tightness of these results. We solve a question of Barmpalias and Lewis-Pye by constructing a minimal degree computable from a (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  7.  36
    Computability, Enumerability, Unsolvability, Directions in Recursion Theory, Edited by S. B. Cooper, T. A. Slaman, and S. S. Wainer, London Mathematical Society Lecture Note Series, No. 224, Cambridge University Press, Cambridge, New York, and Oakleigh, Victoria, 1996, Vii + 347 Pp. - Leo Harrington and Robert I. Soare, Dynamic Properties of Computably Enumerable Sets, Pp. 105–121. - Eberhard Herrmann, On the ∀∃-Theory of the Factor Lattice by the Major Subset Relation, Pp. 139–166. - Manuel Lerman, Embeddings Into the Recursively Enumerable Degrees, Pp. 185–204. - Xiaoding Yi, Extension of Embeddings on the Recursively Enumerable Degrees Modulo the Cappable Degrees, Pp. 313–331. - André Nies, Relativization of Structures Arising From Computability Theory. Pp. 219–232. - Klaus Ambos-Spies, Resource-Bounded Genericity. Pp. 1–59. - Rod Downey, Carl G. Jockusch, and Michael Stob. Array Nonrecursive Degrees and Genericity, Pp. 93–104. - Masahiro Kumabe, Degrees of Generic Sets, Pp. 167–183. [REVIEW]C. T. Chong - 1999 - Journal of Symbolic Logic 64 (3):1362-1365.
  8.  35
    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  
  9.  25
    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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  10.  13
    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  
  11.  8
    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  
  12.  10
    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 [Formula: see text] classes, Ann. Pure Appl. Logic 59 79–139], Cenzer, Downey, Jockusch and Shore proved the density of degrees containing members of countable thin [Formula: see text] classes. In the same paper, Cenzer et al. also proved the existence of degrees containing no members of thin [Formula: see text] classes. We will prove in this paper that the c.e. degrees containing no members of thin [Formula: see text] classes are dense in the c.e. degrees. We (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  13.  18
    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  
  14.  11
    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  
  15.  7
    Effects of Δ9 -Tetrahydrocannabinol on Stimulus Control.Joseph Lyons, Douglas P. Ferraro, Janet E. Lyons, Joseph G. Sullivan & Daniel Downey - 1973 - Bulletin of the Psychonomic Society 2 (5):302-304.
  16.  58
    Calibrating Randomness.Rod Downey, Denis R. Hirschfeldt, André Nies & Sebastiaan A. Terwijn - 2006 - Bulletin of Symbolic Logic 12 (3):411-491.
  17.  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  
  18.  11
    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  
  19.  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   22 citations  
  20.  21
    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  
  21.  27
    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  
  22.  9
    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  
  23.  61
    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  
  24.  9
    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  
  25. Bases of Supermaximal Subspaces and Steinitz Systems. I.Rod Downey - 1984 - Journal of Symbolic Logic 49 (4):1146-1159.
  26. 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   11 citations  
  27.  17
    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   7 citations  
  28.  2
    Lattice Nonembeddings and Initial Segments of the Recursively Enumerable Degrees.Rod Downey - 1990 - Annals of Pure and Applied Logic 49 (2):97-119.
  29.  41
    Completely Mitotic R.E. Degrees.R. G. Downey & T. A. Slaman - 1989 - Annals of Pure and Applied Logic 41 (2):119-152.
  30.  10
    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  
  31.  68
    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  
  32.  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  
  33.  11
    Computably Enumerable Sets and Quasi-Reducibility.R. Downey, G. LaForte & A. Nies - 1998 - Annals of Pure and Applied Logic 95 (1-3):1-35.
    We consider the computably enumerable sets under the relation of Q-reducibility. We first give several results comparing the upper semilattice of c.e. Q-degrees, RQ, Q, under this reducibility with the more familiar structure of the c.e. Turing degrees. In our final section, we use coding methods to show that the elementary theory of RQ, Q is undecidable.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  34.  11
    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  
  35.  16
    Structural Interactions of the Recursively Enumerable T- and W-Degrees.R. G. Downey & M. Stob - 1986 - Annals of Pure and Applied Logic 31 (2):205-236.
  36.  26
    Jumps of Hemimaximal Sets.Rod Downey & Mike Stob - 1991 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 37 (8):113-120.
  37.  21
    Highness and Bounding Minimal Pairs.Rodney G. Downey, Steffen Lempp & Richard A. Shore - 1993 - Mathematical Logic Quarterly 39 (1):475-491.
  38.  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.
  39.  16
    On $\Pi^0_1$ Classes and Their Ranked Points.Rod Downey - 1991 - Notre Dame Journal of Formal Logic 32 (4):499-512.
  40.  31
    Classifications of Degree Classes Associated with R.E. Subspaces.R. G. Downey & J. B. Remmel - 1989 - Annals of Pure and Applied Logic 42 (2):105-124.
    In this article we show that it is possible to completely classify the degrees of r.e. bases of r.e. vector spaces in terms of weak truth table degrees. The ideas extend to classify the degrees of complements and splittings. Several ramifications of the classification are discussed, together with an analysis of the structure of the degrees of pairs of r.e. summands of r.e. spaces.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  41. 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  
  42.  17
    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.
  43.  23
    Maximal Theories.R. G. Downey - 1987 - Annals of Pure and Applied Logic 33 (3):245-282.
  44.  25
    Minimal Degrees Recursive in 1-Generic Degrees.C. T. Chong & R. G. Downey - 1990 - Annals of Pure and Applied Logic 48 (3):215-225.
  45.  16
    Jumps of Hemimaximal Sets.Rod Downey & Mike Stob - 1991 - Mathematical Logic Quarterly 37 (8):113-120.
  46.  23
    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   2 citations  
  47.  34
    Degree Theoretic Definitions of the Low2 Recursively Enumerable Sets.Rod Downey & Richard A. Shore - 1995 - Journal of Symbolic Logic 60 (3):727 - 756.
  48.  18
    Recursion Theory and Ordered Groups.R. G. Downey & Stuart A. Kurtz - 1986 - Annals of Pure and Applied Logic 32 (2):137-151.
  49.  26
    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  
  50.  37
    Automorphisms of Supermaximal Subspaces.R. G. Downey & G. R. Hird - 1985 - Journal of Symbolic Logic 50 (1):1-9.
1 — 50 / 1000