with Rod Downey and Noam Greenberg
Proceedings of the American Mathematical Society 137(2009) no. 6, 2099--2109
Abstract: For every order $h$ such that $\sum_n 1/h(n)$ is finite, every K-trivial degree is $h$-jump-traceable. This motivated Cholak, Downey and Greenberg to ask whether this traceability property is actually equivalent to K-triviality, thereby giving the hoped for combinatorial characterisation of lowness for Martin-Lof randomness. We show however that the K-trivial degrees are properly contained in those that are $h$-jump-traceable for every convergent order h. Indeed, there is a computably enumerable degree which is not K-trivial but is jump traceable with respect to all superlinear orders.
Format:
![[PDF]](images/pdf.gif){kind=small}
with A. Lewis and K.-M. Ng
Journal of Symbolic Logic (in press)
Abstract: We prove a number of results in effective randomness, using methods in which $\Pi^0_1$ classes play an essential role. Amongst many others, the results proved include the fact that every PA Turing degree is the join of two random Turing degrees, and the existence of a minimal pair of LR degrees below the LR degree of the halting problem.
Format:
with Rod Downey and Noam Greenberg
Transactions of the American Mathematical Society. (in press)
Abstract: We investigate the connections between the complexity of a c.e. set, as calibrated by its strength as an oracle for Turing computations of functions in the Ershov hierarchy, and how strong reducibilities allows us to compute such sets. For example, we prove that a c.e. degree is totally $\omega$-c.e. iff every set in it is weak truth-table reducible to a hypersimple, or ranked, set. We also show that a c.e. degree is array computable iff every left-c.e. real of that degree is reducible in a computable Lipschitz way to a random left-c.e. real (an $\Omega$-number).
Format:
with Andy Lewis and Frank Stephan
Annals of Pure and Applied Logic. 156 Issue 1 (2008) pages 21--38
Abstract: We study the relationship between relative randomness and Turing computability. An oracle $A$ is LR below oracle $B$ if every $B$-random is $A$-random. We construct a $\Pi^0_1$ class which does not contain low for random paths, and every path is LR below the halting problem (this was later used in order to obtain a minimal pair of LR degrees below the LR degree of the halting problem). This shows that there is a hyperimmune-free Turing degree LR below 0'. We also show that every LR degree contains a hyperimmune set. We obtain a weak density result, toward Nies' question of whether the LR degrees of c.e. sets are dense: if two c.e. LR degrees have Turing comparable members, then there is an LR degree strictly inbetween and similarly related. This implies upward and downward density. Also, for any non-computable set $W$ we obtain $A$ in the same LR degree and Turing incomparable with $W$. A number of other structural results are obtained as well as that every jump traceable set in the REA hierarchy is superlow, partially answering a question of Simpson.
Format:
with Anthony Morphett
Mathematical Structures in Computer Science. 19(2009) 25--43
Abstract: We show that there is a computably enumerable function $f$ (i.e. computably approximable from below) which dominates almost all functions and $f\oplus W$ is incomplete, for all incomplete computably enumerable sets $W$ . Our main methodology is the LR equivalence relation on reals: $A\equiv_{LR} B$ iff the notions of A-randomness and B-randomness coincide. We also show that there are c.e. sets which cannot be split into two c.e. sets of the same LR degree. Moreover, we show that a c.e. set is low for random iff it computes no c.e. set with this property.
Format:
with Andy Lewis and Mariya Soskova
Journal of Symbolic Logic73(2008), Issue 2, 559--577
Abstract: We say that $A$ is LR reducible to $B$ if every $B$-random number is $A$-random. Intuitively this means that if oracle $A$ can identify some patterns on some real $Z$ , oracle $B$ can also find patterns on $Z$. In other words, $B$ is at least as good as $A$ for this purpose. This notion was defined by Andre Nies for the study of relative randomness. We study the structure of the LR degrees globally and locally (i.e., restricted to the computably enumerable degrees) and their relationship with the Turing degrees. Among other results we show that whenever $Z$ is not generalized low 2, the LR degree of $Z$ bounds continuum many degrees (so that, in particular, there exist LR degrees with uncountably many predecessors) and we give sample results which demonstrate how various techniques from the theory of the c.e. degrees can be used to prove results about the c.e. LR degrees.
Format:
with Paul Brodhead, Douglas Cenzer, Seyyed Dashti and Rebecca Weber
Journal of Logic and Computation 17(2007) 1041-1062.
Abstract: We investigate notions of randomness in the space of nonempty closed subsets of the Cantor space. A probability measure is given and a version of the Martin-Lof test for randomness is defined. There are $\Pi^0_2$ random closed sets but there are no $\Pi^0_1$ random closed sets. It is shown that any random closed set is perfect, has measure 0, and has box dimension $\log_2(4/3)$. Also, a random closed set has no n-c.e. elements. The problem of compressibility of trees (in the sense of Kolmogorov complexity) is also explored.
Format:
with Bahareh Afshari, S.~Barry Cooper and Frank Stephan
Journal of Logic and Computation 17(2007) 1025--1040.
Abstract: This paper extends Post's programme to finite levels of the Ershov hierarchy of $\Delta^0_2$ sets. Our initial characterisation, in the spirit of Post, of the degrees of the immune and hyperimmune $n$-enumerable sets leads to a number of results setting other immunity properties in the context of the Turing and weak truth-table degrees derived from the Ershov hierarchy. For instance, we show that any $n$-enumerable hyperhyperimmune set must be co-enumerable, for each $n>1$. The situation with regard to the weak truth table degrees is particularly interesting, as demonstrated by a range of results concerning the wtt-predecessors of hypersimple sets.
Finally, we give a number of results directed at characterising basic classes of n-enumerable degrees in terms of natural information content. For example, a 2-enumerable degree contains a 2-enumerable dense immune set iff it contains a 2-enumerable r-cohesive set iff it bounds a high enumerable set. This result is extended to a characterisation of n-enumerable degrees which bound high enumerable degrees. Furthermore, a characterisation for n-enumerable degrees bounding only low 2 enumerable degrees is given.
Format:
with Andy Lewis
Annals of Pure and Applied Logic 145(2007) Issue 3, pages 252--257.
Abstract: We show that there exists a real $Z$ such that, for all reals $X$, if $Z$ is linear (sw or computably Lipschitz) reducible to $X$ then $X$ is Turing reducible to $Z$. In fact, every random real satisfies this quasi-maximality property. As a corollary we may conclude that there exists no complete $\Delta^0_2$ real with respect to the computably Lipschitz (cl, for short) reducibility. Upon realizing that quasi-maximality does not characterize the random reals -- there exist reals which are not random but which are of quasi-maximal cl degree -- it is then natural to ask whether maximality could provide such a characterization. Such hopes, however, are in vain since no real is of maximal cl-degree.
Format:
with Andy Lewis
Notre Dame Journal of Formal Logic 47(2006) Issue 3, pages 361--370
Abstract: Hypersimple sets were introduced as a solution to Post's problem for the structure of the truth table degrees, and Rogers observed that they were a natural solution to Post's problem for the weak truth table degrees as well. Hence it is interesting to know the distribution of these natural solutions in the weak truth table degrees.
We show that between any c.e. wtt degrees $b < c$ there is another c.e. wtt degree which does not contain any hypersimple set (i.e. it is hypersimple-free). We also show that for every $w < c$ in the c.e. wtt degrees such that $w$ is hypersimple, there is a hypersimple a such that $w < a < c$ (where hypersimple is a degree which contains a hypersimple set).
Format:
with Andy Lewis
Notre Dame Journal of Formal Logic 47(2006) Issue 2, pages 197--209
Abstract: The strong weak truth table (sw) reducibility [this was later called computably Lipchitz, or cl] was suggested by Downey, Hirschfeldt, and LaForte as a measure of relative random- ness, alternative to the Solovay reducibility. It also occurs naturally in proofs in classical computability theory as well as in the recent work of Soare, Nabutovsky and Weinberger on applications of computability to differential geometry. We study the sw-degrees of c.e. reals and con- struct a c.e. real which has no random c.e. real (i.e. $\Omega$ number) sw-above it.
Format:
with Andy Lewis
Annals of Pure and Applied Logic 141(2006) Issues 1-2, pages 51--60
Abstract: The identity bounded Turing reducibility is implicity in many parts of classical computability theory, and was explicitely introduced by Soare as a tool of applications to differential geometry. Also, it has played central role in some parts of effective randomness, for example the proof of the undecidability of the Solovay degrees of computably enumerable reals by Downey, Hirchfeldt and Laforte. We show that the computably enumerable identity bounded Turing degrees are not dense, although they are downward and upward dense.
Format: