Publications

The hydrophobic polar lattice model captures in a minimal representation the hydrophobic driving force contribution to protein folding. Starting with the limiting case of an all-hydrophobic homopolymer, in which every non-consecutive nearest-neighbor pair contributes a hydrophobic contact, we derive closed-form expressions for the exact maximum number of contacts. On the 2D square-lattice the Harary-Harborth perimeter minimization gives a formula for the maximum number of contacts equal to, whereas the Alonso-Cerf minimum-surface formula together with a traceable minimizing construction gives the exact expression for the maximum contact number on the 3D cubic-lattice. At completed lengths, GPU enumeration recovers these optima and identifies heterogeneous HP sequences that preserve them, minimizing the number of H. We use to normalize HP-like contact readouts from experimental traces and cubic mappings, revealing low but dispersed compactness relative to the allhydrophobic benchmark.

The hydrophobic polar lattice model captures in a minimal representation the hydrophobic driving force contribution to protein folding. Starting with the limiting case of an all-hydrophobic homopolymer, in which every non-consecutive nearest-neighbor pair contributes a hydrophobic contact, we derive closed-form expressions for the exact maximum number of contacts. On the 2D square-lattice the Harary-Harborth perimeter minimization gives a formula for the maximum number of contacts equal to n + 1 − ⌈2√n⌉, whereas the Alonso-Cerf minimum-surface formula together with a traceable minimizing construction gives the exact expression for the maximum contact number U₃(n) = 2n + 1 − A_min(n)/2 on the 3D cubic-lattice. At completed lengths, GPU enumeration recovers these optima and identifies heterogeneous HP sequences that preserve them, minimizing the number of H. We use U₃(n) to normalize HP-like contact readouts from experimental C_α traces and cubic mappings, revealing low but dispersed compactness relative to the all-hydrophobic benchmark.

In this paper, we prove that every effectively locally connected computably compact space has infinitely many pairwise computably non-homeomorphic computably compact presentations. As a consequence, most familiar compacta in the literature, including, for example, compact manifolds, have “infinite homeomorphic autodimension.”

In this article, we analyse the uniform computational content of categoricity problems, showing relationships between the complexity of Scott families and their Weihrauch degrees. We give upper bounds for some classes of linear orders and Boolean algebras, and show in some cases that these are sharp. We also explore the question of which Weihrauch degrees are realizable as categoricity problems, and show that no Weihrauch degree between LLPO and WKL are realizable. In this article, we also explore the poset of Weihrauch degrees of categoricity problems of computable structures, showing that it is closed with respect to product and parallelization, and that there exists a greatest degree in this poset. In contrast, we show that there is no single structure whose categoricity problem bounds all other categoricity problems. This motivates the introduction of the categoricity problems of classes of structures, which we study in relation to other notions of universality in the literature.

Motivated by the problem of understanding small fragments of the first-order theory of the degree structure of the computably enumerable equivalence relations (ceers), we study which finite partial orders and lattices occur as initial segments of the ceer degrees above the finite degrees. We prove that the following structures are isomorphic to initial segments of Ceers ∖ Fin (and, in fact, can be realized inside the light ceers above deg(Id)): (1) every finite distributive lattice, (2) the five-element nondistributive lattices N₅ and M₃, and (3) the bounded six-element partial order P₆, which is neither an upper nor a lower semilattice.

We investigate the relationship between ≤_Q and ≤_T on the computably enumerable sets by asking what kind of lattices can be embedded in the computably enumerable Q degrees with elements of the lattice in the same Turing degree. We will use a pinball machine to show that the diamond lattice can be embedded in the computably enumerable Q degrees, with all elements of the lattice in the same Turing degree.

Downey, LaForte, and Nies constructed a minimal pair in the computably enumerable Q degrees that are in the same Turing degree. That is, there exists a zero-preserving embedding of the diamond, with the non-zero elements in the same Turing degree into the computably enumerable Q degrees. We extend their result by showing that there exists a zero-preserving embedding of the two non-distributive lattices M₃ and N₅, with the non-zero elements of each lattice in the same Turing degree, in the computably enumerable Q degrees.

