Abstract The tower number ${\mathfrak t}$ and the ultrafilter number $\mathfrak {u}$ are cardinal characteristics from set theory. They are based on combinatorial properties of classes of subsets of $\omega $ and the almost inclusion relation $\subseteq ^*$ between such subsets. We consider analogs of these cardinal characteristics in computability theory. We say that a sequence $(G_n)_{n \in {\mathbb N}}$ of computable sets is a tower if $G_0 = {\mathbb N}$ , $G_{n+1} \subseteq ^* G_n$ , and $G_n\smallsetminus G_{n+1}$ is infinite for each n. A tower is maximal if there is no infinite computable set contained in all $G_n$ . A tower ${\left \langle {G_n}\right \rangle }_{n\in \omega }$ is an ultrafilter base if for each computable R, there is n such that $G_n \subseteq ^* R$ or $G_n \subseteq ^* \overline R$ ; this property implies maximality of the tower. A sequence $(G_n)_{n \in {\mathbb N}}$ of sets can be encoded as the “columns” of a set $G\subseteq \mathbb N$ . Our analogs of ${\mathfrak t}$ and ${\mathfrak u}$ are the mass problems of sets encoding maximal towers, and of sets encoding towers that are ultrafilter bases, respectively. The relative position of a cardinal characteristic broadly corresponds to the relative computational complexity of the mass problem. We use Medvedev reducibility to formalize relative computational complexity, and thus to compare such mass problems to known ones. We show that the mass problem of ultrafilter bases is equivalent to the mass problem of computing a function that dominates all computable functions, and hence, by Martin’s characterization, it captures highness. On the other hand, the mass problem for maximal towers is below the mass problem of computing a non-low set. We also show that some, but not all, noncomputable low sets compute maximal towers: Every noncomputable (low) c.e. set computes a maximal tower but no 1-generic $\Delta ^0_2$ -set does so. We finally consider the mass problems of maximal almost disjoint, and of maximal independent families. We show that they are Medvedev equivalent to maximal towers, and to ultrafilter bases, respectively.

Abstract The general theory developed by Ben Yaacov for metric structures provides Fraïssé limits which are approximately ultrahomogeneous. We show here that this result can be strengthened in the case of relational metric structures. We give an extra condition that guarantees exact ultrahomogenous limits. The condition is quite general. We apply it to stochastic processes, the class of diversities, and its subclass of $L_1$ diversities.

Abstract A mass problem is a set of functions $\omega \to \omega $ . For mass problems ${\mathcal {C}}, {\mathcal {D}}$ , one says that ${\mathcal {C}}$ is Muchnik reducible to ${\mathcal {D}}$ if each function in ${\mathcal {C}}$ is computed by a function in ${\mathcal {D}}$ . In this paper we study some highness properties of Turing oracles, which we view as mass problems. We compare them with respect to Muchnik reducibility and its uniform strengthening, Medvedev reducibility. For $p \in [0,1]$ let ${\mathcal {D}}(p)$ be the mass problem of infinite bit sequencesy(i.e., $\{0,1\}$ -valued functions) such that for each computable bit sequencex, the bit sequence $ x {\,\leftrightarrow\,} y$ has asymptotic lower density at mostp(where $x {\,\leftrightarrow\,} y$ has a $1$ in positionniff $x(n) = y(n)$ ). We show that all members of this family of mass problems parameterized by a realpwith $0 < p <1/2 $ have the same complexity in the sense of Muchnik reducibility. We prove this by showing Muchnik equivalence of the problems ${\mathcal {D}}(p)$ with the mass problem $\text {IOE}({2^{2}}^{n})$ ; here for an order functionh, the mass problem $\text {IOE}(h)$ consists of the functionsfthat agree infinitely often with each computable function bounded byh. This result also yields a new version of the proof to of the affirmative answer to the “Gamma question” due to the first author: $\Gamma (A)< 1/2$ implies $\Gamma (A)=0$ for each Turing oracleA. As a dual of the problem ${\mathcal {D}}(p)$ , define ${\mathcal {B}}(p)$ , for $0 \le p < 1/2$ , to be the set of bit sequencesysuch that $\underline \rho (x {\,\leftrightarrow\,} y)> p$ for each computable setx. We prove that the Medvedev (and hence Muchnik) complexity of the mass problems ${\mathcal {B}}(p)$ is the same for all $p \in (0, 1/2)$ , by showing that they are Medvedev equivalent to the mass problem of functions bounded by ${2^{2}}^{n}$ that are almost everywhere different from each computable function. Next, together with Joseph Miller, we obtain a proper hierarchy of the mass problems of type $\text {IOE}$ : we show that for any order functiongthere exists a faster growing order function $h $ such that $\text {IOE}(h)$ is strictly above $\text {IOE}(g)$ in the sense of Muchnik reducibility. We study cardinal characteristics in the sense of set theory that are analogous to the highness properties above. For ins

