Abstract:
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.
Abstract:
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 M3 and N5, with the non-zero elements of each lattice in the same Turing degree, in the computably enumerable Q degrees.
Abstract:
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).
Abstract:
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 RT22 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 RTn∞ which take as input a colouring of n-tuples which has some infinite homogeneous set and asks for any such set. The problem RT1∞ is fairly well-studied, as it is Weihrauch equivalent to the cluster point problem on ℕ. Our main result shows that RT1∞ is not Weihrauch reducible to RT2ℕ, strengthening a result of Solda, Valenti. We also
show that the jump of RT1∞ is Weihrauch equivalent to SRT2∞.
Abstract:
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 Δ02-categorical equialence structures and linear orders, relatively Δ03-categorical Boolean algebras, and computably categorical trees as partial orders.
Abstract:
For the notion of degree of categoricity, we study an analogous notion for punctual structures. We show that such notions coincide for non-Δ01-categorical injection structures, and construct an example of a Δ01-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.
Abstract:
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, ω2, ω + ω*, ζ, 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. Among the notable differences, the structure P(ζ) contains degrees with a minimal cover which is not a strong minimal cover, a phenomenon that does not occur in P(ω).
Abstract:
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 Δ04 categorical and determine exactly which ones are (uniformly) relatively Δ03 categorical.
We also provide a classification for sp-homogeneity and weak sp-homogeneity. We establish that this is the best possible classification by showing that the set of sp-homogeneous linear orderings is Π05-complete and that the set of weakly sp-homogeneous linear orderings is Σ06-complete. This result is obtained in two different ways, one using a hands-on computability theoretic approach and another using more abstract descriptive set theory.
In understanding the categoricity and classification of sp-homogeneous orderings, we define a sequence of strong homogeneity notions that approximate sp-homogeneity called Cn,m-homogeneity. For finite values of n,m there are only finitely many Cn,m-homogeneous orderings, and these are very closely related to the homogeneous colored linear orderings with
finitely many colors. We provide an analytic-combinatorial analysis of the number of Cn,m-homogeneous orderings and the number of homogeneous colored linear orderings with k colors, resulting in precise asymptotic bounds for these sequences.
Abstract:
We give a suffcient 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.
Abstract:
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.
Abstract:
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.
Abstract:
In this article, we investigate the degree structures of various functions 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.
Abstract:
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.
Abstract:
Reverse mathematics is primarily interested in what set existence axioms are necessary and sufficient in a proof of a theorem. Much work has been done in classifying graph colouring theorems, studying k-regular graphs, k-chromatic graphs and forests. 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 WKL0. Further analysis of related principles, obtained by restricting the planar graphs in question to be connected, or with computable planar drawings also yield 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.
Abstract:
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.
Abstract: 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 T0-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. Note that none of these results assume that the Polish (or T0) spaces are effective. Quite surprisingly, the effectively compact topological presentations turn out to be rather well behaved. Not only do such presentations allow one to construct a Δ02 (complete) metric compatible with the topology, but also, under a mild extra condition, they can be turned into a computably compact Polish presentation of the space.
Abstract:
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 (that is, the realizability subtoposes of the effective topos) form a
dense non-modular (thus, non-distributive) lattice. We also show that there is a nonzero join-irreducible subTuring degree (which implies that there is a realizability subtopos of the effective topos that cannot be decomposed into two smaller realizability subtoposes).
Abstract:
We prove that there exists a left-c.e. Polish space not homeomorphic to any right-c.e. space. Combined with some 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 employ our techniques to provide a new, relatively straightforward construction of a computable Polish space K not homeomorphic to any computably compact space. We also show that the Banach space C(K;R) has a computable Banach copy; this gives a negative answer to a question raised by McNicholl. We also give an example of a space that has both a left-c.e. and a right-c.e. presentation, yet it is not homeomorphic to any computable Polish space. In addition, we provide an example of a Δ02 Polish space that lacks both a left-c.e. and a right-c.e. copy, up to homeomorphism.
Memoirs of the American Mathematical Society. Accepted.
Abstract:
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 T0-space (e.g. the ω-power of the Sierpinski space). Hence, every
represented second-countable T0-space determines a collection of enumeration degrees.
For instance, Cantor space captures the total degrees, and the Hilbert cube captures
the continuous degrees by definition. 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.
Annals of Pure and Applied Logic, (2026), 177(5), 103720.
Abstract:
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, one of which orders mathematical problems by the richness of the truth-tables determining how discontinuous steps influence the output.
Abstract:
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.
Annals of Pure and Applied Logic (2025), 176(9), 103616.
Abstract:
Answering an open question raised by Cooper, we show that there exist Δ02 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 Σ02 singleton degrees, and the Δ02 singleton degrees, are not dense (and consequently the Π02 Q-degrees, and the Δ02 Q-degrees, are not dense). Moreover D and E can be built to lie in the same enumeration degree.
Abstract:
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 is not dense.
Abstract:
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] of real-valued continuous functions on the unit interval. We prove that the classification problem for continuous (binary) regular functions among almost everywhere linear, pointwise linear-time Lipshitz functions is Σ02-complete. We show that a function f : [0,1] → ℝ is (binary) transducer if and only if it is continuous regular; interestingly, this peculiar and nontrivial fact was overlooked by experts in automata theory. As one of many consequences, our Σ02-completeness result covers the
class of transducer functions as well. Finally, we show that the Banach space C[0,1] of real-valued
continuous functions admits an arithmetical classification among separable Banach spaces. Our proofs
combine methods of abstract computability theory, automata theory, and functional analysis.
Abstract:
The theory of numberings provides classification results for families of sets in various computability-theoretic hierarchies. The algorithmic content of numberings is typically calibrated via the reducibility between numberings. For a given family of sets S, this reducibility gives rise to an upper semilattice of degrees that is often called the Rogers semilattice of S. This paper studies the cardinalities of Rogers semilattices for families of sets at finite levels of the Ershov hierarchy. The classical result of Khutoretskii (1971) shows that the Rogers semilattice of a family of c.e. sets is either one-element or countably infinite. Badaev and Lempp (2009) constructed a family of d.c.e. sets that demonstrates that the methods of Khutoretskii cannot
be applied to obtain a similar result for Rogers semilattices already at the second level 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. We also obtain another sufficient condition for a Rogers semilattice to be infinite. This condition implies that the Rogers semilattice of Badaev and Lempp is also infinite.
Proceedings of the American Mathematical Society, (2025), 153, pp. 4447-4462.
Abstract:
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.
Journal of Symbolic Logic (2025), 90(1), pp. 188-220.
Abstract:
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.
Journal of Symbolic Logic (2025), 90(3), pp. 1261-1276.
Abstract:
Let K denote prefix-free Kolmogorov Complexity, and KA denote
it relative to an oracle A. We show that for any n, K0(n)
is definable purely in terms of the unrelativized notion K. It was already known that 2-randomness
is definable in terms of K (and plain complexity C) as those reals which infinitely
often have maximal complexity. We can use our characterization to show
that n-randomness is definable purely in terms of K. To do this we extend
a certain "limsup" formula from the literature, and apply Symmetry of Information.
This extension entails a novel use of semilow sets, and a more precise
analysis of the complexity of Δ02sets of mimimal descriptions.
Archive for Mathematical Logic (2025), 64, pp. 159 184.
Abstract:
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. Finally we characterise the Boolean algebras which have a punctually 1-decidable presentation that is computably isomorphic to each 1-decidable presentation.
Computably and punctually universal spaces
(with Ramil Bagaviev, Ilnur Batyrshin, Nikolay Bazhenov, Dmitry Bushtets, Marina Dorzhieva, Heer Tern Koh, Ruslan Kornev and Alexander Melnikov).
Annals of Pure and Applied Logic (2025), 176(1), 103491.
Abstract:
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 prove that the original Urysohn's construction of the universal separable
Polish space is punctually universal. We also show that effectively compact, punctual Stone spaces are punctually homeomorphically embeddable into Cantor
space; note that we do not require effective compactness be primitive recursive. We also prove that effective compactness cannot be dropped from the premises by constructing a counterexample.
Proceedings of the American Mathematical Society (2024), 152, pp. 3123-3136.
Abstract:
We show that every Δ02 Polish space admits a computable topological presentation given by an effective indexing of some non-empty open sets in the space
Journal of Symbolic Logic (2024), 89(3), pp. 1370 - 1395.
Abstract:
We study for each computably bounded Π01class 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 Π01class where all c.e. members have degree a. We
also show that every Σ03 set of c.e. indices is realized in some perfect Π01class,
and classify the sets of c.e. degrees which can be realized in some Π01class as
exactly those with a computable representation.
Journal of Symbolic Logic (2024), 89(3), pp. 1358-1369.
Abstract:
Working towards showing the decidability of the ∀∃-theory of the
Σ02-enumeration degrees, we prove that no so-called Ahmad pair of Σ02-enumeration degrees can join to 0'e.
Journal of Symbolic Logic (2024), 89(4), pp. 1768 - 1797.
Abstract:
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 A0 ⊔ A1 = A splitting A with A0 and A1
both totally ω2-c.a. in terms of the Downey-Greenberg hierarchy. We also show that if cone
avoidance is added then there is no level below ε0 which can be used to characterize the
complexity of A0 and A1 .
Mathematical Structures in Computer Science (2023), 33(9), pp. 781-808.
Abstract: 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. Specifically we focus our attention on computable u-soft and computable p-soft separation axioms and investigate various relations between them. We also compare the effective and classical versions of these soft separation axioms.
International Journal of Algebra and Computation (2023), 33(8), pp. 1687-1711.
Abstract:
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.
Journal of Logic and Computation (2023), 33(5), pp 1060 1088.
Abstract:
We consider three strong reducibilities, s1, s2, Q1 (where we identify a reducibility ≤r with its index r), for which (with proper inclusions) we have s1 ⊂ s2 ⊂ s (s denotes s-reducibility),
and Q1 ⊂ 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 s1 and Q1. We show that there is a minimal Δ02s2-degree, but the nonzero Π01s2-degrees are downwards dense; and there exists a minimal Π01s1-degree (and thus a minimal c.e. Q1-degree; every such one must contain a hypersimple set but no hyperhypersimple set).
Abstract:
In her 1990 thesis, Ahmad showed that there is a so-called "Ahmad pair", i.e., there are incomparable Σ02 enumeration degrees a0 and a1 such
that every enumeration degree x < a0 is ≤ a1. At the same time, she also
showed that there is no symmetric Ahmad pair, i.e., there are no incomparable Σ02 enumeration degrees a0 and a1 such that every enumeration degree
x0 < a0 is ≤ a1 and such that every enumeration degree x1 < a1 is ≤ a0.
In this paper, we first present a direct proof of Ahmad's second result. We then show that her first result cannot be extended to an "Ahmad triple", i.e., there are no Σ02 enumeration degrees a0, a1 and a2 such that both (a0, a1)
and (a1, a2) are an Ahmad pair. On the other hand, there is a "weak Ahmad triple", i.e., there are pairwise incomparable Σ02 enumeration degrees a0, a1 and a2 such that every enumeration degree x < a0 is also ≤ a1 or ≤ a2;
however neither (a0, a1) nor (a0, a2) is an Ahmad pair.
Abstract:
The complexity of equivalence relations has received much attention in the recent literature. The main tool for such endeavour is the following reducibility: given equivalence relations R and S on natural numbers, R is computably reducible to S if there is a computable function f : ω → ω that induces an injective map from R-equivalence classes to S-equivalence classes. In order to compare the complexity of R-equivalence relations which are computable, researchers considered also feasible variants of computable reducibility,
such as the polynomial-time reducibility. In this work, we explore Peq, the degree structure generated by primitive recursive reducibility on punctual equivalence relations (i.e., primitive recursive equivalence relations with domain ω). In contrast with all other known degree structures on equivalence relations, we show that Peq has much more structure: e.g., we show that
it is a dense distributive lattice. On the other hand, we also other evidence of the intricacy of Peq, proving, e.g., that the structure is neither rigid nor homogeneous.
Journal of Mathematical Logic (2022), 22(3), 2250022.
Abstract:
A strong degree of categoricity is a Turing degree d such that there is a computable structure 𝒜 that is d-computably categorical (there is a d-computable isomorphism between any two computable copies of 𝒜), and such that there exist two computable copies of 𝒜 between which every isomorphism computes d. The question of whether every Δ02 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, by constructing an example.
Annals of Pure and Applied Logic (2022), 173(7), 103134.
Abstract:
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 α≤ ε0 which is a power of ω, there is a Δ02Turing degree which is weakly α-change generic, but not α-change generic.
Israel Journal of Mathematics (2022), 250, pp. 1-51.
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 give several theorems concerning the strength required to compute multiply generic degrees, and show that some of the levels in the hierarchy can be separated, and
that these separations can be witnessed by a Δ02degree. Finally, we consider
downward density for these classes.
Journal of Logic and Computation (2021), 31(7), pp. 1660 1689.
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 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 Δ02sets.
Logical Methods in Computer Science (2021), 17(3), pp. 6:1 6:35.
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.
Lobachevskii Journal of Mathematics (2021), 42(4), pp. 693-700.
Abstract:
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.
Journal of Symbolic Logic (2020), 85(4), pp. 1427-1466.
Abstract:
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 it tight. We also construct an example of a punctually categorical structure whose degree of categoricity is 0''. We also prove that, with a bit of work, the latter result can be pushed beyond Δ11, thus showing that punctually categorical structures can posses arbitrarily complex automorphism orbits.
As a consequence, it follows that binary relational structures and unary structures are not universal with respect to primitive recursive interpretations; equivalently, in these classes every rich enough interpretation technique must necessarily involve unbounded existential quantification or infinite disjunction. In contrast, it is well-known that both classes are universal for Turing computability.
Journal of Symbolic Logic (2020), 85(4), pp. 1664-1686.
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 Δ02 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.
Journal of Symbolic Logic (2020), 85(4), pp. 1499-1545.
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 low3-cuppable, or
indeed lown 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 low2-cuppable degrees coincide with the array computable-cuppable
degrees, giving a full understanding of the latter class.
Theoretical Computer Science (2020), 844, pp. 195-216.
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).
Proceedings of the American Mathematical Society (2020), 148, pp. 3113-3128.
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.
Journal of Symbolic Logic (2020), 85(2), pp. 605-623.
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.
Archive for Mathematical Logic (2020), 59, pp. 777-791.
Abstract:
We show that for every intermediate Σ02s-degree (i.e. a nonzero s-degree strictly below the s-degree of the complement of the halting set) there exists an incomparable Π01s-degree. (The same proof yields a similar result for other positive reducibilities as well, including enumeration reducibility.) As a consequence, for every intermediate Π02Q-degree (i.e. a nonzero Q-degree strictly below the Q-degree of the halting set) there exists an incomparable Σ01Q-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.
Notre Dame Journal of Formal Logic (2020), 61(2), pp. 203-225.
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 (2020), 265(1284), pp. 1-104.
Abstract:
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 (2020), 21(1), 2050021.
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 Π01 automorphism. We also construct a strongly η-like linear order where every block has size at most 4 with no rational subinterval such that every Δ02 isomorphic computable copy has a nontrivial Π01 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 Σ11-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 Π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.
Abstract:
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.
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 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.
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 Δ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.
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
Π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.
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 Δ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.
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 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.
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 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.
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 Δ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.
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 Π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.
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 Π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.
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 Π04-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:
The current work includes a result announced in the year 2012 which was unproven until now. 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.
Aspects of Computation and Automata Theory with Applications (2024), 42, pp. 141-158.
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 Δ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:
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.
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 Δ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.
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.