In this paper we introduce the notion of topological computable categoricity for a Polish space. We show that, in contrast to computable structures, homogeneous Polish spaces tend not to be computably categorical. In particular, the infinite countable discrete space, the Baire space, and the Hilbert cube are all not topologically computably categorical. We also show that spaces which are computably compact or have a presentation with a computable base of open sets similarly fail to be topologically computably categorical. Finally, we investigate the degrees of categoricity for the Baire space and the closed unit interval (the arc).

We study the primitive recursive analogue of computable categoricity spectra for various natural classes of structures. We show that these notions coincide for all relatively Δ⁰₂-categorical equivalence structures and linear orders, relatively Δ⁰₃-categorical Boolean algebras, and computably categorical trees as partial orders.

This article explores computable reducibility for the representations of computable linear orders. In particular, this paper investigates the degree structures P(L) consisting of the c-degrees of computable copies of a fixed linear order L, where L is one of the following: ω·k, ω², ω + ω*, ζ, or ω·η. The main objective is to identify structural differences between these posets, focusing on the existence of least degrees, minimal degrees, universal degrees, minimal covers, and the possible number of such covers.

We study linear orderings expanded by functions for successor and predecessor. In particular, the sp-homogeneous and weakly sp-homogeneous linear orderings are those which are homogeneous or weakly homogeneous with this additional structure. We demonstrate that these orderings are always relatively Δ⁰₄ categorical and determine exactly which ones are (uniformly) relatively Δ⁰₃ categorical. We also provide a classification for sp-homogeneity and weak sp-homogeneity, establishing that the set of sp-homogeneous linear orderings is Π⁰₅-complete and that the set of weakly sp-homogeneous linear orderings is Σ⁰₆-complete.

We give a sufficient condition for a computable metric space to have a primitive recursive presentation upon a dense set with no repetition; we call such presentations "punctual". As a consequence, every perfect compact space can be computably turned into a punctual one. To prove this result, we also establish that every compact computable space is computably homeomorphic to one in which the distances between special points are pairwise rational, and furthermore represented as fractions.

In this article, we investigate the degree structures of various hyperspaces. One of our goals is to gain a topological understanding of higher-type computability using negative information, and to this end, we explore the degree structures of function spaces whose ground types are endowed with cofinite topology or its relatives.

In this article, we investigate the degree structures of various function spaces. One of our goals is to gain a topological understanding of higher-type computability using negative information, and to this end, we explore the degree structures of function spaces whose ground types are endowed with cofinite topology or its relatives.

In the first part of this paper, we will prove a new sufficient condition for a structure to have infinite punctual dimension and then apply it to show several new connections between the punctual dimension of a structure and its punctual degrees. In the second part of this paper, we contribute towards a classification of density of punctual degrees for linear orders by proving that the punctual degrees of ℤ·n, for n > 1, are dense.

We provide a full characterisation of which equivalence relations have a dense punctual degree structure.

We prove that every finite distributive lattice is isomorphic to a final segment of the d.c.e. Turing degrees.

The relation "being primitively recursively isomorphic" is a reduction (a pre-order) rather than an equivalence relation between presentations of an algebraic structure. It leads to the definition of punctual degrees of a given algebraic structure. We show that the punctual degrees PR(ℚ) of the order of the rationals are not dense.

In this article we study the notion of completeness for conjunctive reducibilities. We investigate the relationship between c-completeness and r-completeness of computably enumerable (c.e.) sets with respect to various strong reducibilities ≤_r. By using simplicity properties of sets, we prove that there exist c.e. sets that are simultaneously Q-complete and bd-complete, yet fail to be c-complete. Similarly, there exist c.e. sets that are simultaneously Q-complete and bwtt-complete (respectively, btt-complete) but not c-complete. Furthermore, we study two restrictions of c-reducibility, namely c₁- and c_1,N-reducibility, and show that they are distinct on the c.e. sets. Nevertheless, we prove that the notions of completeness for c, c₁, and c_1,N coincide.

We study the uniform computational content of Ramsey's theorem using both Weihrauch reducibility and a new variant of Weihrauch reducibility, where the functions in the reduction are required to be total. In the latter setting, we show that the strength of Ramsey's theorem varies significantly depending on how one represents its solutions, for example, using characteristic functions or using enumerations. Some of our results extend beyond variants of Ramsey's theorem. In particular, we show that RT²₂ where solutions are represented using characteristic functions is not totally Weihrauch reducible to any computational problem whose solutions are represented using enumerations. Next, we study the computational problems RTⁿ_∞ which take as input a colouring of n-tuples which has some infinite homogeneous set and asks for any such set. The problem RT¹_∞ is fairly well-studied, as it is Weihrauch equivalent to the cluster point problem on ℕ. Our main result shows that RT¹_∞ is not Weihrauch reducible to RT²_ℕ, strengthening a result of Soldà, Valenti. We also show that the jump of RT¹_∞ is Weihrauch equivalent to SRT²_∞.

