The automatic complexity of a finite word (string) is an analogue for finite automata of Sipser’s distinguishing complexity (1983) and was introduced by Shallit and Wang (2001). For a finite alphabet Σ of at least two elements, we consider the non-deterministic automatic complexity given by exactly - yet not necessarily uniquely - accepting automata: a word x ∈ Σ^* has exact non-deterministic automatic complexity k ∈ ℕ if there exists a non-deterministic automaton of k states which accepts x while rejecting every other word of the same length as x, and no automaton of fewer states has this property. Importantly, and in contrast to the classical notion, the witnessing automaton may have multiple paths of computation accepting x. We denote this measure of complexity by A_{Ne}, and study a class of languages of low A_{Ne}-complexity defined as L_q = {x ∈ Σ^* : A_{Ne}(x) < q|x|}, which is parameterised by rationals q ∈ (0,1/2) (generalising a class of sets first studied by Kjos-Hanssen). We show that for every q ∈ (0,1/2), this class is neither context-free nor recognisable by certain Boolean circuits. In the process, we answer an open question of Kjos-Hanssen quantifying the complexity of L_{1/3} in terms of Boolean circuits, and also prove the Shannon effect for A_{Ne}.

Abstract Jiménez, Becerra and Gelbukh (2013) defined a family of ‘symmetric Tversky ratio models’ $S_{\alpha ,\beta }$, $0\le \alpha \le 1$, $\beta>0$. Each function $D_{\alpha ,\beta }=1-S_{\alpha ,\beta }$ is a semimetric on the powerset of a given finite set. We show that $D_{\alpha ,\beta }$ is a metric if and only if $0\le \alpha \le \frac 12$ and $\beta \ge 1/(1-\alpha )$. This result is formally verified in the Lean proof assistant. The extreme points of this parametrized space of metrics are $\mathcal V_1=D_{1/2,2}$, the Jaccard distance and $\mathcal V_{\infty }=D_{0,1}$, an analogue of the normalized information distance of M. Li, Chen, X. Li, Ma and Vitányi (2004). As a second interpolation, in general, we also show that $\mathcal V_p$ is a metric, $1\le p\le \infty $, where $$ \begin{align*} & \varDelta_p(A,B)=(\lvert{B\setminus A}\rvert^p+\lvert{A\setminus B}\rvert^p)^{1/p}, \end{align*}$$$$ \begin{align*} & \mathcal V_p(A,B)=\frac{\varDelta_p(A,B)}{\lvert{A\cap B}\rvert + \varDelta_p(A,B)}. \end{align*}$$

We investigate enumerability properties for classes of sets which permit recursive, lexicographically increasing approximations, or left-r.e. sets. In addition to pinpointing the complexity of left-r.e. Martin-Löf, computably, Schnorr, and Kurtz random sets, weakly 1-generics and their complementary classes, we find that there exist characterizations of the third and fourth levels of the arithmetic hierarchy purely in terms of these notions. More generally, there exists an equivalence between arithmetic complexity and existence of numberings for classes of left-r.e. sets with shift-persistent elements. While some classes (such as Martin-Löf randoms and Kurtz nonrandoms) have left-r.e. numberings, there is no canonical, or acceptable , left-r.e. numbering for any class of left-r.e. randoms. Finally, we note some fundamental differences between left-r.e. numberings for sets and reals.

Abstract We affirm a conjecture of Sacks [1972] by showing that every countable distributive lattice is isomorphic to an initial segment of the hyperdegrees, . In fact, we prove that every sublattice of any hyperarithmetic lattice (and so, in particular, every countable, locally finite lattice) is isomorphic to an initial segment of . Corollaries include the decidability of the two quantifier theory of , and the undecidability of its three quantifier theory. The key tool in the proof is a new lattice representation theorem that provides a notion of forcing for which we can prove a version of the fusion lemma in the hyperarithmetic setting and so the preservation of ω1ck. Somewhat surprisingly, the set theoretic analog of this forcing does not preserve ω1. On the other hand, we construct countable lattices that are not isomorphic to any initial segment of .

Abstract We consider two axioms of second-order arithmetic. These axioms assert, in two different ways, that infinite but narrow binary trees always have infinite paths. We show that both axioms are strictly weaker than Weak König's Lemma, and incomparable in strength to the dual statement (WWKL) that wide binary trees have paths.

Dobrinen and Simpson [4] introduced the notions of almost everywhere domination and uniform almost everywhere domination to study recursion theoretic analogues of results in set theory concerning domination in generic extensions of transitive models of ZFC and to study regularity properties of the Lebesgue measure on 2ω in reverse mathematics. In this article, we examine one of their conjectures concerning these notions. Throughout this article, ≤T denotes Turing reducibility and μ denotes the Lebesgue (or “fair coin”) probability measure on 2ω given by A property holds almost everywhere or for almost all X ∈ 2ω if it holds on a set of measure 1. For f, g ∈ ωω, f dominatesg if ∃m∀n < m(f(n) > g(n)). (Dobrinen, Simpson). A set A ∈ 2ωis almost everywhere (a.e.) dominating if for almost all X ∈ 2ω and all functions g ≤TX, there is a function f ≤TA such that f dominates g. A is uniformly almost everywhere (u.a.e.) dominating if there is a function f ≤TA such that for almost all X ∈ 2ω and all functions g ≤TX, f dominates g. There are several trivial but useful observations to make about these definitions. First, although these properties are stated for sets, they are also properties of Turing degrees. That is, a set is (u.)a.e. dominating if and only if every other set of the same degree is (u.)a.e. dominating. Second, both properties are closed upwards in the Turing degrees. Third, u.a.e. domination implies a.e. domination. Finally, if A is u.a.e. dominating, then there is a function f ≤TA which dominates every computable function.

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.

Abstract. In Reverse Mathematics, the axiom system DNR. asserting the existence of diagonally non-recursive functions, is strictly weaker than WWKL0 (weak weak König's Lemma).