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.

Answering an open question raised by Cooper, we show that there exist Δ 2 0 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 Σ 2 0 singleton degrees, and the Δ 2 0 singleton degrees, are not dense (and consequently the Π 2 0 Q -degrees, and the Δ 2 0 Q -degrees, are not dense). Moreover D and E can be built to lie in the same enumeration degree.

Abstract Let K denote prefix-free Kolmogorov complexity, and let $K^A$ denote it relative to an oracle A. We show that for any n, $K^{\emptyset ^{(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 $\Delta _2^0$ sets of minimal descriptions.

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.

We develop a systematic algorithmic framework that unites global and local classification problems using index sets. We prove that the classification problem for continuous (binary) regular functions among almost everywhere linear, pointwise linear-time Lipschitz functions is Σ20-complete. (Every regular function is pointwise linear-time Lipschitz.) We show that a function f:[0,1]→R is (binary) transducer if and only if it is continuous regular. As one of many consequences, our Σ20-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.

This paper contributes to a systematic study of punctual structures , which are structures computable without delay. The (punctual) degree structure induced by treating “being primitive recursively isomorphic” as a reduction provides insight into the different speeds of enumerations of a given structure. In this paper, we work towards a classification of density of the punctual degrees for linear orders. More specifically, we construct a discrete linear order whose punctual degrees are not dense.

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

Abstract Working toward showing the decidability of the $\forall \exists $ -theory of the ${\Sigma ^0_2}$ -enumeration degrees, we prove that no so-called Ahmad pair of ${\Sigma ^0_2}$ -enumeration degrees can join to ${\mathbf 0}_e'$ .

Abstract We consider three strong reducibilities, $s_{1}, s_{2}, Q_{1}$ (where we identify a reducibility $\leqslant _r$ with its index $r$). The first two reducibilities can be viewed as injective versions of $s$-reducibility, whereas $Q_1$-reducibility can be viewed as an injective version of $Q$-reducibility. We have, with proper inclusions, $s_{1} \subset s_{2} \subset s$. It is well known that there is no minimal $s$-degree, and there is no minimal $Q$-degree. We show on the contrary that there exist minimal $\varDelta ^{0}_{2}$$s_{2}$-degrees and minimal $\varDelta ^{0}_{2}$$s_{1}$-degrees. On the other hand, both the $\varPi ^{0}_{1}$$s_{2}$-degrees and the $\varPi ^{0}_{1}$$s_{1}$-degrees are downwards dense. By the isomorphism of the $s_1$-degrees with the $Q_1$-degrees induced by complementation of sets, it follows that there exist minimal $\varDelta ^0_2$$Q_1$-degrees, but the c.e. $Q_{1}$-degrees are downwards dense.

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. Soft topological spaces were first considered in Shabir and Naz ((2011). Computers & Mathematics with Applications61 (7) 1786–1799) and soft separation axioms for soft topological spaces were studied in El-Shafei et al. ((2018). Filomat32 (13) 4755–4771), El-Shafei and Al-Shami ((2020). Computational and Applied Mathematics39 (3) 1–17), Al-shami ((2021). Mathematical Problems in Engineering2021). 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.

Abstract The current work includes a result announced in the year 2012 which was unproven for 10 years. 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, and hyperimmune-free and form a perfect tree. This article is the journal version of two conference articles from 2012 and 2022; the article contains the main result proved in 2022 and also the other major results from 2012.

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 an arbitrary complexity. We give a new framework which (i) ties online algorithms with computable analysis, (ii) shows how to use modifications of notions from computable analysis, such as Weihrauch reducibility, to analyse finite but uniform combinatorics, (iii) show how to finitize reverse mathematics to suggest a fine structure of finite analogs of infinite combinatorial problems, and (iv) see how similar ideas can be amalgamated from areas such as EX-learning, computable analysis, distributed computing and the like. One of the key ideas is that online algorithms can be viewed as a sub-area of computable analysis. Conversely, we also get an enrichment of computable analysis from classical online algorithms.

Abstract We define a class of computable functions over real numbers using functional schemes similar to the class of primitive and partial recursive functions defined by Gödel (1931, 1934) and Kleene (1936, Math. Ann., 112, 727–742). 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 (1936, Math. Ann., 112, 727–742). Furthermore, this characterization is a natural combination of two most influential theories of computation over real numbers, namely the type-two theory of effectivity (see, e.g. Weihrauch (2000, Springer)) and the Blum–Shub–Smale (1989, Bull. Amer. Math. Soc. (N.S.), 21, 1–46) model of computation. Under this notion of computability, the recursive (or computable) subsets of real numbers are exactly effective $\varDelta ^0_2$ sets.

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 ${\text {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''$ . We also prove that, with a bit of work, the latter result can be pushed beyond $\Delta ^1_1$ , thus showing that punctually categorical structures can possess 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.

Abstract We characterize the linear order types $\tau $ with the property that given any countable linear order $\mathcal {L}$ , $\tau \cdot \mathcal {L}$ is a computable linear order iff $\mathcal {L}$ is a computable linear order, as exactly the finite nonempty order types.

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 ${\operatorname {\mathrm {low}}}_3$ -cuppable, or indeed ${\operatorname {\mathrm {low}}}_n$ cuppable for anyn, refuting a conjecture by Li. On the other hand, we show that one cannot improve highness to superhighness. We also show that the ${\operatorname {\mathrm {low}}}_2$ -cuppable degrees coincide with the array computable-cuppable degrees, giving a full understanding of the latter class.

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 $\Delta ^0_2$ Polish space not homeomorphic to a computable one. We apply our techniques to build, for any computable ordinal $\alpha $ , an effectively closed set not homeomorphic to any $0^{(\alpha )}$ -computable Polish space; this answers a question of Nies. We also prove analogous results for compact Polish groups and locally path-connected spaces.

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 ${\rm{\Sigma }}_1^1 $ -complete. We also use similar methods to show that there is no reasonable characterisation of the structures with a polynomial-time presentation in the sense of Nerode and Remmel.

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 ${\rm{\Pi }}_{n + 2}^0$ -complete under computable reducibility, we show that, for everyn, there does exist a natural equivalence relation which is ${\rm{\Pi }}_{n + 2}^0$ -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 study the number of changes of the initial segment Zs ↾n for computable approximations of a Martin-Löf random Δ20 set Z. We establish connections between this number of changes and various notions of computability theoretic lowness, as well as the fundamental thesis that, among random sets, randomness is antithetical to computational power. We introduce a new randomness notion, called balanced randomness, which implies that for each computable approximation and each constant c, there are infinitely many n such that Zs ↾n changes more than c2n times. We establish various connections with ω-c.e. tracing and omega;-c.e. jump domination, a new lowness property. We also examine some relationships to randomness theoretic notions of highness, and give applications to the study of (weak) Demuth cuppability.

Abstract We study computably enumerable equivalence relations (ceers), under the reducibility $R \le S$ if there exists a computable function f such that $x\,R\,y$ if and only if $f\left( x \right)\,\,S\,f\left( y \right)$ , for every $x,y$ . We show that the degrees of ceers under the equivalence relation generated by $\le$ 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 1) the uniformly effectively inseparable ceers are universal, but there are effectively inseparable ceers that are not universal; 2) a ceer R is universal if and only if $R\prime \le R$ , where $R\prime$ denotes the halting jump operator introduced by Gao and Gerdes (answering an open question of Gao and Gerdes); and 3) both the index set of the universal ceers and the index set of the uniformly effectively inseparable ceers are ${\rm{\Sigma }}_3^0$ -complete (the former answering an open question of Gao and Gerdes).

for furthering research in logic and the exchange of ideas among mathematicians, computer scientists, linguists, and others interested in this fi eld.

Abstract We study the relative complexity of equivalence relations and preorders from computability theory and complexity theory. Given binary relationsR,S, a componentwise reducibility is defined by R≤S⇔ ∃f∀x, y[x R y↔f(x)S f(y)]. Here,fis taken from a suitable class of effective functions. For us the relations will be on natural numbers, andfmust be computable. We show that there is a ${\rm{\Pi }}_1^0$ -complete equivalence relation, but no ${\rm{\Pi }}_k^0$ -complete fork≥ 2. We show that ${\rm{\Sigma }}_k^0$ preorders arising naturally in the above-mentioned areas are ${\rm{\Sigma }}_k^0$ -complete. This includes polynomial timem-reducibility on exponential time sets, which is ${\rm{\Sigma }}_2^0$ , almost inclusion on r.e. sets, which is ${\rm{\Sigma }}_3^0$ , and Turing reducibility on r.e. sets, which is ${\rm{\Sigma }}_4^0$ .

Abstract 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 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. A further application is the complete solution of [24, Problem 3.6.9]: 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 give a negative answer to [24, Problem 8.2.14]: not all weakly 2-random sets are array computable. In fact, given any oracle X, there is a weakly 2-random which is not array computable relative to X. This contrasts with the fact that all 2-random sets are array computable.

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 δ20 set B >tt ∅′ such that there is no c.e. set A with A′ ≡wttB. We also show that there is a Σ20 set C >tt ∅′ such that there is no δ20 set D with D′ ≡wttC.

Abstract We introduce a natural strengthening of prompt simplicity which we call strong promptness, and study its relationship with existing lowness classes. This notion provides a ≤wtt version of superlow cuppability. We show that every strongly prompt c.e. set is superlow cuppable. Unfortunately, strong promptness is not a Turing degree notion, and so cannot characterize the sets which are superlow cuppable. However, it is a wtt-degree notion, and we show that it characterizes the degrees which satisfy a wtt-degree notion very close to the definition of superlow cuppability. Further, we study the strongly prompt c.e. sets in the context of other notions related promptness, superlowness, and cupping. In particular, we show that every benign cost function has a strongly prompt set which obeys it, providing an analogue to the known result that every cost function with the limit condition has a prompt set which obeys it. 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.

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

Abstract In this paper we show that there is a pair of superhigh r.e. degree that forms 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 ∅′ very closely in terms of ∅′-jump traceability. In particular, we will construct an ultrahigh degree which is cappable.