For the notion of degree of categoricity, we study an analogous notion for punctual structures. We show that such notions coincide for non-Δ⁰₁-categorical injection structures, and construct an example of a Δ⁰₁-categorical injection structure for which these notions differ. Additionally, we also show that in every non-zero c.e. Turing degree, there exists a PR-degree that is low for punctual isomorphism (to be defined), and also a PR-degree that is a degree of punctual categoricity.

Reverse mathematics is primarily interested in what set existence axioms are necessary and sufficient in a proof of a theorem. This paper takes inspiration from an old paper by Bean and studies graph colouring theorems restricted to planar graphs. We show that for any natural number n > 3, the n-colouring theorem for planar graphs is equivalent to WKL₀. Further analysis of related principles yields similar results. However, many of the proofs of equivalence are non-uniform; utilising tools from the study of Weihrauch reducibility, we show that in many instances such non-uniformity is necessary.

The result shows that there is a co-r.e. tree with uncountably many infinite branches such that the nonisolated infinite branches of the constructed tree are all nonrecursive, generalised low, hyperimmune-free and form a perfect tree.

A computable topological presentation of a space is given by an effective list of a countable basis of non-empty open sets so that the intersection of the basic sets is uniformly effectively enumerable. We show that every countably based T₀-space has a computable topological presentation, and that, conversely, every (formal) computable topological presentation represents some Polish space. In the compact case, we give a computable uniform list of computable topological presentations such that every compact Polish space is represented by exactly one presentation from the list.

In this article, we introduce a notion of reducibility for partial functions on the natural numbers, which we call subTuring reducibility. One important aspect is that the subTuring degrees correspond to the structure of the realizability subtoposes of the effective topos. We show that the subTuring degrees form a dense non-modular (thus, non-distributive) lattice. We also show that there is a nonzero join-irreducible subTuring degree.

We prove that there exists a left-c.e. Polish space not homeomorphic to any right-c.e. space. Combined with other recent works, this finishes the task of comparing all classical notions of effective presentability of Polish spaces that frequently occur in the literature up to homeomorphism. We also show that the Banach space C(K;ℝ) has a computable Banach copy, giving a negative answer to a question raised by McNicholl.

The enumeration degrees of sets of natural numbers can be identified with the degrees of difficulty of enumerating neighborhood bases of points in a universal second-countable T₀-space. Hence, every represented second-countable T₀-space determines a collection of enumeration degrees. Based on these observations, we utilize general topology (particularly non-metrizable topology) to establish a classification theory of enumeration degrees of sets of natural numbers.

The Weihrauch degrees are a tool to gauge the computational difficulty of mathematical problems. Often, what makes these problems hard is their discontinuity. We look at discontinuity in its purest form, that is, at otherwise constant functions that make a single discontinuous step along each dimension of their underlying space. This is an extension of previous work of Kihara, Pauly, Westrick from a single dimension to multiple dimensions. Among other results, we obtain strict hierarchies in the Weihrauch degrees.

Extending a result of Zacharov, we show that every nonzero enumeration degree consists of infinitely many s-degrees. In fact we show that there is no minimal s-degree inside any nonzero enumeration degree. This answers open questions in the literature raised by Cooper and Bathyrshin.

Answering an open question raised by Cooper, we show that there exist Δ⁰₂ sets D and E such that the singleton degree of E is a minimal cover of the singleton degree of D. This shows that the Σ⁰₂ singleton degrees, and the Δ⁰₂ singleton degrees, are not dense. Moreover D and E can be built to lie in the same enumeration degree.

In this paper, we work towards a classification of density of punctual degrees for linear orders. More specifically, we construct a discrete linear order whose punctual degrees are not dense.

We develop a systematic algorithmic framework that unites global and local classification problems for functional separable spaces and apply it to attack classification problems concerning the Banach space C[0,1]. We prove that the classification problem for continuous (binary) regular functions among almost everywhere linear, pointwise linear-time Lipshitz functions is Σ⁰₂-complete. We also show that a function f : [0,1] → ℝ is (binary) transducer if and only if it is continuous regular; this peculiar fact was overlooked by experts in automata theory.

