Source author record

Rod Downey

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.LO

Catalog footprint

Research overview

5works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Realizing Computably Enumerable Degrees in Separating Classes

We investigate what collections of c.e.\ Turing degrees can be realised as the collection of elements of a separating $Π^0_1$ class of c.e.\ degree. We show that for every c.e.\ degree $\mathbf{c}$ , the collection $\{\mathbf{c}, \mathbf{0}'\}$ can be thus realized. We also rule out several attempts at constructing separating classes realizing a unique c.e.\ degree. For example, we show that there is no \emph{super-maximal} pair: disjoint c.e.\ sets $A$ and $B$ whose separating class is infinite, but every separator of c.e.\ degree is a finite variant of either $A$ or $\overline{B}$ .

preprint2016arXiv

Any FIP real computes a 1-generic

We construct a computable sequence of computable reals $\langle X_i\rangle$ such that any real that can compute a subsequence that is maximal with respect to the finite intersection property can also compute a Cohen 1-generic. This is extended to establish the same result with 2IP in place of FIP.

preprint2016arXiv

Solovay functions and their applications in algorithmic randomness

Classical versions of Kolmogorov complexity are incomputable. Nevertheless, in 1975 Solovay showed that there are computable functions $f > K+O(1)$ such that for infinitely many strings $σ$ , $f(σ)=K(σ)+O(1)$ , where $K$ denotes prefix-free Kolmogorov complexity (while $C$ denotes plain Kolmogorov complexity). Such an $f$ is now called a Solovay function. We prove that many classical results about $K$ can be obtained by replacing $K$ by a Solovay function. For example, the three following properties of a function $g$ all hold for the function $K$ . (i) The sum of the terms $\sum_n 2^{-g(n)}$ is a Martin-Löf random real. (ii) A sequence A is Martin-Löf random if and only if $C(A \upharpoonright n) > n -g(n)-O(1)$ . (iii) A sequence A is K-trivial if and only if $K(A \upharpoonright n) < g(n) + O(1)$ . We show that when fixing any of these three properties, then among all computable functions exactly the Solovay functions possess this property. Furthermore, this characterization extends accordingly to the larger class of right-c.e. functions.

preprint2014arXiv

Asymptotic density and the Ershov hierarchy

We classify the asymptotic densities of the $Δ^0_2$ sets according to their level in the Ershov hierarchy. In particular, it is shown that for $n \geq 2$ , a real $r \in [0,1]$ is the density of an $n$ -c.e.\ set if and only if it is a difference of left- $Π_2^0$ reals. Further, we show that the densities of the $ω$ -c.e.\ sets coincide with the densities of the $Δ^0_2$ sets, and there are $ω$ -c.e.\ sets whose density is not the density of an $n$ -c.e. set for any $n \in ω$ .

preprint2007arXiv

The Complexity of Orbits of Computably Enumerable Sets

The goal of this paper is to announce there is a single orbit of the c.e. sets with inclusion, $\E$, such that the question of membership in this orbit is $Σ^1_1$ -complete. This result and proof have a number of nice corollaries: the Scott rank of $\E$ is $\wock +1$; not all orbits are elementarily definable; there is no arithmetic description of all orbits of $\E$; for all finite $α\geq 9$ , there is a properly $Δ^0_α$ orbit (from the proof). A few small corrections made in this version

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.