Abstract The Jordan decomposition theorem states that every function $f \colon \, [0,1] \to \mathbb {R}$ of bounded variation can be written as the difference of two non-decreasing functions. Combining this fact with a result of Lebesgue, every function of bounded variation is differentiable almost everywhere in the sense of Lebesgue measure. We analyze the strength of these theorems in the setting of reverse mathematics. Over $\mathsf {RCA}_{0}$ , a stronger version of Jordan’s result where all functions are continuous is equivalent to $\mathsf {ACA}_0$ , while the version stated is equivalent to ${\textsf {WKL}}_{0}$ . The result that every function on $[0,1]$ of bounded variation is almost everywhere differentiable is equivalent to ${\textsf {WWKL}}_{0}$ . To state this equivalence in a meaningful way, we develop a theory of Martin–Löf randomness over $\mathsf {RCA}_0$ .

We study algorithmic randomness properties for probability measures on Cantor space. We say that a measure μ on the space of infinite bit sequences is Martin-Löf absolutely continuous if the non-Martin-Löf random bit sequences form a null set with respect to μ. We think of this as a weak randomness notion for measures. We begin with examples, and a robustness property related to Solovay tests. Our main work connects our property to the growth of the initial segment complexity for measures μ; the latter is defined as a μ-average over the complexity of strings of the same length. We show that a maximal growth implies our weak randomness property, but also that both implications of the Levin-Schnorr theorem fail. We briefly discuss K-triviality for measures, which means that the growth of initial segment complexity is as slow as possible. We show that full Martin-Löf randomness of a measure implies Martin-Löf absolute continuity; the converse fails because only the latter property is compatible with having atoms. In a final section we consider weak randomness relative to a general ergodic computable measure. We seek appropriate effective versions of the Shannon-McMillan-Breiman theorem and the Brudno theorem where the bit sequences are replaced by measures.

Abstract We investigate the strength of a randomness notion ${\cal R}$ as a set-existence principle in second-order arithmetic: for eachZthere is anXthat is ${\cal R}$ -random relative toZ. We show that the equivalence between 2-randomness and being infinitely oftenC-incompressible is provable in $RC{A_0}$ . We verify that $RC{A_0}$ proves the basic implications among randomness notions: 2-random $\Rightarrow$ weakly 2-random $\Rightarrow$ Martin-Löf random $\Rightarrow$ computably random $\Rightarrow$ Schnorr random. Also, over $RC{A_0}$ the existence of computable randoms is equivalent to the existence of Schnorr randoms. We show that the existence of balanced randoms is equivalent to the existence of Martin-Löf randoms, and we describe a sense in which this result is nearly optimal.

Abstract We study the complexity of the topological isomorphism relation for various classes of closed subgroups of the group of permutations of the natural numbers. We use the setting of Borel reducibility between equivalence relations on Borel spaces. For profinite, locally compact, and Roelcke precompact groups, we show that the complexity is the same as the one of countable graph isomorphism. For oligomorphic groups, we merely establish this as an upper bound.

(1) There is a finitely presented group with a word problem which is a uniformly effectively inseparable equivalence relation. (2) There is a finitely generated group of computable permutations with a word problem which is a universal co-computably enumerable equivalence relation. (3) Each c.e. truth-table degree contains the word problem of a finitely generated group of computable permutations.