The theory of numberings provides classification results for families of sets in various computability-theoretic hierarchies. This paper studies the cardinalities of Rogers semilattices for families of sets at finite levels of the Ershov hierarchy. We prove that for any finite family of sets S at any finite level of the Ershov hierarchy, the corresponding Rogers semilattice is either one-element or countably infinite.

Using a novel technique, we prove that there is a structure that is punctually 1-decidably categorical and is not computably categorical with respect to 1-decidable presentations.

We investigate what it means for a (Hausdorff, second-countable) topological group to be computable. We compare several potential definitions based on classical notions in the literature. We relate these notions with the well-established definitions of effective presentability for discrete and profinite groups, and compare our results with similar results in computable topology.

Let K denote prefix-free Kolmogorov Complexity, and K^A denote it relative to an oracle A. We show that for any n, K⁰⁽ⁿ⁾ is definable purely in terms of the unrelativized notion K. It was already known that 2-randomness is definable in terms of K. We use our characterization to show that n-randomness is definable purely in terms of K.

We investigate the problem of punctual (fully primitive recursive) presentability of algebraic structures up to primitive recursive and computable isomorphism. We show that for mono-unary structures and undirected graphs, if a structure is not punctually categorical then it has infinitely many punctually non-isomorphic punctual presentations. We also show that the punctual degrees of any computably almost rigid structure as well as the order (ℤ, <) are dense.

We prove that the standard computable presentation of the space C[0,1] of continuous real-valued functions on the unit interval is computably and punctually (primitively recursively) universal. From the perspective of modern computability theory, this settles a problem raised by Sierpinski in the 1940s. We also prove that the original Urysohn's construction of the universal separable Polish space is punctually universal.

We show that every Δ⁰₂ Polish space admits a computable topological presentation given by an effective indexing of some non-empty open sets in the space.

We study for each computably bounded Π⁰₁ 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 Π⁰₁ class where all c.e. members have degree a. We also show that every Σ⁰₃ set of c.e. indices is realized in some perfect Π⁰₁ class, and classify the sets of c.e. degrees which can be realized in some Π⁰₁ class as exactly those with a computable representation.

Working towards showing the decidability of the ∀∃-theory of the Σ⁰₂-enumeration degrees, we prove that no so-called Ahmad pair of Σ⁰₂-enumeration degrees can join to 0'_e.

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₀ ⊔ A₁ = A splitting A with both totally ω²-c.a. in terms of the Downey-Greenberg hierarchy.

Soft sets were introduced as a means to study objects that are not defined in an absolute way, and have found applications in numerous areas of mathematics, decision theory and in statistical applications. In this paper we introduce the effective versions of soft separation axioms, focusing on computable u-soft and computable p-soft separation axioms and investigate various relations between them.

We compare and separate several natural notions of effective presentability of a topological space up to homeomorphism. We then apply our techniques to totally disconnected locally compact (tdlc) groups.

We consider three strong reducibilities, s₁, s₂, Q₁, for which (with proper inclusions) we have s₁ ⊂ s₂ ⊂ s (s-reducibility), and Q₁ ⊂ Q (Q-reducibility). We show that there is a minimal Δ⁰₂ s₂-degree, but the nonzero Π⁰₁ s₂-degrees are downwards dense; and there exists a minimal Π⁰₁ s₁-degree (and thus a minimal c.e. Q₁-degree).

In her 1990 thesis, Ahmad showed that there is a so-called "Ahmad pair", i.e., incomparable Σ⁰₂ enumeration degrees a₀ and a₁ such that every enumeration degree x < a₀ is ≤ a₁. She also showed that there is no symmetric Ahmad pair. In this paper, we present a direct proof of Ahmad's second result and show that her first result cannot be extended to an "Ahmad triple".

We explore Peq, the degree structure generated by primitive recursive reducibility on punctual equivalence relations. In contrast with all other known degree structures on equivalence relations, we show that Peq has much more structure: e.g., it is a dense distributive lattice. On the other hand, we also provide other evidence of the intricacy of Peq, proving, e.g., that the structure is neither rigid nor homogeneous.

