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.
We study the degree structure of the ω-r.e., n-r.e. and Π01equivalence 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 Π01equivalence relations. We prove that for all the degree classes considered, upward density holds and downward density fails.
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 Δ02degree. We finally consider downward density
for these classes, and give some further directions for research.
We prove that c.c. torsion abelian groups can be described by a Π04-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 Π04-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.
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 high2 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.
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.
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.
Memoirs of the American Mathematical Society. To appear.
We prove that there is a Δ02set 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.
Journal of Mathematical Logic, (2017), 17, 1750008.
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.
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  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).
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.
Theoretical Computer Science (2017), 674, pp. 73–98.
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.
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.
Annals of Pure and Applied Logic (2016), 167(11), pp.1123-1138.
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 Δ02-categoricity. We partially reduce the description of Δ02-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 Δ02-categoricity that lies strictly in-between plain Δ02-categoricity and relative Δ02-categoricity (to be defined). We then reduce the problem of classifying effective Δ02-categoricity to a question stated in terms of Δ02-sets. Among other results, we show that for c.e. Turing degrees bounding such sets is equal to being complete.
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 KA(n)/K(n) is 1.
We show that there is a perfect Π01-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 nc, for any c > 0.
Journal of Symbolic Logic (2016), 81(4), pp. 1225-1254.
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
Π0n+2-complete under computable reducibility, we show that, for every n, there does exist a natural equivalence relation which is
Π0n+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.
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.
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 Π01-complete equivalence relation, but no Π0k-complete for k>1. We show that many Σ0k preorderings arising naturally in the above-mentioned areas are in fact Σ0k-complete. This includes polynomial time m-reducibility on exponential time sets, which is Σ02, almost inclusion on r.e. sets, which is Σ03, and Turing reducibility on r.e. sets, which is Σ04.
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.
Conference: 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' .
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 kth 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 Σ03-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.
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 Δ02 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: 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.
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 Δ02 set B >tt 0' such that there is no c.e. set A with A' ≡wtt B. We also show that there is a Σ02 set C >tt 0' such that there is no Δ02 set D with D' ≡wtt C.
Proceedings of the American Mathematical Society (2011), 139, pp. 345-360.
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.
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.
We study inversions of the jump operator on Π01 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.
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.
Conference: Computability in Europe 2010, pp. 162-171.
Journal: Journal of Logic and Computation (2015), 25(4), pp 1073-1089. doi:10.1093/logcom/exs083
Consider a Martin-Lof random Δ02 set Z. We give lower bounds for the number of changes of the first n bits of Zs for computable approximations of Z. We show that each nonempty Π01 class has a low member Z with a computable approximation that changes only o(2n) 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 Zs changes more than c2n times.
Notre Dame Journal of Formal Logic (2010), 51(2), pp. 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 ≤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.
We prove a number of results in effective randomness, using methods in which Π01 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.
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.
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 Π04-complete.
Journal of Symbolic Logic (2008), 73(1), pp. 309-342.
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.
Proceedings of "Second Conference on Computability in Europe", CiE 2006, Swansea (2006), pp. 413-422.
In this paper we show that there is some Δ02 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.
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.
Papers in preparation
Cupping Ahmad pairs (with Iskander Kalimullin, Steffen Lempp and Mars Yamaleev).
On one point extension in the &Sigma02 enumeration degrees (with Uri Andrews, Steffen Lempp and Andrea Sorbi).
Contiguity and strong contiguity (with Mars Yamaleev).