Rod Downey
YOU?
Author Swipe
View article: NOTES ON SACKS’ SPLITTING THEOREM
NOTES ON SACKS’ SPLITTING THEOREM Open
We explore the complexity of Sacks’ Splitting Theorem in terms of the mind change functions associated with the members of the splits. We prove that, for any c.e. set A , there are low computably enumerable sets $A_0\sqcup A_1=A$ splitting…
View article: Lowness properties for strong reducibilities and the computational power of maximal sets
Lowness properties for strong reducibilities and the computational power of maximal sets Open
We introduce the notion of eventually uniformly weak truth table array computable (e.u.wtt-a.c.) sets. As our main result, we show that a computably enumerable (c.e.) set has this property iff it is weak truth table ([Formula: see text]-) …
View article: ON THE C.E. DEGREES REALIZABLE IN $\Pi ^0_1$ CLASSES
ON THE C.E. DEGREES REALIZABLE IN $\Pi ^0_1$ CLASSES Open
We study for each computably bounded $\Pi ^0_1$ class P the set of degrees of c.e. paths in P . We show, amongst other results, that for every c.e. degree a there is a perfect $\Pi ^0_1$ class where all c.e. members have degree a . We also…
View article: Three topological reducibilities for discontinuous functions
Three topological reducibilities for discontinuous functions Open
We define a family of three related reducibilities, $\leq _{\mathbf {T}}$, $\leq _{\mathbf {tt}}$ and $\leq _{\mathbf {m}}$, for arbitrary functions $f,g:X\rightarrow \mathbb R$, where $X$ is a compact separable metric space. The $\equiv _…
View article: A MINIMAL SET LOW FOR SPEED
A MINIMAL SET LOW FOR SPEED Open
An oracle A is low-for-speed if it is unable to speed up the computation of a set which is already computable: if a decidable language can be decided in time $t(n)$ using A as an oracle, then it can be decided without an oracle in time $p(…
View article: Hierarchy of Computably Enumerable Degrees II
Hierarchy of Computably Enumerable Degrees II Open
A transfinite hierarchy of Turing degrees of c.e.\ sets has been used to calibrate the dynamics of families of constructions in computability theory, and yields natural definability results. We review the main results of the area, and disc…
View article: RELATIONSHIPS BETWEEN COMPUTABILITY-THEORETIC PROPERTIES OF PROBLEMS
RELATIONSHIPS BETWEEN COMPUTABILITY-THEORETIC PROPERTIES OF PROBLEMS Open
A problem is a multivalued function from a set of instances to a set of solutions . We consider only instances and solutions coded by sets of integers. A problem admits preservation of some computability-theoretic weakness property if ever…
View article: Realizing Computably Enumerable Degrees in Separating Classes
Realizing Computably Enumerable Degrees in Separating Classes Open
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}…
View article: Computability and Randomness
Computability and Randomness Open
RootsVon Mises.Around 1930, Kolmogorov and others founded the theory of probability, basing it on measure theory.Probability theory is concerned with the distribution of outcomes in sample spaces.It does not seek to give any meaning to the…
View article: Three topological reducibilities for discontinuous functions
Three topological reducibilities for discontinuous functions Open
We define a family of three related reducibilities, $\leq_T$, $\leq_{tt}$ and $\leq_m$, for arbitrary functions $f,g:X\rightarrow\mathbb R$, where $X$ is a compact separable metric space. The $\equiv_T$-equivalence classes mostly coincide …
View article: Relationships between computability-theoretic properties of problems
Relationships between computability-theoretic properties of problems Open
A problem is a multivalued function from a set of \emph{instances} to a set of \emph{solutions}. We consider only instances and solutions coded by sets of integers. A problem admits preservation of some computability-theoretic weakness pro…
View article: On a question of Kalimullin
On a question of Kalimullin Open
We prove that for every computable limit ordinal $\alpha$ there exists a computable structure $\mathcal {A}$ which is $\Delta ^0_\alpha$-categorical and $\alpha$ is smallest such, but nonetheless for every isomorphic computable copy $\math…
View article: Solovay functions and their applications in algorithmic randomness
Solovay functions and their applications in algorithmic randomness Open
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 …
View article: Integer Valued Betting strategies and Turing Degrees
Integer Valued Betting strategies and Turing Degrees Open
Betting strategies are often expressed formally as martingales. A martingale is called integer-valued if each bet must be an integer value. Integer-valued strategies correspond to the fact that in most betting situations, there is a minimu…