A strong degree of categoricity is a Turing degree d such that there is a computable structure that is d-computably categorical, and such that there exist two computable copies between which every isomorphism computes d. The question of whether every Δ⁰₂ degree is a strong degree of categoricity has been of interest since the first paper on this subject. We answer the question in the affirmative.

In other work, a transfinite hierarchy of genericity notions stronger than 1-genericity and weaker than 2-genericity was introduced. We close a line of questioning begun there by showing that for every α ≤ ε₀ which is a power of ω, there is a Δ⁰₂ Turing degree which is weakly α-change generic, but not α-change generic.

We introduce a transfinite hierarchy of genericity notions stronger than 1-genericity and weaker than 2-genericity, with many connections to Downey and Greenberg's hierarchy of totally ω-c.a. degrees. We give several theorems concerning the strength required to compute multiply generic degrees, show that some levels in the hierarchy can be separated, and these separations can be witnessed by a Δ⁰₂ degree.

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 Gödel and Kleene. We show that this class of functions can also be characterized by MS-machines, which are Turing machine-like devices. The proof of the characterization gives a normal form theorem in the style of Kleene. Furthermore, this characterization is a natural combination of two most influential theories of computation over real numbers, namely, the type-two theory of effectivity (TTE) and the Blum-Shub-Smale model of computation (BSS). Under this notion of computability, the recursive (or computable) subsets of real numbers are exactly effective Δ⁰₂ sets.

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.

An α-coloring ξ of a structure S is distinguishing if there are no nontrivial automorphisms of S respecting ξ. In this note we prove several results illustrating that computing the distinguishing number of a structure can be very hard in general. In contrast, we show that every computable Boolean algebra has a 0''-computable distinguishing 2-coloring. We also define the notion of a computable distinguishing 2-coloring of a separable space; we apply the new definition to separable Banach spaces.