The Gamma question was formulated by Andrews et al. In "Asymptotic density, computable trace ability and 1-randomness" (2013, available at http://www.math.wisc.edu/~lempp/papers/traceable.pdf). It is related to the recent notion of coarse computability which stems from complexity theory. The Gamma value of an oracle set measures to what extent each set computable with the oracle is approximable, in the sense of density, by a computable set. The closer to 1 this value is, the closer the oracle is to being computable. The Gamma question asks whether this value can be strictly in between 0 and 1/2. We say that an oracle is weakly Schnorr engulfing if it computes a Schnorr test that succeeds on all computable reals. We show that each non weakly Schnorr engulfing oracle has a Gamma value of at least 1/2. Together with a recent result of Kjos-Hanssen, Stephan, and Terwijn, this establishes new examples of such oracles. We also give a unifying approach to oracles with Gamma value 0. We say that an oracle is infinitely often equal with bound h if it computes a function that agrees infinitely often with each computable function bounded by h. We show that every oracle which is infinitely equal with bound 2dn for d>1 has a Gamma value of 0. This provides new examples of such oracles as well. We present a combinatorial characterization of being weakly Schnorr engulfing via traces, which is inspired by the study of cardinal characteristics in set theory.

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.

We show that a real z is polynomial time random if and only if each nondecreasing polynomial time computable function is differentiable at z. This establishes an analog in feasible analysis of a recent result of Brattka, Miller and Nies, who characterized computable randomness in terms of differentiability of nondecreasing computable functions. Further, we show that a Martin-Loef random real z is a density-one point if and only if each interval-c.e. function is differentiable at z. (To say z is a density-one point means that every effectively closed class containing z has density one at z. The interval-c.e. functions are, essentially, the variation functions of computable functions.) The proofs are related: they both make use of the analytical concept of porosity in novel ways, and both use a basic geometric fact on shifting dyadic intervals by 1/3.

Abstract We show the existence of noncomputable oracles which are low for Demuth randomness, answering a question in [15] (also Problem 5.5.19 in [34]). We fully characterize lowness for Demuth randomness using an appropriate notion of traceability. Central to this characterization is a partial relativization of Demuth randomness, which may be more natural than the fully relativized version. We also show that an oracle is low for weak Demuth randomness if and only if it is computable.

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

We show that every non-low c.e. set joins all Δ20 diagonally non-computable functions to ∅′. We give two proofs: a direct argument, and a proof using an analysis of functions that are DNC relative to an oracle, extending work by Day and Reimann. The latter proof is also presented in the language of Kolmogorov complexity.

The Denjoy-Young-Saks Theorem from classical analysis states that for an arbitrary function f:R->R, the Denjoy alternative holds outside a null set, i.e., for almost every real x, either the derivative of f exists at x, or the derivative fails to exist in the worst possible way: the limit superior of the slopes around x equals +infinity, and the limit inferior -infinity. Algorithmic randomness allows us to define randomness notions giving rise to different concepts of almost everywhere. It is then natural to wonder which of these concepts corresponds to the almost everywhere notion appearing in the Denjoy-Young-Saks theorem. To answer this question Demuth investigated effective versions of the theorem and proved that Demuth randomness is strong enough to ensure the Denjoy alternative for Markov computable functions. In this paper, we show that the set of these points is indeed strictly bigger than the set of Demuth random reals - showing that Demuth's sufficient condition was too strong - and moreover is incomparable with Martin-Löf randomness; meaning in particular that it does not correspond to any known set of random reals. To prove these two theorems, we study density-type theorems, such as the Lebesgue density theorem and obtain results of independent interest. We show for example that the classical notion of Lebesgue density can be characterized by the only very recently defined notion of difference randomness. This is to our knowledge the first analytical characterization of difference randomness. We also consider the concept of porous points, a special type of Lebesgue nondensity points that are well-behaved in the sense that the "density holes" around the point are continuous intervals whose length follows a certain systematic rule. An essential part of our proof will be to argue that porous points of effectively closed classes can never be difference random.

We give an alternative proof of a result of Kučera and Slaman (2009, Lower upper bounds of ideals, Journal of Symbolic Logic, 74, 517–534) on low bounds of ideals in the Δ02 Turing degrees. This is a characterization of the ideals in the Δ02 degrees which have a low upper bound. It follows that there is a low upper bound for the ideal of the K-trivial degrees. Our proof is direct, in the sense that it does not use universal classes of PA degrees.

As part of his groundbreaking work on algorithmic randomness, Solovay demonstrated in the 1970s the remarkable fact that there are computable upper bounds of prefix-free Kolmogorov complexity $K$ that are tight on infinitely many values (up to an additive constant). Such computable upper bounds are called Solovay functions. Recent work of Bienvenu and Downey~[STACS 2009, LIPIcs 3, pp 147-158] indicates that Solovay functions are deeply connected with central concepts of algorithmic randomness such as $Omega$ numbers, K-triviality, and Martin-Loef randomness. In what follows, among other results we answer two open problems posed by Bienvenu and Downey about the definition of $K$-triviality and about the Gacs-Miller-Yu characterization of Martin-Loef randomness. The former defines a sequence A to be K-trivial if K(A|n) <=^+ K(n), the latter asserts that a sequence A is Martin-Loef random iff C(A|n) >=^+ n-K(n). So both involve the noncomputable function K. As our main results we show that in both cases K(n) can be equivalently replaced by any Solovay function, and, what is more, that among all computable functions such a replacement is possible exactly for the Solovay functions. Moreover, similar statements hold for the larger class of all right-c.e. in place of the computable functions. These full characterizations, besides having significant theoretical interest on their own, will be useful as tools when working with K-trivial and Martin-Loef random sequences.

Abstract We show that the class of strongly jump-traceable c.e. sets can be characterised as those which have sufficiently slow enumerations so they obey a class of well-behaved cost functions, called benign. This characterisation implies the containment of the class of strongly jump-traceable c.e. Turing degrees in a number of lowness classes, in particular the classes of the degrees which lie below incomplete random degrees, indeed all LR-hard random degrees, and allω-c.e. random degrees. The last result implies recent results of Diamondstone's and Ng's regarding cupping with superlow c.e. degrees and thus gives a use of algorithmic randomness in the study of the c.e. Turing degrees.

Abstract We show that there is a complete, consistent Borel theory which has no “Borel model” in the following strong sense: There is no structure satisfying the theory for which the elements of the structure are equivalence classes under some Borel equivalence relation and the interpretations of the relations and function symbols are uniformly Borel. We also investigate Borel isomorphisms between Borel structures.

We define the notion of indifferent set with respect to a given class of {0,1}-sequences. Roughly, for a set A in the class, a set of natural numbers I is indifferent for A with respect to the class if it does not matter how we change A at the positions in I: the new sequence continues to be in the given class. We are especially interested in studying those sets that are indifferent with respect to classes containing different types of stochastic sequences. For the class of Martin-Löf random sequences, we show that every random sequence has an infinite indifferent set and that there is no universal indifferent set. We show that indifferent sets must be sparse, in fact sparse enough to decide the halting problem. We prove the existence of co-c.e. indifferent sets, including a co-c.e. set that is indifferent for every 2-random sequence with respect to the class of random sequences. For the class of absolutely normal numbers, we show that there are computable indifferent sets with respect to that class and we conclude that there is an absolutely normal real number in every non-trivial many-one degree.

We study the classes of Büchi and Rabin automatic structures. For Büchi (Rabin) automatic structures their domains consist of infinite strings (trees), and the basic relations, including the equality relation, and graphs of operations are recognized by Büchi (Rabin) automata. A Büchi (Rabin) automatic structure is injective if different infinite strings (trees) represent different elements of the structure. The first part of the paper is devoted to understanding the automata-theoretic content of the well-known Löwenheim-Skolem theorem in model theory. We provide automata-theoretic versions of Löwenheim-Skolem theorem for Rabin and Büchi automatic structures. In the second part, we address the following two well-known open problems in the theory of automatic structures: Does every Büchi automatic structure have an injective Büchi presentation? Does every Rabin automatic structure have an injective Rabin presentation? We provide examples of Büchi structures without injective Büchi and Rabin presentations. To answer these questions we introduce Borel structures and usesome of the basic properties of Borel sets and isomorphisms. Finally, in the last part of the paper we study the isomorphism problem for Büchi automatic structures.

We study the existence of automatic presentations for various algebraic structures. An automatic presentation of a structure is a description of the universe of the structure by a regular set of words, and the interpretation of the relations by synchronised automata. Our first topic concerns characterising classes of automatic structures. We supply a characterisation of the automatic Boolean algebras, and it is proven that the free Abelian group of infinite rank, as well as certain Fraisse limits, do not have automatic presentations. In particular, the countably infinite random graph and the random partial order do not have automatic presentations. Furthermore, no infinite integral domain is automatic. Our second topic is the isomorphism problem. We prove that the complexity of the isomorphism problem for the class of all automatic structures is \Sigma_1^1-complete.

Abstract We prove that there exists a noncomputable c.e. real which is low for weak 2-randomness, a definition of randomness due to Kurtz, and that all reals which are low for weak 2-randomness are low for Martin-Löf randomness.

Abstract We compare various notions of algorithmic randomness. First we consider relativized randomness. A set is n-random if it is Martin-Löf random relative to ∅(n − 1). We show that a set is 2-random if and only if there is a constant c such that infinitely many initial segments x of the set are c-incompressible: C(x) ≥ ∣x∣ − c. The ‘only if’ direction was obtained independently by Joseph Miller. This characterization can be extended to the case of time-bounded C-complexity. Next we prove some results on lowness. Among other things, we characterize the 2-random sets as those l-random sets that are low for Chaitin's Ω. Also, 2-random sets form minimal pairs with 2-generic sets. The r.e. low for Ω. sets coincide with the r.e. K-trivial ones. Finally we show that the notions of Martin-Löf randomness, recursive randomness, and Schnorr randomness can be separated in every high degree while the same notions coincide in every non-high degree. We make some remarks about hyperimmune-free and PA-complete degrees.

We answer a question of Ambos-Spies and Kucera in the affirmative. They asked whether, when a real is low for Schnorr randomness, it is already low for Schnorr tests.

This paper studies the existence of automatic presentations for various algebraic structures. The automatic Boolean algebras are characterised, and it is proven that the free Abelian group of infinite rank and many Fraisse limits do not have automatic presentations. In particular, the countably infinite random graph and the universal partial order do not have automatic presentations. Furthermore, no infinite integral domain is automatic. The second topic of the paper is the isomorphism problem. We prove that the complexity of the isomorphism problem for the class of all automatic structures is /spl Sigma//sub 1//sup 1/-complete.

We study effectively given positive reals (more specifically, computably enumerable reals) under a measure of relative randomness introduced by Solovay [manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 1975] and studied by Calude, Hertling, Khoussainov, and Wang [Theoret. Comput. Sci., 255 (2001), pp. 125--149], Calude [Theoret. Comput. Sci., 271 (2002), pp. 3--14], Kucera and Slaman [SIAM J. Comput., 31 (2002), pp. 199--211], and Downey, Hirschfeldt, and LaForte [Mathematical Foundations of Computer Science 2001, Springer-Verlag, Berlin, 2001, pp. 316--327], among others. This measure is called domination or Solovay reducibility and is defined by saying that $\alpha$ dominates $\beta$ if there are a constant c and a partial computable function $\varphi$ such that for all positive rationals $q < \alpha$ we have $\varphi(q)\!\downarrow < \beta$ and $\beta- \varphi(q) \leqslant c(\alpha- q)$. The intuition is that an approximating sequence for $\alpha$generates one for $\beta$ whose rate of convergence is not much slower than that of the original sequence. It is not hard to show that if $\alpha$ dominates $\beta$, then the initial segment complexity of $\alpha$ is at least that of $\beta$. In this paper we are concerned with structural properties of the degree structure generated by Solovay reducibility. We answer a natural question in this area of investigation by proving the density of the Solovay degrees. We also provide a new characterization of the random computably enumerable reals in terms of splittings in the Solovay degrees. Specifically, we show that the Solovay degrees of computably enumerable reals are dense, that any incomplete Solovay degree splits over any lesser degree, and that the join of any two incomplete Solovay degrees is incomplete, so that the complete Solovay degree does not split at all. The methodology is of some technical interest, since it includes a priority argument in which the injuries are themselves controlled by randomness considerations.

Abstract. We show that in the lattice of classes there are initial segments [∅, P] = (P) which are not Boolean algebras, but which have a decidable theory. In fact, we will construct for any finite distributive lattice L which satisfies the dual of the usual reduction property a class P such that L is isomorphic to the lattice (P)*, which is (P). modulo finite differences. For the 2-element lattice, we obtain a minimal class, first constructed by Cenzer, Downey, Jockusch and Shore in 1993. For the simplest new class P constructed, P has a single, non-computable limit point and (P)* has three elements, corresponding to ∅, P and a minimal class P0 ⊂ P, The element corresponding to P0 has no complement in the lattice. On the other hand, the theory of (P) is shown to be decidable. A class P is said to be decidable if it is the set of paths through a computable tree with no dead ends. We show that if P is decidable and has only finitely many limit points, then (P)* is always a Boolean algebra. We show that if P is a decidable class and (P) is not a Boolean algebra, then the theory of (P) interprets the theory of arithmetic and is therefore undecidable.

Abstract We prove that each Σ20 set which is hypersimple relative to ∅′ is noncuppable in the structure of the Σ20 enumeration degrees. This gives a connection between properties of Σ20 sets under inclusion and and the Σ20 enumeration degrees. We also prove that some low non-computably enumerable enumeration degree contains no set which is simple relative to ∅′.

We prove that the theory of EXPTIME degrees with respect to polynomial time Turing and many-one reducibility is undecidable. To do so we use a coding method based on ideal lattices of Boolean algebras which is introduced A. Nies. The method can be applied in fact to all hyper-polynomial time classes.

We show that the elementary theory of the recursively enumerable tt-degrees has the same computational complexity as true first-order arithmetic. As auxiliary results, we prove theorems about exact pairs and initial segments in the tt-degrees.

Abstract We show that the Π4-theory of the partial order of recursively enumerable weak truth-table degrees is undecidable, and give a new proof of the similar fact for r.e. T-degrees. This is accomplished by introducing a new coding scheme which consists in defining the class of finite bipartite graphs with parameters.

Abstract We show that the partial order of -sets under inclusion is elementarily definable with parameters in the semilattice of r.e. wtt-degrees. Using a result of E. Herrmann, we can deduce that this semilattice has an undecidable theory, thereby solving an open problem of P. Odifreddi.