Abstract:
We study computable Polish spaces and Polish groups up to homeomorphism. We
prove a natural effective analogy of Stone duality, and we also develop an effective
definability technique which works up to homeomorphism. As an application, we show
that there is a Δ^{0}_{2} Polish space not homeomorphic to a computable one. We also prove
that, for any computable ordinal α, there is an effectively closed set not homeomorphic
to any 0^{(α)}-computable Polish space; this answers a question of Nies. We also prove analogous results for compact Polish groups.
Abstract:
Let A and B be two finite sets of computable real numbers which denote the allowable wagers, i.e. the additive difference of capital at any betting position. Following the terminology in Chalcraft et. al., an A-martingale is a martingale whose wagers are limited to elements in A, and a B-martingale has wagers limited to elements in B. Extending the work of Chalcraft et. al., Bavly and Peretz establish necessary and sufficient conditions for some A-martingale to succeed betting on sequences that B-martingales can succeed betting on for arbitrary infinite sets of reals.
In this paper, we investigate the analogous question of comparative betting power of martingales when the ratios of bets are restricted to a finite set of rationals which excludes 1. This contrasts with the setting of simple martingales and almost simple martingales as investigated by Ambos-Spies, Mayordomo, Wang and Zheng. We derive necessary and sufficient conditions for deciding when a set of ratios allows greater power in betting as compared to another. Analogous to a recent work of Teutsch, we establish that success and strong success of martingales are distinct notions in the setting of restricted ratio betting.
Abstract:
We introduce a framework for online structure theory. Our approach generalises notions arising independently in several areas of computability theory and complexity theory. We suggest a unifying approach using operators where we allow the input to be a countable object of any arbitrary complexity.
Abstract:
We show that there is a cuppable c.e. degree, all of whose cupping partners are high. In particular, not all cuppable degrees are low_{3}-cuppable, or indeed low_{n} cuppable for any n, refuting a conjecture by Li. On the other hand, we show that one cannot improve highness to superhighness.
Abstract:
We systematically investigate into the online content of finitely generated structures. The online content of an algebraic or combinatorial structure is perhaps best reflected by its FPR-degrees (to be defined). We show that the FPR-degrees of a finitely generated structure must be dense. We prove that, however, it does not have to be upwards dense by constructing an example of a f.g. structure with the least and the greatest presentation (which are not equivalent). Finally, we disprove a natural conjecture about honestly generated structures (to be defined).
Abstract:
We consider three strong reducibilities, s_{1}, s_{2}, Q_{1} (where we identify a reducibility ≤_{r} with its index r), for which (with proper inclusions) we have s_{1} ⊂ s_{2} ⊂ s (s denotes s-reducibility),
and Q_{1} ⊂ Q (Q denotes Q-reducibility). It is known that s and Q are isomorphic, via the isomorphism given by taking complements of sets, which induces also an isomorphism between s_{1} and Q_{1}. We show that there is a minimal Δ^{0}_{2}s_{2}-degree, but the nonzero Π^{0}_{1}s_{2}-degrees are downwards dense; and there exists a minimal Π^{0}_{1}s_{1}-degree (and thus a minimal c.e. Q_{1}-degree; every such one must contain a hypersimple set but no hyperhypersimple set).
Abstract:
We introduce a transfinite hierarchy of genericity notions stronger than 1-genericity and weaker than 2-genericity. There are many connections
with Downey and Greenberg's hierarchy of totally ω-c.a. degrees. We
show that the hierarchy is proper, and moreover, that the separation of each
level can be witnessed by a Δ^{0}_{2}degree. We finally consider downward density
for these classes, and give some further directions for research.
Abstract:
We define a class of computable functions over the real numbers using functional schemes similar to the class of primitive and partial recursive functions defined by Godel and Kleene. We show that this class of functions can also be characterized
by what we call master-slave machines. The proof of the characterization gives a normal form theorem in the style of Kleene. The equivalence itself illustrates that this characterization is a natural combination of two of the most infuential theories of computation over the real numbers, namely, the type-two theory of effectivity(TTE) and the Blum-Shub-Smale (BSS) model of computation.
Proceedings of the American Mathematical Society. Accepted.
Abstract:
The paper contributes to the general program which aims to eliminate unbounded search from proofs and procedures in computable structure theory. A countable structure in a finite language is punctual if its domain is ω and its operations and relations are primitive recursive. A function f is punctual if both f and f^{-1} are primitive recursive. We prove that there exists a countable rigid algebraic structure which has exactly two punctual presentations, up to punctual isomorphism.
Abstract:
We characterize the linear order types τ with the property that given any countable linear order L, τ ⋅ L is a computable linear order iff L is a computable linear order, as exactly the finite nonempty order types.
Abstract:
Given an integer n>0 we give a computable injective listing of the isomorphism types of all computable abelian p-groups of Ulm type at most n. We give a similar result for certain classes of profinite groups.
Abstract:
We show that for every intermediate Σ^{0}_{2}s-degree (i.e. a nonzero s-degree strictly below the s-degree of the complement of the halting set) there exists an incomparable Π^{0}_{1}s-degree. (The same proof yields a similar result for other positive reducibilities as well, including enumeration reducibility.) As a consequence, for every intermediate Π^{0}_{2}Q-degree (i.e. a nonzero Q-degree strictly below the Q-degree of the halting set) there exists an incomparable Σ^{0}_{1}Q-degree. We also show how these results can be applied to provide proofs or new proofs (essentially already known, although some of them not explicitly noted in the literature) of upper density results in local structures of s-degrees and Q-degrees.
Abstract:
We study the relationship between effective domination properties and the bounded jump. We answer two open questions about the bounded jump: (1) We prove that the analogue of Sacks' jump inversion fails for the bounded jump and the wtt-reducibility. (2) We prove that no c.e. bounded high set can be low by showing that they all have to be Turing complete. We characterize the class of c.e. bounded high sets as being those sets computing the Halting problem via a reduction with use bounded by an ω-c.e. function. We define several notions of a c.e. set being effectively dominant, and show that together with the bounded high sets they form a proper hierarchy.
Memoirs of the American Mathematical Society. To appear.
Abstract:
We prove that there is a Δ^{0}_{2}set A whose weak truth table degree is minimal, and A Turing computes a non-computable set of computably enumerable degree. We also prove that it is impossible to make A have c.e. Turing degree, that is, every weak truth table degree contained in a c.e. Turing degree is not minimal with respect to weak truth table degrees.
Abstract:
We give a partial answer to an important open problem in descriptive set theory, the Decomposability Conjecture for Borel functions on an analytic subset of a Polish space to a separable metrizable space. Our techniques employ deep results from effective descriptive set theory and recursion theory. In fact it is essential to extend several prominent results in recursion theory (e.g. the Shore-Slaman Join Theorem) to the setting of Polish spaces. As a by-product we give both positive and negative results on the Martin Conjecture on the degree preserving Borel functions between Polish spaces. Additionally we prove results about the transfinite version as well as the computable version of the Decomposability Conjecture, and we explore the idea of applying the technique of turning Borel-measurable functions into continuous ones.
Transactions of the American Mathematical Society (2019), 372(5), pp. 3713-3753.
Abstract:
We settle the longstanding Kierstead's Conjecture in the negative. We do this by constructing a computable linear order with no rational subintervals, where every block has order type finite or ζ, and where every computable copy has a strongly nontrivial Π^{0}_{1} automorphism. We also construct a strongly η-like linear order where every block has size at most 4 with no rational subinterval such that every Δ^{0}_{2} isomorphic computable copy has a nontrivial Π^{0}_{1} automorphism.
Abstract:
We prove that for every computable limit ordinal α there exists a computable linear ordering ℒ which is Δ^{0}_{α}-categorical and α is smallest such, but nonetheless for every isomorphic computable copy ℬ of ℒ there exists a β < α such that ℬ ≅_{ Δβ } ℒ. This answers a question left open in the earlier work of Downey, Igusa, and Melnikov. We also show that such examples can be found among ordered abelian groups and real-closed fields.
Journal of Symbolic Logic (2019), 84(4), pp. 1630-1669.
Abstract:
A structure is automatic if its domain, functions, and relations are all regular languages. Using the fact that every automatic structure is decidable, in the literature many decision problems have been solved by giving an automatic presentation of a particular structure. Khoussainov and Nerode asked whether there is some way to tell whether a structure has, or does not have, an automatic presentation. We answer this question by showing that the set of Turing machines that represent automata-presentable structures is Σ^{1}_{1}-complete. We also use similar methods to show that there is no reasonable characterisation of the structures with a polynomial-time presentation in the sense of Nerode and Remmel.
Israel Journal of Mathematics (2019), 234(2), pp. 959-1000.
Abstract:
We study the algorithmic content of back-and-forth proofs for homogeneous structures and graphs from the perspective of Turing computations in which unbounded search is forbidden. The paper contributes to a general program that aims to understand the role of unbounded search in computable algebra.
Notre Dame Journal of Formal Logic (2019), 60(4), pp. 733-761.
Abstract:
We study the degree structure of the ω-r.e., n-r.e. and Π^{0}_{1}equivalence relations under the computable many-one reducibility. In particular we investigate for each of these classes of degrees the most basic questions about the structure of the partial order. We prove the existence of the greatest element for the ω-r.e. and n-r.e. equivalence relations. We provide computable enumerations of the degrees of ω-r.e., n-r.e. and Π^{0}_{1}equivalence relations. We prove that for all the degree classes considered, upward density holds and downward density fails.
Abstract:
We prove that c.c. torsion abelian groups can be described by a Π^{0}_{4}-predicate that describes the failure of a brute-force diagonalisation attempt on such groups. We show that there is no simpler description since their index set is Π^{0}_{4}-complete. The results can be viewed as a solution to a 60 year-old problem of Mal'cev in the case of torsion abelian groups. We prove that a computable torsion abelian group has one or infinitely many computable copies, up to computable isomorphism. The result confirms a conjecture of Goncharov from the early 1980s for the case of torsion abelian groups.
Annals of Pure and Applied Logic (2018), 169(8), pp. 803-834.
Abstract:
We investigate the extent to which a c.e. degree can be split into two smaller c.e. degrees which are computationally weak. In contrast to a result of Bickford and Mills that 0' can be split into two
superlow c.e. degrees, we construct a SJT-hard c.e. degree which is not
the join of two superlow c.e. degrees. We also prove that every high
c.e. degree is the join of two array computable c.e. degrees, and that
not every high_{2} c.e. degree can be split in this way. Finally we extend a
result of Downey, Jockusch and Stob by showing that no totally ω-c.a.
wtt-degree can be cupped to the complete wtt-degree.
Abstract:
We suggest several new ways to compare fully primitive recursive presentations of a structure. Properties of this kind have never been seen in computable structure theory. We prove that these new definitions are nonequivalent.
Theoretical Computer Science (2017), 702, pp. 23-33.
Abstract:
Bennett's concept of logic depth seeks to capture the idea that a language has a lot of useful information. Thus we would expect that neither suffciently random nor suffciently computationally trivial sequences be deep. A question of Moser and Stephan explores the boundary of this assertion, asking if there is a c.e. low (Bennett) deep language. We answer this question affirmatively constructing a superlow c.e. Bennett deep language.
Journal of Mathematical Logic, (2017), 17, 1750008.
Abstract:
We solve a problem posed by Goncharov and Knight. More specifically, we produce an effective Friedberg (i.e., injective) 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.
Information Processing Letters (2017), 125, pp. 41-45.
Abstract:
The main purpose of this paper is to answer two questions about the distributional complexity of multi-branching trees. We first show that for any independent distribution d on assignments for a multi-branching tree, a certain directional algorithm DIRd is optimal among all the depth-first algorithms (maybe also non-directional ones) with respect to d. We next answer an open question in [2] by showing that for any balanced multi-branching AND-OR tree, the optimal distributional complexity among all the independent distributions (ID) is actually achieved by an independent and identical distribution (IID).
Theoretical Computer Science (2017), 674, pp. 73–98.
Abstract:
In this article we suggest a systematic approach to studying algebraic structures using primitive recursion. Our intention is to fill the gap between the theory of computable structures and "feasible" (polynomial-time) algebra. As will be clarified in the introduction, the class PR_{ω} of primitive recursive structures upon the domain of ω is the most
suitable intermediate notion between computable and polynomial time structures. The main idea is that we want to see more of the structure computed now, i.e. without any reference to the unbounded μ-operator. We call such structures fully primitive recursive (informally, computable without delay). Among other results, we show that in many common algebraic classes every computable structure has an isomorphic copy in PR_{ω}. On the other hand, there are also natural examples of computable structures that have no fully primitive recursive presentations. Our proofs use techniques specific to a class under consideration, but there are some general observable patterns. We also study the category of fully primitive recursive structures under primitive recursive isomorphism with primitive recursive inverse. The induced notion of fpr-categoricity (informally, categoricity without delay) behaves very differently from its analogy from computable structure theory, namely computable categoricity. We describe fpr-categorical structures in many common algebraic classes. In all these classes fpr-categoricity implies computable categoricity. Our proofs blend novel strategies with techniques from computable structure theory. Remarkably, with some effort we can construct an fpr-categorical structure that is not computably categorical. The proof is interesting on its own right, and the new technique that we introduce in the proof has some further applications. We also touch on several further topics including the primitive recursive analogies of 1-decidability, intrinsic computability, and relativization. Most of these directions we leave wide open.
Annals of Pure and Applied Logic (2016), 167(11), pp.1123-1138.
Abstract:
We investigate which effectively presented abelian p-groups are isomorphic relative to the halting problem. The standard approach to this and similar questions uses the notion of Δ^{0}_{2}-categoricity. We partially reduce the description of Δ^{0}_{2}-categorical p-groups of Ulm type 1 to the analogous problem for equivalence structures. For the sake of the mentioned above reduction, we introduce a new notion of effective Δ^{0}_{2}-categoricity that lies strictly in-between plain Δ^{0}_{2}-categoricity and relative Δ^{0}_{2}-categoricity (to be defined). We then reduce the problem of classifying effective Δ^{0}_{2}-categoricity to a question stated in terms of Δ^{0}_{2}-sets. Among other results, we show that for c.e. Turing degrees bounding such sets is equal to being complete.
Journal of Symbolic Logic (2016), 81(4), pp. 1225-1254.
Abstract:
We introduce the notion of finitary computable reducibility on equivalence relations on the domain ω. This is a weakening of the usual notion of computable reducibility, and we show it to be distinct in several ways. In particular, whereas no equivalence relation can be
Π^{0}_{n+2}-complete under computable reducibility, we show that, for every n, there does exist a natural equivalence relation which is
Π^{0}_{n+2}-complete under finitary reducibility. We also show that our hierarchy of finitary reducibilities does not collapse, and illustrate how it sharpens certain known results. Along the way, we present several new results which use computable reducibility to establish the complexity of various naturally defined equivalence relations in the arithmetical hierarchy. We also refute a possible generalization of Myhill's Theorem.
Proceedings of the American Mathematical Society (2016), 144(4), pp. 1735-1744.
Abstract: Working in the Turing degree structure, we show that those degrees which contain computably enumerable sets all satisfy the meet property, i.e. if a is c.e. and b < a , then there exists non-zero m < a with b ∩ m = 0. In fact, more than this is true: m may always be chosen to be a minimal degree. This settles a conjecture of Cooper and Epstein from the 80s.
Abstract: We show that (C[0,1]; sup) possesses infinitely many computable structures non-equivalent up to a computable isometry. We also investigate if the usual operations on C[0,1] are necessarily computable in every computable structure on C[0,1]. Among other results, we show that there is a computable structure on C[0,1] which computes + and the scalar multiplication, but does not compute the operation of pointwise multiplication of functions. Another
unexpected result is that there exists more than one computable structure making C[0,1] a computable Banach algebra.
Journal of Logic and Computation (2015), 25(4), pp 1073-1089. doi:10.1093/logcom/exs083
Abstract:
Consider a Martin-Lof random Δ^{0}_{2} set Z. We give lower bounds for the number of changes of the first n bits of Z_{s} for computable approximations of Z. We show that each nonempty Π^{0}_{1} class has a low member Z with a computable approximation that changes only o(2^{n}) times. We prove that each superlow ML-random set already satisfies a stronger randomness notion called balanced randomness, which implies that for each computable approximation and each constant c, there are infinitely many n such that the first n bits of Z_{s} changes more than c2^{n} times.
Abstract:
We examine the sequences A that are low for dimension, i.e., those for which the effective (Hausdorff) dimension relative to A is the same as the unrelativized effective dimension. Lowness for dimension is a weakening of lowness for randomness, a central notion in effective randomness. By considering analogues of characterizations of lowness for randomness, we show that lowness for dimension can be characterized in several ways. It is equivalent to lowishness for randomness, namely, that every Martin-Lof random sequence
has effective dimension 1 relative to A, and lowishness for K, namely, that the limit of K^{A}(n)/K(n) is 1.
We show that there is a perfect Π^{0}_{1}-class of low for dimension sequences. Since there are only countably many low for random sequences, many more sequences are low for dimension. Finally, we prove that every low for dimension is jump-traceable in order n^{c}, for any c > 0.
International Journal of Algebra and Computation (2014), 24(7), pp.1055-1084.
Abstract: In the paper we develop a technique that we call iterated effective embeddings. We use this technique to confirm and extend a 30-year old conjecture of Ash, Knight and Oates. More specically, Ash, Knight and Oates conjectured that there exists a reduced abelian p-group of Ulm type ω such that its effective invariants, limitwise monotonic functions, are not uniform. We construct a computable reduced abelian p-group of Ulm type ω having its invariants, limitwise monotonic functions, not only non-uniform but at the maximal potentially possible level of non-uniformity. The result confirms the conjecture in a strong way, and it also provides us with an explanation of why computable reduced p-groups of Ulm type ω seem hard to classify in general.
Journal of Symbolic Logic (2014), 79(3), pp. 859-881.
Abstract: We study the relative complexity of equivalence relations and preorderings from computability theory, complexity theory, and effective. All relations studied are on natural numbers. We show that there is a Π^{0}_{1}-complete equivalence relation, but no Π^{0}_{k}-complete for k>1. We show that many Σ^{0}_{k} preorderings arising naturally in the above-mentioned areas are in fact Σ^{0}_{k}-complete. This includes polynomial time m-reducibility on exponential time sets, which is Σ^{0}_{2}, almost inclusion on r.e. sets, which is Σ^{0}_{3}, and Turing reducibility on r.e. sets, which is Σ^{0}_{4}.
Abstract: We investigate how much information in a random set can be preserved if one splits the random set into two halves in a recursive way. We prove that every high Turing degree contains a Schnorr random set Z such that Z ≡_{T} Z ∩ R for every infinite recursive set R. This is impossible for a Martin-Lof random set Z since the two halves of a ML-random set are Turing incomparable. Nevertheless we show that for each set X there is a ML-random set Z ≥_{T} X such that for all recursive sets R, either Z ∩ R ≥_{T} X or Z \ R ≥_{T} X.
Journal of Symbolic Logic (2014), 79(3), pp. 776-791.
Abstract: We extend our work on difference randomness. Each component of a difference test is a Boolean combination of two r.e. open sets; here we consider tests in which the k^{th} component is a Boolean combination of g(k) r.e. open sets for a given recursive function g. We use this method to produce an alternate characterization of weak Demuth randomness in terms of these tests and further show that a real is weakly Demuth random if and only if it is Martin-Lof random and cannot compute a strongly prompt r.e. set. We conclude with a study of related lowness notions and obtain as a corollary that lowness for balanced randomness is equivalent to being recursive.
Abstract: We study computably enumerable equivalence relations (ceers)
under the computable reducibility R ≤ S if there exists a computable function f such that, for every x,y, x R y if and only if f(x) S f(y). We show that the induced degrees of ceers under ≤ form a bounded poset that is neither a lower semilattice, nor an upper semilattice, and its first order
theory is undecidable. We then study the universal ceers. We show that the uniformly effectively inseparable ceers are universal, but there are effectively inseparable ceers that are not universal. We show that a ceer R is universal if and only if R' ≤ R, where R' denotes the halting jump operator introduced by Gao and Gerdes (answering an open question of Gao and Gerdes). Finally we show that both the index set of the universal ceers and the index set of the uniformly effectively inseparable ceers are Σ^{0}_{3}-complete.
Theoretical Computer Science (2012), 460C, pp. 1-9. doi:10.1016/j.tcs.2012.06.004.
Abstract: We explore the lowness notions associated with bounded (in terms of cardinality) notions of randomness. While these bounded notions seem far from classical notions with infinite tests like Martin-Lof and Demuth randomness, the lowness notions associated with bounded randomness turn out to be intertwined with the lowness notions for these two concepts (via K-triviality and BLR-traceability). We show that lowness for finitely bounded randomness coincides with K-triviality, while lowness for computably bounded randomness lies between being hyperimmune-free and faithfully BLR-traceable, and being hyperimmune-free.
Abstract: We show that if a point in a computable probability space X satisfies the ergodic recurrence property for a computable measure-preserving transformation
T : X → X with respect to effectively closed sets, then it also satisfies Birkhoff's ergodic theorem for T with respect to effectively closed sets. As a corollary, every Martin-Lof random sequence in the Cantor space satisfies Birkhoff's ergodic theorem for the shift operator with respect to effectively closed sets. This answers a question of Hoyrup and Rojas.
Journal of Symbolic Logic (2011), 76(4), pp. 1287-1296.
Abstract:
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 Δ^{0}_{2} set B >_{tt} 0' such that there is no c.e. set A with A' ≡_{wtt} B. We also show that there is a Σ^{0}_{2} set C >_{tt} 0' such that there is no Δ^{0}_{2} set D with D' ≡_{wtt} C.
Proceedings of the American Mathematical Society (2011), 139, pp. 345-360.
Abstract:
In this paper, we define new notions of randomness based on the difference hierarchy. We consider various ways in which a real can avoid all effectively given tests consisting of n-r.e. sets for some given n. In each case, the n-r.e. randomness hierarchy collapses for n ≥ 2. In one case, we call the resulting notion difference randomness and show that it results in a class of random reals that is a strict subclass of the Martin-Lof random reals and a proper superclass of both the Demuth random and weakly 2-random reals. In particular, we are able to characterize the difference random reals as the Turing incomplete Martin-Lof random reals. We also provide a martingale characterization for difference randomness.
Journal of Symbolic Logic (2011), 76(3), pp. 946-972.
Abstract:
We introduce a natural strengthening of prompt simplicity, and study its relationship with existing lowness classes. We show that this notion is intimately related to superlow cuppability. We also study the effect that lowness properties have on the behaviour of a set under the join operator. In particular we construct an array noncomputable c.e. set, whose join with every low c.e. set is low.
Journal of Symbolic Logic (2011), 76(2), pp. 491-518.
Abstract:
We study inversions of the jump operator on Π^{0}_{1} classes, combined with certain basis theorems. These jump inversions have implications for the study of the jump operator on the random degrees for various notions of randomness. For example, we characterize the jumps of the weakly 2-random
sets which are not 2-random, and the jumps of the weakly 1-random relative to 0' sets which are not 2-random. Both of the classes coincide with the degrees above 0' which are not 0'-dominated. We also show that one direction of van Lambalgen's theorem holds for weak 2-randomness, while the other fails. Finally we discuss various techniques for coding information into incomplete randoms. Using these techniques we show that not all weakly 2-random sets are array computable.
Proceedings of the London Mathematical Society (2011), 102(3), pp. 423-467.
Abstract:
Strong jump traceability has been studied by various authors. In this paper we study a variant of strong jump traceability by looking at a partial relativization of strong jump traceability. We discover a new subclass H of the c.e. K-trivials with some interesting properties. These sets are computationally very weak, but yet contains a cuppable member. Surprisingly they cannot be constructed directly using cost functions, and is the first known example of a subclass of the K-trivials which does not contain any promptly simple member. Furthermore there is a single c.e. set which caps every member of H, demonstrating that they are in fact very far away from being promptly simple.
Notre Dame Journal of Formal Logic (2010), 51(2), pp. 279-290.
Abstract:
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 ≤_{T} 0'' which is hyperimmune-free and not c.e. traceable, such that every real α ≤_{T} A has effective packing dimension 0. We also construct a set B ≤_{T} 0' with the same properties.
Journal of Symbolic Logic (2010), 75(1), pp. 387-400.
Abstract:
We prove a number of results in effective randomness, using methods in which Π^{0}_{1} classes play an essential role. 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.
Notre Dame Journal of Formal Logic (2009), 50(4), pp. 469-493.
Abstract:
Semi-hyperhypersimple c.e. sets, also known as diagonals, were introduced by Kummer. He showed that by considering an analogue of hyper-hypersimplicity, one could characterize the sets which are the Halting problem relative to arbitrary computable numberings. One could also consider half of splittings of maximal or hyperhypersimple sets and get another variant of maximality and hyperhypersimplicity, which are closely related to the study of automorphisms of the c.e. sets. We investigate the Turing degrees of these classes of c.e. sets. In particular, we show that the analogue of a theorem of Martin fails for these classes.
Annals of Pure and Applied Logic (2008), 154, pp. 51-69.
Abstract:
In this paper we show that there is no minimal bound for jump traceability. In particular, there is no single order function such that strong jump traceability is equivalent to jump traceability for that order. The uniformity of the proof method allows us to adapt the technique to show that the index set of the c.e. strongly jump traceable sets is Π^{0}_{4}-complete.
Journal of Symbolic Logic (2008), 73(1), pp. 309-342.
Abstract:
In this paper we show that there is a pair of superhigh r.e. degrees that form a minimal pair. An analysis of the proof shows that a critical ingredient is the growth rates of certain order functions. This leads us to investigate certain high r.e. degrees, which resemble 0' very closely in terms of 0'-jump traceability. In particular, we will construct an ultrahigh degree which is half of a minimal pair.
Abstract:
This paper continues the study of weakly homogeneous structures. It is shown that a countable Boolean algebra is weakly homogeneous if and only if it has finitely many atoms. Hence every countable weakly homogeneous Boolean algebra has a computable copy, and a computable Boolean algebra is weakly homogeneous if and only if it is computably categorical. We also characterize countable weakly homogeneous Boolean algebras in various signatures. The countable weakly homogeneous abelian p-groups are characterized, and it is shown that every such group has a computable copy.
Proceedings of the 13th Asian Logic Conference (2015), pp. 1-29.
Abstract: We develop an analogy between cardinal characteristics from set theory and highness properties from computability theory, which specify a sense in which a Turing oracle is computationally strong. We focus on characteristics from Cichon's diagram.
Proceedings of the 13th Asian Logic Conference (2015), pp. 53-68.
Abstract: In this paper we construct a pair of r.e. sets A and B such that the truth-table degrees of A and B form a minimal pair, and where A ≥_{wtt} 0' and B ≥_{T} 0'.
Proceedings of the 12th Asian Logic Conference (2012), pp. 271-284. doi:10.1142/9789814449274_0015
Abstract: We explore the computational strength of the hyperimmune-free Turing degrees. We construct an uncountable effectively closed set where every path is hyperimmune-free and generalized low. We also show that only a computable set can be simultaneously hyperimmune-free and hyperimmune-free relative to the Halting problem. Finally we show that for every 2-generic degree c , there is a hyperimmune-free degree a such that a' = c ∪ 0' .
M.J. Dinneen et al. (Eds.): Workshop on Theoretical Computer Science 2012 (Calude Festschrift), LNCS 7160, pp. 59--70. Springer, Heidelberg (2012)
Abstract: We introduce two notions of randomness weaker than Martin-Lof randomness. We call them finitely bounded (FB) randomness and computably bounded (CB) randomness. These notions of randomness are obtained by restricting the cardinality of Martin-Lof tests to being finite and computably bounded respectively. We prove that amongst the Δ^{0}_{2} reals, FB-randomness coincides with Martin-lof randomness, but that in general the former notion is strictly weaker than Marint-Lof randomness. We also show characterize the r.e. degrees computing a CB-random real as precisely the non-totally ω-c.a. degrees.
Abstract:
Consider a Martin-Lof random Δ^{0}_{2} set Z. We give lower bounds for the number of changes of the first n bits of Z_{s} for computable approximations of Z. We show that each nonempty Π^{0}_{1} class has a low member Z with a computable approximation that changes only o(2^{n}) times. We prove that each superlow ML-random set already satisfies a stronger randomness notion called balanced randomness, which implies that for each computable approximation and each constant c, there are infinitely many n such that the first n bits of Z_{s} changes more than c2^{n} times.
Proceedings of "Second Conference on Computability in Europe", CiE 2006, Swansea (2006), pp. 413-422.
Abstract:
In this paper we show that there is some Δ^{0}_{2} set such that every non-recursive degree below it contains no weakly computable real. We also show that given any r.e. degree a, every real computed by a is weakly computable if and only if a is array recursive.
Computational prospects of infinity. Part II. Presented talks, 207--223, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., 15, World Sci. Publ., Hackensack, NJ, 2008.
Abstract:
We will provide a proof for the conjecture put forward by Nies, that there is a cuppable, non-bounding r.e. degree. This implies that the ideals generated by the non-bounding and/or noncuppable degrees are new, and different from the known ones.