We describe punctual categoricity in several natural classes, including binary relational structures and mono-unary functional structures. We prove that every punctually categorical structure in a finite unary language is PA(0')-categorical, and we show that this upper bound is tight. We also construct an example of a punctually categorical structure whose degree of categoricity is 0''. As a consequence, it follows that binary relational structures and unary structures are not universal with respect to primitive recursive interpretations.

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 Δ⁰₂ 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.

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₃-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. We also show that the low₂-cuppable degrees coincide with the array computable-cuppable degrees, giving a full understanding of the latter class.

We systematically investigate the online content of finitely generated structures. The online content of an algebraic or combinatorial structure is perhaps best reflected by its FPR-degrees. 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 finitely generated structure with the least and the greatest presentation.

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. We prove that there exists a countable rigid algebraic structure which has exactly two punctual presentations, up to punctual isomorphism.

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.

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.

We show that for every intermediate Σ⁰₂ s-degree there exists an incomparable Π⁰₁ s-degree. As a consequence, for every intermediate Π⁰₂ Q-degree there exists an incomparable Σ⁰₁ Q-degree. We also show how these results can be applied to provide proofs or new proofs of upper density results in local structures of s-degrees and Q-degrees.

We study the relationship between effective domination properties and the bounded jump. We answer two open questions about the bounded jump: (1) the analogue of Sacks' jump inversion fails for the bounded jump and the wtt-reducibility; (2) no c.e. bounded high set can be low — they all must be Turing complete. We characterize the class of c.e. bounded high sets as those sets computing the Halting problem via a reduction with use bounded by an ω-c.e. function.

We prove that there is a Δ⁰₂ 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 — every weak truth table degree contained in a c.e. Turing degree is not minimal with respect to weak truth table degrees.

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. 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.

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 Π⁰₁ automorphism. We also construct a strongly η-like linear order where every block has size at most 4 with no rational subinterval such that every Δ⁰₂ isomorphic computable copy has a nontrivial Π⁰₁ automorphism.

We prove that for every computable limit ordinal α there exists a computable linear ordering ℒ which is Δ⁰_α-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 earlier work of Downey, Igusa, and Melnikov. We also show that such examples can be found among ordered abelian groups and real-closed fields.

A structure is automatic if its domain, functions, and relations are all regular languages. 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 Σ¹₁-complete. We also use similar methods to show that there is no reasonable characterisation of the structures with a polynomial-time presentation.

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 Π⁰₁ 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 prove that for all the degree classes considered, upward density holds and downward density fails.

We prove that c.c. torsion abelian groups can be described by a Π⁰₄-predicate. We show that there is no simpler description since their index set is Π⁰₄-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, confirming a conjecture of Goncharov from the early 1980s for this case.

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, 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₂ c.e. degree can be split in this way.

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 logical depth seeks to capture the idea that a language has a lot of useful information. A question of Moser and Stephan explores whether there is a c.e. low (Bennett) deep language. We answer this question affirmatively, constructing a superlow c.e. Bennett deep language.

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.

We 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 depth-first algorithms with respect to d. We next show that for any balanced multi-branching AND-OR tree, the optimal distributional complexity among all independent distributions is actually achieved by an independent and identical distribution.

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. The class PR_ω of primitive recursive structures upon the domain of ω is the most suitable intermediate notion between computable and polynomial time structures. 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.

We investigate which effectively presented abelian p-groups are isomorphic relative to the halting problem. We partially reduce the description of Δ⁰₂-categorical p-groups of Ulm type 1 to the analogous problem for equivalence structures. We introduce a new notion of effective Δ⁰₂-categoricity that lies strictly in-between plain Δ⁰₂-categoricity and relative Δ⁰₂-categoricity, and show that for c.e. Turing degrees bounding such sets is equal to being complete.

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 Π⁰_n+2-complete under computable reducibility, we show that, for every n, there does exist a natural equivalence relation which is Π⁰_n+2-complete under finitary reducibility. We also refute a possible generalization of Myhill's Theorem.

Working in the Turing degree structure, we show that those degrees which contain computably enumerable sets all satisfy the meet property: if a is c.e. and b < a, then there exists non-zero m < a with b ∩ m = 0. In fact, m may always be chosen to be a minimal degree. This settles a conjecture of Cooper and Epstein from the 80s.

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.

We investigate which computable equivalence structures are isomorphic relative to the Halting problem.

Consider a Martin-Löf random Δ⁰₂ 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 Π⁰₁ class has a low member Z with a computable approximation that changes only o(2ⁿ) times. We prove that each superlow ML-random set already satisfies a stronger randomness notion called balanced randomness.

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. We show that there is a perfect Π⁰₁-class of low for dimension sequences. Finally, we prove that every low for dimension sequence is jump-traceable in order n^c, for any c > 0.

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 specifically, we construct a computable reduced abelian p-group of Ulm type ω having its invariants, limitwise monotonic functions, at the maximal potentially possible level of non-uniformity.

We study the relative complexity of equivalence relations and preorderings from computability theory, complexity theory, and effective descriptive set theory. We show that there is a Π⁰₁-complete equivalence relation, but no Π⁰_k-complete for k > 1. We show that many Σ⁰_k preorderings arising naturally in the above-mentioned areas are Σ⁰_k-complete, including polynomial time m-reducibility on exponential time sets (Σ⁰₂), almost inclusion on r.e. sets (Σ⁰₃), and Turing reducibility on r.e. sets (Σ⁰₄).

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. 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.

We extend previous work on difference randomness. 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-Löf 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.

We study computably enumerable equivalence relations (ceers) under computable reducibility. We show that the induced degrees of ceers form a bounded poset that is neither a lower semilattice, nor an upper semilattice, and its first order theory is undecidable. 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. Finally we show that both the index set of the universal ceers and the index set of the uniformly effectively inseparable ceers are Σ⁰₃-complete.

We explore the lowness notions associated with bounded notions of randomness. 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.

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-Löf random sequence in the Cantor space satisfies Birkhoff's ergodic theorem for the shift operator with respect to effectively closed sets.

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 Δ⁰₂ set B >_tt 0' such that there is no c.e. set A with A' ≡_wtt B. We also show that there is a Σ⁰₂ set C >_tt 0' such that there is no Δ⁰₂ set D with D' ≡_wtt C.

In this paper, we define new notions of randomness based on the difference hierarchy. 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-Löf random reals and a proper superclass of both the Demuth random and weakly 2-random reals. In particular, we characterize the difference random reals as the Turing incomplete Martin-Löf random reals.

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.

We study inversions of the jump operator on Π⁰₁ 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 we show that not all weakly 2-random sets are array computable.

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.

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 prove a number of results in effective randomness, using methods in which Π⁰₁ 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.

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. 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.

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 Π⁰₄-complete.

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.