Effective aspects of algorithmically random structures

Abstract

In this paper we study various properties of algorithmically random infinite structures. Our results address the following questions. How would one define algorithmic randomness for infinite structures? Could algorithmically random structures be computable? What are the similarities and differences between algorithmically random structures and algorithmically random infinite strings? What are the possible Turing degrees of algorithmically random structures? Are there algorithmically random infinite groups? For instance, we prove the following in this paper: (1) there are classes which contain algorithmically random yet computable structures, (2) there exist algorithmically random universal algebras with co-computably enumerable as well as computably enumerable word problems, (3) there are natural classes of structures in which the Turing degrees of algorithmically random structures can only be either computable or equivalent to the halting set, and (4) there are examples of algorithmically random groups. The first result shows a dramatic difference between algorithmically random strings and algorithmically random structures. The second result significantly improves the known theorem that algorithmically random structures computable in the halting set exist; these examples of algebras are sharp in terms of arithmetical hierarchy of the word problem for random algebras. The third result is a dichotomy theorem that characterises all possible Turing degrees of algorithmically random structures. Finally, the fourth result answers a nontrivial open question about the existence of algorithmically random groups.

Keywords

Random structures word problem degree of a structure random groups

1. Introduction

1.1. Background and motivation

Algorithmic randomness of infinite strings has a captivating history going back to Kolmogorov [11], Martin-Löf [16], Chaitin [2], Schnorr [20,21], Levin [24]. In the last two decades the topic has attracted the attention of experts in complexity, computability, logic, philosophy, and algorithms. For instance, see the monographs by Downey/Hirschfeldt [3], Nies [17] and textbooks by Li/Vitanyi [13], Calude [1]. Martin-Löf gave one of the foundational definitions of algorithmic randomness for infinite strings. The key ingredient in the definition is the natural measure present on the Cantor space ${0, 1}^{ω}$ . Martin-Löf randomness states that random strings are those that avoid all effective measure zero sets.

Martin-Löf random (ML-random) infinite strings possess many properties that are intuitively clear (and that can formally be proved; see [3,17]): they are incompressible; they do not contain infinite computable substrings; they satisfy the law of large numbers; no winning strategies exist that given an initial segment of the string bet on the next bit of it.

How would one define algorithmic randomness for infinite structures such as graphs, trees, groups, or universal algebras? What properties would these algorithmically random structures possess? Can algorithmically random structures be computable? Can algorithmically random universal algebras have computably enumerable word problem? What are the similarities and differences between algorithmically random structures and random infinite strings? Are there algorithmically random infinite groups? What are the possible Turing degrees of algorithmically random structures? In this paper we address and (partially) answer all these questions.

A natural yet naive way to introduce algorithmic randomness for structures is this. Let $G = (ω; R)$ be a relational structure, say in the language of undirected graphs. So, G is a graph. List all unordered pairs from ω. Now we code $G$ into the following binary string $α_{G}$ : $α_{G} (i) = 1$ if and only if R is true on the ith unordered pair. Call the graph $G$ algorithmically random if the string $α_{G}$ is Martin-Löf random. Is this a good definition? One proves that if $α_{G}$ is ML-random then $G$ is the Fraïssé limit of all finite graphs [9]. So, from model theory [7] we know that (1) the first order theory of graph $G$ is $ℵ_{0}$ -categorical, (2) the graph $G$ is isomorphic to a computable graph, (3) the graph $G$ satisfies the extension axioms, and (4) the theory of $G$ admits effective quantifier elimination. Property (1) implies that all algorithmically random structures (as defined above) are isomorphic. Erdös and Spencer [4] remark that this phenomenon “demolishes the theory of infinite random graphs”. As far as algorithmic randomness is concerned, property (2) is counter-intuitive in two ways. The first is that one would like algorithmic randomness to be a property of the isomorphism type rather than a property of the presentation of the structure. The second is that it is not clear at all why computability of a structure is compatible with algorithmic randomness; certainly this fails for infinite binary strings. Properties (3) and (4) provide an effective description of the structure in the first order logic and decidability of its the first order theory. All these defy the intuitive notion of algorithmic randomness and suggest alternative approaches should be taken towards defining algorithmic randomness for infinite structures.

As the natural measure in the Cantor space is central in defining algorithmic randomness for infinite strings, ultimately the task (of defining algorithmically random structures) consists of introducing meaningful measures into the classes of infinite algebraic structures. The second author accomplishes this task in papers [9] and [8] thus initiating a systematic study of algorithmic randomness for infinite algebraic structures. This paper continuous the line of research for studying algorithmic randomness for infinite structures proposed in [9] and [8]. In particular, the paper answers some of the important questions, including the ones we posed earlier, necessary for deep understanding of algorithmic random algebraic structures.

1.2. Outline and contributions

1. Algorithmic randomness for infinite structures is introduced through the concept of branching classes (B-classes for short) defined in [8]. Informally, a branching class provides a context in which one can reason about algorithmic randomness of algebraic structures. Section 2 recalls the definition and provides examples of branching classes. Every branching class $K$ consists of finite structures and determines the class $K_{ω}$ of infinite structures that are direct limits of structures from $K$ . The class $K$ also determines a finitely branching tree $T (K)$ such that there is a bijective operator $η \to A_{η}$ mapping infinite paths η of $T (K)$ to structure $A_{η}$ from $K_{ω}$ . Using the tree $T (K)$ , we naturally equip the class $K_{ω}$ with measure. Having the measure, one defines Martin-Löf random structures in $K_{ω}$ . This implies, just like for infinite bit strings, that ML-random structures in the class $K_{ω}$ forms the continuum (Theorem 3.6), and among them there are ML-random structures computable in the halting set $0^{'}$ (Theorem 4.11).

2. It is an expected phenomenon that there exist ML-random structures computable in the halting set $0^{'}$ . Such structures correspond to the leftmost paths of computable infinite finitely branching trees, and such paths are computable in $0^{'}$ . The mapping $η \to A_{η}$ mentioned above is a computable operator; hence, the structure $A_{η}$ is computable in any oracle computing η. In contrast, building η from $A_{η}$ requires the jump of the open diagram of $A_{η}$ . We exploit this in constructing ML-random and yet computable structures (Theorem 5.1). Such example is also built in [8], but our construction here is considerably simpler and shorter. This example is also essential for understanding results appearing later in the paper. We remarked earlier that it is counter-intuitive that a computable object might be algorithmically random; it is because ML-randomness does not preclude computability just like ML-randomness of strings does not preclude computability in the halting set $0^{'}$ . But, we prove that no 2-ML-random structure is computable (Theorem 5.4), where 2-ML-randomness is ML-randomness relative to the halting set $0^{'}$ .

3. We construct ML-random universal algebra $A_{1}$ with computably enumerable word problem (Theorem 6.8). We also construct ML-random universal algebra $A_{2}$ with co-computably enumerable word problem (Theorem 6.2). These examples are important because of the following reasons. The first is that no ML-random algebra has a computable word problem [9]. So, there are no computable ML-random algebras. Compare this with existence of ML-random computable structures mentioned above. However, ML-random algebras computable in the halting set $0^{'}$ exist by Theorem 4.11. The word problems in such algebras are $Δ_{2}^{0}$ -sets. The examples $A_{1}$ and $A_{2}$ show that the word problem in ML-random algebras can be $Σ_{1}^{0}$ and $Π_{1}^{0}$ thus significantly improving the $Δ_{2}^{0}$ bound. The second reason is that these are the only possible imrpovements in terms of arithmetical hierarchy. Finally, drawing a parallel to infinite strings, it is known that there exist ML-random computably enumerable from the left (and also there exist ML-random computably enumerable from the right) strings, e.g. the halting probability of the prefix free universal Turing machine [2]. The existence of structures $A_{1}$ and $A_{2}$ can be viewed as a reflection of this phenomenon in the case of universal algebras.

4. We study the degrees of ML-random structures. The degree of a structure is a fundamental concept used in modern model theory and computability [10,19,23]. Let $B$ be an infinite structure with domain ω. The open diagram of $B$ is the set of atomic relations or their negations true in $B$ . The degree of a structure $A$ , denoted by $\deg (A)$ , is the least Turing degree among all Turing degrees of open diagrams of structures isomorphic to $A$ in case such degree exists. So, x is the degree of $A$ if the following two properties are satisfied: (a) x computes a copy of the structure, and (b) all copies of $A$ compute x. The degree represents the least amount of computability needed to represent the structure. We prove a dichotomy theorem showing that for natural branching classes $K$ , the only possible degrees of ML-random structures are the computable degree and the degree of the halting set, and both degrees are realisable (Theorem 7.5). This is an unexpected phenomenon and stands in a stark contrast with algorithmic randomness for infinite strings.

5. The study of random finitely generated groups has a long history [5,22]. Traditionally, this is done by fixing generators and choosing for each n a relator of length n at random. By Gromov [5], random groups are hyperbolic (with probability 1), and hence have decidable word problem. The approach to randomness taken in this paper gives a different notion of randomness for groups, which corresponds to randomly determining larger and larger balls in Cayley graphs. Our approach contrasts Gromov’s one in the sense that all ML-random groups have undecidable word problem. But, to exhibit ML-random groups we need to build branching classes of groups, the problem asked in [9]. The problem of finding branching classes of groups is hard because it intuitively relates to the word problem in groups. Using small cancellation theory developed in [14], we solve the problem and provide an example of a branching class of groups. So, there are ML-random groups (Theorem 8.6). The reason Gromov’s random groups contrast with our random groups is that Gromov’s definition is syntactic (select relators at random) while our definition is semantic and algebraic (select extensions of Cayley graphs at random).

2. Branching classes

In this section we review the branching classes of [8,9]. A relational signature σ is $(R_{1}^{n_{0}}, \dots, R_{m}^{n_{m}}, c_{1}, \dots, c_{k})$ , where $R_{i}^{n_{i}}$ is a relational symbol of arity $n_{i}$ and $c_{j}$ is a constant symbol. We identify structures of the signature up to isomorphisms and call them σ-structures or structures if σ is clear from the content. All our structures are countable. Structures that contain functional operations can be identified with relational structures by replacing operations with their graphs.

Definition 2.1.
An embedded system is a sequence ${(A_{i}, f_{i})}_{i \in ω}$ such that each $A_{i}$ is a finite structure, the cardinality of $A_{i}$ is smaller than the cardinality of $A_{i + 1}$ , and $f_{i}$ is an embedding from $A_{i}$ into $A_{i + 1}$ . Call the sequence $A_{0}, A_{1}, \dots$ the base of the system.

Each embedded system ${(A_{i}, f_{i})}_{i \in ω}$ determines the limit structure denoted by ${lim}_{i} (A_{i}, f_{i})$ . Formally, the limit structure is the quotient of $⋃_{i} A_{i}$ by a particular equivalence relation: for $a \in A_{i}$ and $b \in A_{j}$ with $i < j$ , $a \sim b$ iff $f_{j - 1} \circ f_{j - 2} \circ \dots \circ f_{i} (a) = b$ . The limit structure depends on embeddings $f_{i}$ . For instance, each countable linear order is a direct limit of an embedded system with base ${0 < \dots < i}_{i \in ω}$ . We want the limit to be independent of the embeddings, and formalise this through the following definition.
Definition 2.2.
An embedded system ${(A_{i}, f_{i})}_{i \in ω}$ is strict if ${lim}_{i} (A_{i}, f_{i})$ is isomorphic to the direct limit of any embedded system with the base $A_{0}, A_{1}, \dots$ .

Let $K$ be a decidable class of finite structures. We assume that the structures are given by their explicit representations. Our goal is to define classes of structures in which all embedded systems are strict.
Definition 2.3 (Height function).

A computable function $h : K \to ω$ is called a height function for the class $K$ if it satisfies the following properties:

The set $h^{- 1} (i)$ is finite for all $i \in ω$ , and we can compute the cardinality of $h^{- 1} (i)$ for every i. A structure $A \in K$ has height i if $h (A) = i$ .

For every $A \in K$ of height i there is a substructure $A [i - 1]$ of height $i - 1$ such that all substructures of $A$ of height $⩽ i - 1$ are contained in $A [i - 1]$ .

For all $A \in K$ of height i and all $B \in K$ with $A [i - 1] \subset B \subseteq A$ and $A [i - 1] = B [i - 1]$ , we have $h (B) = i$ .

Note that h is an isomorphism invariant. Also, condition (2) implies that the substructure $A [i - 1]$ is unique, as it is the largest substructure of A of height $i - 1$ . In addition, for all $A \in K$ of height i and $j ⩽ i$ there exists a substructure $A [j]$ of height j such that all substructures of $A$ of height $⩽ j$ are contained in $A [j]$ . Also, $A [0] \subset A [1] \subset \dots \subset A [i]$ , where $A [i] = A$ , and for $ℓ ⩽ j$ , $A [j] [ℓ] = A [ℓ]$ . Thus:

Corollary 2.4.
For all $A, B \in K$ , the structures $A$ and $B$ are isomorphic if and only if $h (A) = h (B)$ and $A [j] = B [j]$ for all $j ⩽ h (A)$ .

The next lemma states the main property of classes $K$ with height functions.
Lemma 2.5 ([8]).

Let $K$ and h be as above. Every embedded system of structures from $K$ is strict.

Proof.
Briefly, this is because of the uniqueness of the substructure $A [i]$ . Let ${(A_{i}, f_{i})}_{i \in ω}$ and ${(B_{i}, g_{i})}_{i \in ω}$ be embedded systems with the same base. For $j < i$ , let $f_{j, i} : A_{j} \to A_{i}$ and $g_{j, i} : B_{j} \to B_{i}$ by the obvious compositions of maps. Let $A$ and $B$ be the direct limits of these two systems, respectively. We prove that $A$ and $B$ are isomorphic. If need be, by selecting subsequences, we can assume that the heights of $A_{i}$ and $B_{i}$ are at least i, and $A_{i} [j] = A_{j} [j]$ and $B_{i} [j] = B_{j} [j]$ for all $i ⩾ j$ . This can be done since the number of structures of height j is finite and $A_{i}$ , $B_{i}$ are increasing in size.

For all i, consider all isomorphisms $α : A_{i} [i] \to B_{i} [i]$ . Such an isomorphism necessarily exists, since $i ⩽ ℓ = min {h (A_{i}), h (B_{i})}$ , and $A_{i} [i] = A_{i} [ℓ] [i]$ and is unique. By the uniqueness of $A_{i} [j]$ , we have $α (A_{i} [j]) = B_{i} [j]$ for all $j ⩽ i$ . By uniqueness of $A_{i} [j]$ and our assumption, $f_{j, i} (A_{j} [j]) = A_{i} [j]$ . Similarly, $g_{j, i} (B_{j} [j]) = B_{i} [j]$ . Thus the composition $g_{j, i}^{- 1} \circ α \circ f_{j, i}$ is an isomorphism from $A_{j} [j]$ to $B_{j} [j]$ .

For $j ⩽ i$ , $α_{i} : A_{i} [i] \to B_{i} [i]$ and $α_{j} : A_{j} [j] \to B_{j} [j]$ , write $α_{j} ⊴ α_{i}$ if $α_{i} \circ f_{j, i} = g_{j, i} \circ α_{j}$ . As we have just argued, for every $α_{i}$ there is an $α_{j}$ with $α_{j} ⊴ α_{i}$ . The set of all such isomorphisms α thus forms a tree T under ⊴. Namely, nodes of this tree at level i are isomorphisms from $A_{i} [i]$ onto $B_{i} [i]$ . This tree T is finitely branching, since each $A_{i} [i]$ is finite. By König’s lemma, there is an infinite path $(α_{0}, α_{1}, \dots)$ on the tree. By definition of ⊴, this path induces a well-defined map from $A$ to $B$ .

It remains to show that α is total and surjective. For $A_{j}$ of height i, there is an embedding $f_{j, i}$ of $A_{j}$ into $A_{i} [i]$ , and so $f_{j, i} (A_{j}) \subseteq A_{i} [i]$ . Thus $A_{j} \subseteq dom α_{i} \circ f_{j, i}$ . So α is total. A symmetric argument shows that it is surjective. □

Thus, for every embedded system ${(A_{i}, f_{i})}_{i \in ω}$ from $K$ there is an embedded system ${B_{i}, g_{i}}_{i \in ω}$ of structures from the same class such that: (1) the direct limits ${lim}_{i} (A_{i}, f_{i})$ and ${lim}_{i} (B_{i}, g_{i})$ are isomorphic; (2) the height of each $B_{i}$ is i; (3) the embeddings $g_{i}$ are identity embeddings; and (4) for all $i ⩽ j$ we have $B_{j} [i] = B_{i} [i] = B_{i}$ . First, we can assume that the $A_{0} \subseteq A_{1} \subseteq A_{2} \subseteq \dots$ , and then we can simply take $B_{i} = A_{j} [i]$ for sufficiently large j.
Definition 2.6.
Let $K$ and h be as above. Set: $\begin{matrix} K_{ω} = {A ∣ A is the direct limit of an embedded system from the class K} . \end{matrix}$

Here is now our definition (from [8]) that provides the context for defining algorithmically random structures:
Definition 2.7.
The class $K$ together with the height function h is called a branching class, or B-class for short, if for all $A \in K$ of height i there exist distinct structures $B, C \in K$ such that $h (B) = h (C) > h (A)$ and $B [i] = C [i] = A$ . If a class $K$ is a B-class, then we refer to the class $K_{ω}$ also as a B-class.

We use the following examples of B-classes. The first two examples are from [9]. Many more examples are in [8].
Example 1 (Rooted trees).

Consider the class $T r e e_{d}$ of all finite rooted trees T such that every node of T has not more than d immediate successors. The height $h (T)$ of T is the length of the longest path from the root to the leaves of T. The gives a B-class.

Example 2 (c-generated algebras).

An algebra $A$ is a tuple $(A; f_{1}, \dots, f_{n}, c_{1}, \dots, c_{m})$ , where $A \neq \emptyset$ is the domain of $A$ , each $f_{i} : A^{k_{i}} \to A$ is a total function called an atomic operation of arity $k_{i}$ , and each $c_{j}$ is a constant of $A$ . The algebra $A$ is c-generated if every element a of $A$ is the interpretation of some ground term t. Call the term t a representation of a.

We define the height $h (t)$ of a ground term t: if $t = c_{i}$ then $h (t) = 0$ ; if $t = f_{i} (t_{1}, \dots, t_{k_{i}})$ , then $h (t) = max {h (t_{1}), \dots, h (t_{k_{i}})} + 1$ . The height $h (a)$ of the element $a \in A$ is the minimal height among the heights of all the ground terms representing a. The height $h (A)$ of the algebra $A$ is the supremum of all the heights of its elements.

For a c-generated algebra $A$ and $n \in ω$ , we define: $A (n) = {a \in A ∣ h (a) ⩽ n}$ . Each $k_{i}$ -ary operation $f_{i}$ of $A$ defines the partial operation $f_{i, n}$ on $A (n)$ : $f_{i, n} (a_{1}, \dots, a_{k_{i}}) = f_{i} (a_{1}, \dots, a_{k_{i}})$ if $h (a_{i}) < n$ for $i = 1, \dots, k_{i}$ , and else undefined.

Call the partial algebras of the form $A (n)$ proper partial algebras. The term “proper” refers to the fact in $A (n)$ we do not decide the operations on elements of height n, even if the result is also of height n (this is vital to make the class branching). Define the height of $A (n)$ to be n. Every infinite c-generated algebra $A$ is the direct limit of the sequence ${A (n)}_{n \in ω}$ . Define: $\begin{matrix} PAlg = {B ∣ B is a proper partial algebra} . \end{matrix}$ The class $PAlg$ is a B-class. The class ${PAlg}_{ω}$ consists of all c-generated infinite algebras.

Example 3 (Binary rooted ordered trees).

Let $O T (2)$ be the class of all binary rooted trees where the children of internal node are linearly ordered. Since the trees are binary, every internal node has either left-child or right-child. These trees have signature $σ = (L, R, c)$ , where c is the root, $L (x, y)$ indicates that y is the left child of x, and $R (x, y)$ that y is the right child of x. The class $O T (2)$ is a B-class.

3. Topology and measure

In this section we will review the definition of a random structure from [8,9]. Let $K$ be a branching class, $r_{K} (n)$ be the number of structures in $K$ of height n. We define the tree $T (K)$ .

The root of $T (K)$ is the empty set. This is level $- 1$ . The nodes of $T (K)$ at level $n ⩾ 0$ are all structures from $K$ of height n. There are exactly $r_{K} (n)$ of them. Let $B$ be a structure from $K$ of height n. Its successors in $T (K)$ are the structures $C$ of height $n + 1$ such that $B = C [n]$ .

To generate a random structure, we randomly choose a height zero structure, and then a height one structure extending that, a height two structure extending that, and so on, to obtain the structure which is the union of all of them. This corresponds essentially to picking a random path through the tree $T (K)$ . We need to show that this tree is effective, following which we will put a probability measure on paths through the tree, similar to the way in which one puts a measure on $2^{ω}$ when considering binary strings.

The proof of the next lemma is easy:

Lemma 3.1 (Computable tree lemma).

For $T (K)$ we have the following:

Given a node x of $T (K)$ , we can effectively compute the structure $B_{x}$ associated with x. We identify the nodes x and the structures $B_{x}$ .

For each node x in $T (K)$ , the structure $B_{x}$ has an immediate successor. Moreover, we can compute the number of immediate successors of x.

For each path $η = B_{0}, B_{1}, \dots$ in $T (K)$ we have: $B_{0} \subset B_{1} \subset \dots$ . Thus, the union of this chain determines the structure $B_{η} = ⋃_{i} B_{i} \in K_{ω}$ .

The mapping $η \to B_{η}$ is a bijection between all infinite paths of $T (K)$ and the class $K_{ω}$ .

For $A \in K_{ω}$ , let $A [i]$ be the largest substructure of $A$ of height i. This is well-defined. The structure $A [i]$ contains all substructures of $A$ of height $⩽ i$ .

Using the tree $T (K)$ we introduce topology in $K_{ω}$ :

Definition 3.2 (Topology).

For $B \in K$ , set: $\begin{matrix} Cone (B) = {A ∣ A \in K_{ω}, and A [n] = B} . \end{matrix}$ These are base open sets. Call $B$ the base of the cone.

We now define the following measures on $K_{ω}$ :

Definition 3.3 (Measure).

For the root r, define $μ (Cone (B_{r})) = 1$ . Let $B_{x} \in K$ be of height n. Let $e_{x}$ be the number of immediate successors of $B_{x}$ in the tree $T (K)$ . For any immediate successor y of x, set $μ (Cone (B_{y})) = μ (Cone (B_{x})) / e_{x}$ .

Definition 3.4 (Metric).

For structures $A, C \in K_{ω}$ , let n be the maximal level at which $A [n]$ and $C [n]$ coincide. Let $B$ be the node of the tree such that $A [n] = B$ . The distance $d_{μ} (A, C)$ between $A$ and $C$ is then: $d_{μ} (A, C) = μ (Cone (B))$ .

The space $K_{ω}$ has the following properties: (1) The function d is a metric on $K_{ω}$ ; (2) $K_{ω}$ is compact; (3) Finite unions of cones form clopen sets in the topology; (4) All μ-measurable sets is a σ-algebra.

Now we define ML-random structures in $K_{ω}$ using definitions from algorithmic randomness. A class $C \subseteq K_{ω}$ is a $Σ_{1}^{0}$ -class if there is a computably enumerable (c.e.) sequence $B_{0}, B_{1}, \dots$ of structures from $K$ such that $C = ⋃_{i ⩾ 1} Cone (B_{i})$ .

Definition 3.5.
Let $K$ be a B-class. Consider the class $K_{ω}$ of infinite structures.
A Martin-Löf (ML) test is a uniformly c.e. sequence ${G_{n}}_{n \in ω}$ of $Σ_{1}^{0}$ -classes with $G_{n + 1} \subset G_{n}$ and $μ (G_{n}) < 2^{- n}$ for all n.

A structure $A$ from $K_{ω}$ fails a ML-test ${G_{n}}_{n \in ω}$ if $A$ belongs to $⋂_{n} G_{n}$ . Otherwise, we say that the structure $A$ passes the test.

A structure $A$ from $K_{ω}$ is ML-random if it passes every Martin-Löf test.
If $C \subset K_{ω}$ is contained in a ML-test, then we say that C has effective measure 0.

It is standard to show that there is a universal ML-test in the sense that passing that test is equivalent to passing all ML-tests [17]. Formally, a ML-test ${U_{n}}_{n \in ω}$ is universal if for any ML-test ${G_{m}}_{m \in ω}$ it is the case that $⋂_{m} G_{m} \subseteq ⋂_{n} U_{n}$ . A construction of a universal ML-test is easy: list all ML-tests ${G_{k}^{e}}_{k \in ω}$ uniformly on e and k, and set $U_{n} = ⋃_{e} G_{n + e + 1}^{e}$ . The resulting sequence ${U_{n}}_{n \in ω}$ is a universal ML-test. Hence, to prove that a structure $A \in K_{ω}$ is ML-random it suffices to show that $A$ passes the universal ML-test ${U_{n}}_{n \in ω}$ . The class of non-ML-random structures has effective measure 0. Thus, we have: Theorem 3.6 (Theorem 6.7 of [8]).

Let $K$ be a B-class. The number of ML-random structures in $K_{ω}$ is continuum.

4. Randomness and the halting set

We study elementary effective aspects of ML-random structures from $K_{ω}$ . We start with the following definition that goes back to Malcev [15] and Rabin [18].

Definition 4.1.
An infinite structure $A$ is computable if it is isomorphic to a structure with domain ω such that all atomic operations and relations of the structure are computable.

Computability is an isomorphism property. A structure is computable iff it is isomorphic to a structure that has a computable open diagram. A stronger definition that involves the height function and fits the setting of this paper is this:
Definition 4.2.
A computable structure $A$ from $K_{ω}$ is strictly computable if the size of the substructure $A [i]$ can be effectively computed for all $i \in ω$ .

Strict computability implies non ML-randomness:
Theorem 4.3 (Lemma 6.11 of [8]).

If $A$ is strictly computable then $A$ is not ML-random.

Proof.
There exists an effective procedure that given n computes the structure $A [n]$ . Hence, for an appropriately chosen sequence ${(n_{i})}_{i \in ω}$ , the sequence of cones $Cone (A [n_{0}]), Cone (A [n_{1}]), Cone (A [n_{2}]), \dots$ forms a Martin-Löf test that the structure $A$ fails. □

We derive several corollaries. The first corollary is the following logical property of ML-random structures. For $A \in K_{ω}$ consider the binary predicate L: $\begin{matrix} L (x, y) iff x \in A [i] ⟺ y \in A [i] for all i ⩾ 0 . \end{matrix}$
Definition 4.4.
Call L the level predicate. Extend $A$ with L thus defining the extended structure $(A, L)$ .

The extension $(A, L)$ of $A$ is a natural extension in the sense that the automorphism group of $A$ coincides with the automorphism group of $(A, L)$ .
Corollary 4.5 (Corollary 6.12 of [8]).

If $(A, L)$ is a computable structure and the ∃-theory of $(A, L)$ , that is the set $\begin{matrix} {ϕ ∣ (A, L) ⊧ ϕ and ϕ is an existential first-order sentence}, \end{matrix}$ is decidable, then $A$ is not ML-random.

Proof.
We can determine the elements of $K$ of height i, and for each such finite structure $B$ we can construct an existential sentence stating that $B$ is a substructure of $A$ . Thus we can determine the substructures of $A$ of height i. The largest is $A [i]$ , allowing us to effectively compute $A [i]$ for all i. □

The second property concerns c-generated algebras:
Corollary 4.6.
No computable c-generated ML-random algebra exists.
Proof.
If $A$ is c-generated, then one computes $A [i]$ for any given i. Hence, $A$ is strictly computable. □

In particular, we have the following property for classical algebraic structures such as groups and rings:
Corollary 4.7.
No finitely generated computable group or ring exists that is ML-random.
Proof.
Say G is a finitely generated group with generators a and b. We can view G as a universal algebra with generators a and b (from the signature). Hence, since G is computable, for each i we can compute the domain $G [i]$ . Hence, G is strictly computable. □

The next property concerns connected graphs:
Definition 4.8.
A connected computable locally finite graph $G = (ω, E)$ is highly computable if for each $v \in G$ we can effectively compute all neighbours (that is, the set ${u ∣ {v, u} \in E}$ ) of v.

In order to form a B-class of locally finite connected graphs, one must fix a vertex as the origin and add a constant for this vertex to the language. However, it is shown in [9] that the randomness of a such a graph does not depend on the choice of constant, and so we shall speak of random locally finite connected graphs, rather than random locally finite connected pointed graphs.
Corollary 4.9.
No connected highly computable graph G is ML-random.
Proof.
For each fixed vertex g in the graph G, the naturally defined height function $\begin{matrix} f (v) = the shortest distance from v to g \end{matrix}$ is computable since G is highly computable. In any branching class $K$ of graphs (as formally defined in [8]), the height function for the class $K$ is compatible with the height function f defined above. Now note that for each i we can compute $G [i]$ (that is all vertices at distance $⩽ i$ from g). Therefore, G is strictly computable, and hence G is not ML-random. □

Note that the hypotheses of the theorem and all the corollaries above depend only on the structures chosen, and not on the branching classes $K_{ω}$ . Namely, if $A$ is strictly computable and $A \in K_{ω}$ (no matter what the branching class $K$ is) then $A$ is not ML-random in the class $K_{ω}$ . Thus, non-randomness of strictly computable structures is context independent.
Definition 4.10.
A structure $A$ is $0^{'}$ -computable if it is isomorphic to a structure with domain ω such that all atomic relations, including equality, and operations of $A$ are computable in $0^{'}$ .

Each computable structure is $0^{'}$ -computable. The reverse is false: there are finitely presented groups with undecidable word problem. The next theorem shows that Theorem 4.3 can’t be extended to $0^{'}$ -computable structures. Theorem 4.11 (Theorem 6.14 of [8]).

Every branching class $K_{ω}$ contains a $0^{'}$ -computable ML-random structure.

Proof.
Consider the mapping $η \to A_{η}$ that maps all paths of the tree onto the structures $K_{ω}$ . The mapping $η \to A_{η}$ is such that the structure $A_{η}$ is a computable operator. Hence $A_{η}$ is computable in any oracle that computes η. It is standard to show that there exists an ML-random path η in the tree such that η is computable in the halting set $0^{'}$ [3,17]. Hence the structure $A_{η}$ is computable in $0^{'}$ . □

5. Randomness and computability

For any structure $A$ from a branching class $K_{ω}$ there is a path $η \in T (K)$ such that the structure $A_{η}$ (determined by η) is isomorphic to $A$ . As we noted the path η can be constructed in the jump of the open diagram of $A$ . In particular, if $A$ is computable then η is computable in the halting set $0^{'}$ . We exploit this observation to prove the following theorem.

Theorem 5.1 (Theorem 7.1 of [8]).

There exists a branching class $S_{ω}$ that has a computable ML-random structure.

The proof we give here is better than that from [8]; in particular, it highlights certain combinatorial properties of the branching class which we will motivate results later in the paper.

Proof.
Consider the full binary tree $T = {0, 1}^{⋆}$ (whose elements are finite binary strings). The signature of this tree consists of the root symbol c and two binary predicates L and R such that $L (x, y)$ if and only if $y = x 0$ and $R (x, y)$ if and only if $y = x 1$ .

Let ⪯ be the lexicographic order. For each $x \in {0, 1}^{⋆}$ consider the structure $B_{x}$ whose domain consists of all strings y such that $| y | ⩽ | x |$ and $y ⪯ x$ . Clearly $B_{x}$ is a tree in the signature $(c, L, R)$ .

We set $S = {B_{x} ∣ x \in {0, 1}^{⋆}}$ . The height function of the class $S$ associates with every structure $B_{x}$ the length $| x |$ of x. Obviously, $S$ is a branching class; also, $T (S)$ can naturally be identified with the binary tree $T = {0, 1}^{⋆}$ . We have the following easy lemma: Lemma 5.2 (Algebraic left-embedding lemma).

Suppose that $x ⪯ y$ . Then:

If $| x | ⩽ | y |$ then $B_{x}$ is embedded into $B_{y}$ .

If $| x | > | y |$ then $B_{x}$ is embedded into $B_{y z}$ for all z such that $| x | ⩽ | y z |$ and $x ⪯ y z$ .

Let ${U_{n}}_{n \in ω}$ be the universal ML-test. Consider the set ${0, 1}^{ω} ∖ U_{1}$ . All infinite paths in this set are paths through a computable binary tree. Let η be the leftmost infinite path of the tree. The path is a ML-random path. So, the structure $B_{η}$ is ML-random. The path is effectively approximable from the left.

Let $x_{0} ⪯ x_{1} ⪯ x_{2} ⪯ \dots$ be computable approximation to η such that $| x_{i} | < | x_{i + 1} |$ . By the lemma above we have a computable sequence of embedded structures: $B_{x_{0}} \subset B_{x_{1}} \subset \dots$ . The direct limit of this structure is isomorphic to $B_{η}$ . Thus we have built a ML-random structure which is computable. □

In the introduction, we remarked that a ML-random string cannot be computable, and yet by the theorem ML-random structures can be computable. The issue is that an ML-random structure is not sufficiently random to preclude being computable just as an ML-random string is not sufficiently random to preclude being computable in the halting set. Nevertheless, below we show that no computable structure is 2-ML-random.

Definition 5.3.
Consider a B-class $K_{ω}$ . One defines what it means for a structure $A$ from the class $K_{ω}$ to be 2-ML-random by replacing the $Σ_{1}^{0}$ -classes in the definition of ML-randomness by $Σ_{1}^{0}$ -classes relative to the halting set $0^{'}$ .

Clearly, 2-ML-randomness implies ML-randomness. The theorem below shows that 2-ML-randomness precludes computable structures to be 2-ML-random (just like ML-randomness for strings precludes ML-random strings to be computable). Theorem 5.4.
If structure $A$ is computable then $A$ is not 2-ML-random.
Proof.
The proof is just recasting of the proof of Theorem 4.3 with an oracle for $0^{'}$ . There is a $0^{'}$ -computable function that computes, for each n, the finite structure $A [n]$ . Then we can use the same argument as in Theorem 4.3: for an appropriately chosen sequence ${(n_{i})}_{i \in ω}$ , the sequence of cones $Cone (A [n_{0}]), Cone (A [n_{1}]), \dots$ forms a Martin-Löf test relative to $0^{'}$ that the structure $A$ fails. □

6. Co-c.e. and c.e. ML-random algebras

Our interest is in ML-random c-generated algebras as explained in Example 3. From Corollary 4.6 no finitely generated computable algebra is ML-random. But we also know, from Theorem 4.11, that the class contains ML-random structures computable in the halting set. It is not too hard to see that the word problem in such an ML-random algebra is always a $Δ_{2}^{0}$ -set. Thus, a natural question is whether it is possible to sharpen these results. We sharpen these results by showing that there exist computably enumerable as well as co-computably enumerable ML-random algebras. Clearly, the word problems in such algebras are $Σ_{1}^{0}$ and $Π_{1}^{0}$ -sets.

Formally, the word problem is defined as follows. Let $A$ be a c-generated algebra. Elements of this algebra are represented by ground terms. The word problem for algebra $A$ refers to the set $\begin{matrix} {(t, p) ∣ t and p are ground terms and A ⊧ t = p} . \end{matrix}$

Definition 6.1.
Let $A$ be a c-generated algebra.
Call $A$ computably enumerable if the word problem for $A$ is computably enumerable.

Call $A$ co-computably enumerable if the word problem for $A$ is co-computably enumerable.

There are a plethora of examples of c.e. and co-c.e. algebras. For instance, all finitely presented groups (in fact, all finitely presented algebras) are c.e. algebras. An example of a co-c.e. algebra is any group generated by finitely many computable permutations of ω. Every c.e. or co-c.e. algebra is computable in the halting set $0^{'}$ . So, the next theorem strengthens Theorem 4.11 for the class of algebras. Theorem 6.2.
There is a branching class of finitely generated algebras that contains a co-computably enumerable ML-random structure.
Proof.
Consider the B-class $K$ of all finite ordered trees T as where each non-leaf node has at most two children. The children of the node are ordered from left to right. Order the nodes of the tree T on the same level (from left to right) in the natural way. We call to this order the level order of the nodes. The tree T is a structure in the signature $(c, L, R)$ .

We now transform any tree T from $K$ into a partial-tree algebra $A (T)$ as follows. The signature of $A (T)$ has unary operation L and R, and the generator, or constant, c (root). The domain of $A (T)$ is T. Operations L and R are defined as follows. For a leaf x, $L (x)$ and $R (x)$ are undefined. For a non-leaf node x, if x has a left child y and right child z then $L (x) = y$ and $R (x) = z$ . If x has one child only, say y, then $L (x) = R (x) = y$ . This transformed the tree T to the partial algebra $A (T)$ . We identify T with $A (T)$ .

To define the desired class S, consider the concatenation operations on partial tree–algebras $T_{1}$ and $T_{2}$ . The concatenation of $T_{1}$ and $T_{2}$ , written $T_{1} \cdot T_{2}$ , is obtained by attaching to every leaf of $T_{1}$ the tree $T_{2}$ and by identifying the leaf with the root of $T_{2}$ . Formally, the domain of $T_{1} \cdot T_{2}$ is the set $T_{1} ∖ {x ∣ x is a leaf of T_{1}} \cup {(v, x) ∣ x is a leaf of T_{1} and v \in T_{2}}$ . The L and R operations on $T_{1}$ are inherited from the original L and R. For elements $(v, x)$ , we have $L (v, x) = (v^{'}, x)$ if $L (v) = v^{'}$ and $R (v, x) = v^{″}$ if $R (v) = v^{″}$ .

We need some notation: denote the full binary partial-tree algebra of height k by $T_{k}$ ; the tree $L_{k}$ denotes the partial tree-algebra isomorphic to $({a_{0}, \dots, a_{k}}; L, R)$ where $L (a_{i}) = R (a_{i}) = a_{i + 1}$ for $i < k$ , and the root is $a_{0}$ ; finally, $A_{k, i}$ denotes the partial tree-algebra $L_{k - i} \cdot T_{i}$ , where $i ⩽ k$ . Lemma 6.3.
The partial tree-algebras $A_{k, 0}, A_{k, 1}, \dots, A_{k, k}$ have the same height. In addition, each partial algebra $A_{k, i}$ is a homomorphic image of the partial algebra $A_{k, i + 1}$ , and the homomorphism is unique.

We define, by induction, our branching class $S$ by directly constructing the tree $T (S)$ that represents structures from $S$ . At stage n we define partial-tree algebras at level n of the tree $T (S)$ . We also define an ordering on the elements of level n.

Stage 0. The root of $T (S)$ is the partial-tree algebra $L_{0}$ (and so, the root is also $T_{0}$ ).

Stage $n + 1$ . Suppose we constructed partial tree-algebras $B_{1}, \dots, B_{2^{n}}$ at level n of the tree $T (S)$ , listed from left to right. At level n the tree $T (S)$ has exactly $2^{n + 1}$ nodes. Namely, each node (partial tree-algebra) $B_{i}$ has exactly two immediate successors: $B_{i} \cdot A_{2^{n}, i - 1}$ and $B_{i} \cdot A_{2^{n}, i}$ . We order $B_{i} \cdot A_{2^{n}, i - 1}$ to the left of $B_{i} \cdot A_{2^{n}, i}$ . For $j < i$ , we order the successors of $B_{j}$ to the left of the successors of $B_{i}$ .

Thus, the class $S$ consists of all partial tree-algebras T that appear at some stage n of the construction above. All the partial tree-algebras at level n of the tree $T (S)$ are defined to have height n. We provide several lemmas about the partial tree-algebras of the class $S$ . The next lemma is obvious: Lemma 6.4.
The class $S$ is a B-class. Moreover, the tree $T (S)$ is isomorphic to the infinite binary tree.

From this lemma above we immediately get: Lemma 6.5.
For all $B \in S$ , $μ (Cone (B)) = 2^{- h (B)}$ .

The next lemma proves an algebraic property of tree-algebras of height n. Lemma 6.6.
If $B_{1}, \dots, B_{2^{n}}$ are the partial tree-algebras at level n of $T (S)$ listed from left to right, then each $B_{i}$ is a homomorphic image of $B_{i + 1}$ . Further, each homomorphism is unique.
Proof.
The proof is by induction on n. When $n = 0$ the statement is clear. Assume that we have proved the lemma for all trees $B_{1}, \dots, B_{2^{n}}$ that correspond to nodes at level n of the tree $T (S)$ . Consider $B_{i}$ . This has exactly two immediate successors: $B_{i} \cdot A_{2^{n}, i - 1}$ and $B_{i} \cdot A_{2^{n}, i}$ . By Lemma 6.3 there is a unique homomorphism from $A_{2^{n}, i}$ onto $A_{2^{n}, i - 1}$ . Hence, there exists a homomorphism from $B_{i} \cdot A_{2^{n}, i}$ onto $B_{i} \cdot A_{2^{n}, i - 1}$ . It is clearly unique.

Consider $B_{i - 1} \cdot A_{2^{n}, i - 1}$ , which is the element at level $n + 1$ immediately to the left of $B_{i} \cdot A_{2^{n}, i - 1}$ . There is a unique homomorphism $h_{i}$ , by inductive hypothesis, from $B_{i}$ onto $B_{i - 1}$ . This implies that there exists a unique homomorphism from $B_{i} \cdot A_{2^{n}, i - 1}$ onto $B_{i - 1} \cdot A_{2^{n}, i - 1}$ . This proves that all the partial tree-algebras at level n of $T (S)$ form a chain of homomorphically embedded structures. □

Thus there is a natural bijection $x \to A_{x}$ from the set of all binary strings onto the class $S$ . We identify the tree $T (S)$ with the full binary tree. Corollary 6.7.
If $x ⪯ y & | x | = | y |$ , then $A_{y}$ is homomorphically mapped onto $A_{x}$ .

Let ${U_{n}}_{n \in ω}$ be the universal ML-test in the class $S_{ω}$ (which we identify with the Cantor space ${0, 1}^{ω}$ ). Consider the set ${0, 1}^{ω} ∖ U_{1}$ . Since $μ (U_{1}) < 1 / 2$ , all infinite paths in ${0, 1}^{ω} ∖ U_{1}$ can be considered as paths through a computable binary tree. Let η be the leftmost infinite path of the tree.

Let $x_{0} ⪯ x_{1} ⪯ x_{2} ⪯ \dots$ be computable approximation to η such that $| x_{i} | < | x_{i + 1} |$ . We have the sequence of partial tree-algebras: $A_{x_{0}}, A_{x_{1}}, A_{x_{2}}, \dots$ . The direct limit of this structure is isomorphic to $B_{η}$ . This structure is ML-random. Our goal is to show that $B_{η}$ is a co-c.e. algebra.

Consider all terms of the signature $⟨ L, R, c ⟩$ built from the constant c and operation symbols L and R: $c, L (c), R (c), L L (c), L R (c), R L (c), \dots$ . The set of all terms forms an algebra; in this algebra for terms t the values of L and of R on t are terms $L (t)$ and $R (t)$ . This is known as the term algebra $Term$ . The algebra $B_{η}$ is a homomorphic image of the term algebra $Term$ . Let $g : Term \to B_{η}$ be the onto homomorphism, and let $E = {(t, q) ∣ g (t) = g (q)}$ be the kernel of the homomorphism. The quotient algebra $Term / E$ is isomorphic to $B_{η}$ . It suffices to explain why E is a co-c.e. relation.

To show that E is co-c.e. consider the partial algebra $A_{x_{n + 1}}$ in the sequence above. We can assume that we have an equivalence relation $E_{n}$ on the partial algebra $T_{k (n)}$ such that the factor structure $T_{k (n)} / E_{n}$ is isomorphic to $A_{x_{n}}$ . At stage $n + 1$ either $A_{x_{n + 1}}$ extends $A_{x_{n}}$ or $A_{x_{n}}$ is a substructure of a homomorphic image of $A_{x_{n + 1}}$ . In the second case some $E_{n}$ -equivalent elements become non- $E_{n + 1}$ -equivalent. These elements can effectively be computed. If two elements are not $E_{n}$ -equivalent then they will never be $E_{m}$ -equivalent for all $m ⩾ n$ . So, non-equality in the algebra $Term / E$ is co-c.e. □
Theorem 6.8.
There exists a branching class of finitely generated algebras that contains a computably enumerable ML-random structure.
Proof.
The proof of Theorem 6.2 can be changed slightly to construct the desired algebra. Simply replace η with the rightmost infinite path, say $1 - η$ , which instead of being computable from the left below, is computable from the right. Consider an effective sequence of strings $y_{0} ⪰ y_{1} ⪰ y_{2} ⪰ y_{3} ⪰ \dots$ that converges to $1 - η$ from the right. The resulting structure $B_{1 - η}$ is a desired algebra. This is because, by Corollary 6.7, whenever we move from $A_{y_{n}}$ to $A_{y_{n + 1}}$ , we pass to a homomorphic image and then extend. □

7. Degrees of random structures

In this section we study Turing degrees of algorithmically random structures in branching classes $K_{ω}$ .

Definition 7.1.
For a structure $A$ , the degree of $A$ is the least Turing degree computing an isomorphic copy of $A$ , if such degree exists.

Degrees of structures play important role in understanding effective aspects of structures and their interactions with model theory [10,19,23]. Here we show that the degrees of ML-random structures depend on the underlying branching classes $K_{ω}$ . Here is one natural example of branching classes:
Definition 7.2.
A branching class $K$ is jumpless if for every path η in $T (K)$ , every isomorphic copy of $A_{η}$ computes η.

For instance, the class of c-generated algebras is jumpless. There are many other examples of jumpless classes among graphs and trees. The following proposition is easy to prove:
Proposition 7.3.
If the class $K_{ω}$ is jumpless, then every structure in $K_{ω}$ has a degree, and the degrees of ML-random structures in the class are precisely the Turing degrees which contain random binary strings.

Motivated by the algebraic left-embedding lemma (Lemma 5.2), we give the next definition:
Definition 7.4.
A B-class $K$ is left-algebraic if there is a computable ordering on the elements of each level of $T (K)$ such that for the induced lexicographic ordering ⪯ the following holds:
For every path η through $T (K)$ , for every sequence $x_{0} ⪯ x_{1} ⪯ x_{2} ⪯ \dots$ with limit η, the sequence computes an isomorphic copy of $A_{η}$ .

For every path η through $T (K)$ , for every isomorphic copy of $A_{η}$ , the copy computes a sequence $x_{0} ⪯ x_{1} ⪯ x_{2} ⪯ \dots$ with limit η.

An example of a left-algebraic branching class is the class $S$ constructed in the proof of Theorem 5.1.
Theorem 7.5.
If a B-class $K$ is left-algebraic, then the class $K_{ω}$ contains ML-random structures of degree $0$ and $0^{'}$ , but of no other degree.
Proof.
Let ${(U_{n})}_{n \in ω}$ be the universal ML-test for $K$ . Then $μ (U_{1}) < 1 / 2$ , and the elements of $K_{ω} - U_{1}$ are the paths through a computable tree. Let η be the leftmost path. Then there is a computable sequence $x_{0} ⪯ x_{1} ⪯ \dots$ with limit η. Since $K$ is left-algebraic, there is a computable copy of $A_{η}$ . Hence, the class $K_{ω}$ has an ML-random structure of degree 0.

The following fact is analogous to one by Kučera and Slaman [12] for random infinite binary strings, and the proof is similar (see Sections 6.1 and 9.2 of [3]): Lemma 7.6.
If $A_{η} \in K_{ω}$ is ML-random and there is a computable sequence $x_{0} ⪯ x_{1} ⪯ x_{2} ⪯ \dots$ with limit η, or a computable sequence $x_{0} ⪰ x_{1} ⪰ x_{2} ⪰ \dots$ with limit η, then η has degree $0^{'}$ .

The path η in this lemma should not be confused with the sequence $x_{0} ⪯ x_{1} ⪯ x_{2} ⪯ \dots$ ; we do not, in general, expect them to have the same Turing degree.

Now consider the computable tree for which the paths are elements of $K_{ω} - U_{1}$ , and let η be the rightmost path. There exists a computable sequence $x_{0} ⪰ x_{1} ⪰ x_{2} ⪰ \dots$ converging to η. Since $K$ is left-algebraic, every isomorphic copy of $A_{η}$ computes a sequence ${\hat{η}}_{0} ⪯ {\hat{η}}_{1} ⪯ {\hat{η}}_{2} ⪯ \dots$ with limit η. So every isomorphic copy of $A_{η}$ computes η as follows: for an input i, search for an ℓ such that $η_{ℓ} [j] = {\hat{η}}_{ℓ} [j]$ for all $j ⩽ i$ . Such an ℓ must exist. Then $η_{ℓ} [i] = η [i]$ . Since η has degree $0^{'}$ , this shows that $A_{η}$ has degree $0^{'}$ . So, $K_{ω}$ contains a random structure of degree $0^{'}$ .

Thus, the class $K_{ω}$ has ML-random structures of degrees $0$ and $0^{'}$ . To show that no other random degrees are possible, we need a deeper analysis provided by the next lemmas. Lemma 7.7.
If $A_{η} \in K_{ω}$ and $A_{η}$ has a degree, then there is a sequence $η_{0} ⪯ η_{1} ⪯ η_{2} ⪯ \dots$ with limit η and a computably enumerable set $F \subset ω \times K \times K$ such that $η_{n} = x$ iff there is a $y ⪯ η$ with $(n, x, y) \in F$ .
Proof.
Consider an isomorphic copy $B$ of $A_{η}$ realising the degree of the structure $A_{η}$ . Since $K$ is left-algebraic, this copy computes a sequence $(η_{0} ⪯ η_{1} ⪯ η_{2} ⪯ \dots)$ with limit η. From now on we fix this sequence. As $B$ realises the least degree, every other copy of $A_{η}$ computes this fixed sequence $(η_{0} ⪯ η_{1} ⪯ η_{2} ⪯ \dots)$ . Also, every other sequence $(ρ_{0} ⪯ ρ_{1} ⪯ ρ_{2} ⪯ \dots)$ with limit η computes a copy of $A_{η}$ . Hence, the sequence $(ρ_{0} ⪯ ρ_{1} ⪯ ρ_{2} ⪯ \dots)$ also computes the specified sequence $(η_{0} ⪯ η_{1} ⪯ η_{2} ⪯ \dots)$ .

The idea is now the following. We will attempt to build a sequence $(ρ_{0} ⪯ ρ_{1} ⪯ ρ_{2} ⪯ \dots)$ with limit η which does not compute $(η_{0} ⪯ η_{1} ⪯ η_{2} ⪯ \dots)$ . Any such attempt must fail, and we use this failure to construct the desired c.e. set F.

Let ${(Φ_{i})}_{i \in ω}$ be an effective listing of all Turing functionals, and let ${(σ_{i})}_{i \in ω}$ be a listing of the elements of $T (K)$ such that $σ_{i} ⪯ η$ for all i. We construct $(ρ_{0} ⪯ ρ_{1} ⪯ ρ_{2} ⪯ \dots)$ in stages, although we do not claim that our construction is effective.

Stage 0. We begin by letting $ρ_{0} = σ_{0}$ .

Stage $2 i + 1$ . Suppose we defined $ρ_{0}$ through $ρ_{k_{2 i}}$ . At this stage, we must ensure that $Φ_{i}$ does not compute $(η_{0} ⪯ η_{1} ⪯ η_{2} ⪯ \dots)$ . To ensure this, we search for an n and a finite sequence $(τ_{1} ⪯ τ_{2} ⪯ \dots ⪯ τ_{m})$ such that $ρ_{k_{2 i}} ⪯ τ_{1}$ , $τ_{m} ⪯ η$ and $\begin{matrix} Φ_{i}^{(ρ_{0} ⪯ \dots ⪯ ρ_{k_{2 i}} ⪯ τ_{1} ⪯ \dots ⪯ τ_{m})} (n) is defined and this value is not equal to η_{n} . \end{matrix}$ Define $ρ_{k_{2 i} + j} = τ_{j}$ for $1 ⩽ j ⩽ m$ . Otherwise, we make no new definitions at this stage.

Stage $2 i + 2$ . Suppose we have defined $ρ_{0}$ through $ρ_{k_{2 i + 1}}$ . At this stage, we must ensure that our sequence surpasses $σ_{i}$ without exceeding η. We define $ρ_{k_{2 i + 1} + 1} = σ_{i}$ if $ρ_{k_{2 i + 1}} ⪯ σ_{i}$ . Otherwise, we make no new definitions at this stage.

Note that even numbered stages guarantee that the limit of $(ρ_{0} ⪯ ρ_{1} ⪯ ρ_{2} ⪯ \dots)$ is η. As we argued earlier, this sequence computes the specified sequence $(η_{0} ⪯ η_{1} ⪯ η_{2} ⪯ \dots)$ . Therefore there must exists the least i such that $\begin{matrix} Φ_{i}^{(ρ_{0} ⪯ ρ_{1} ⪯ \dots)} (n) = η_{n} for all n . \end{matrix}$

Consider now the way the construction acts at stage $2 i + 1$ . There must be no sequence $(τ_{1} ⪯ \dots ⪯ τ_{m})$ as desired. Now we define F. A triple $(n, x, y)$ belongs to F iff there is a sequence $(τ_{1} ⪯ \dots ⪯ τ_{m})$ with $Φ_{i}^{(ρ_{0} ⪯ \dots ⪯ ρ_{k_{2 i}} ⪯ τ_{1} ⪯ \dots ⪯ τ_{m})} (n) = x$ and $τ_{m} = y$ . Observe that F is computably enumerable. We now argue that F has the desired properties.

Suppose $(n, x, y) \in F$ and $y ⪯ η$ . Then there is some sequence $(τ_{1} ⪯ \dots ⪯ τ_{m})$ which witnessed that $(n, x, y)$ belongs in F. If $η_{n} \neq x$ , then this sequence is as desired for Stage $2 i + 1$ , contrary to our choice of i. So $η_{n} = x$ .

Conversely, suppose $η_{n} = x$ . There is an m with $Φ_{i}^{(ρ_{0} ⪯ \dots ⪯ ρ_{k_{2 i} + m})} (n) = x$ . Define the sequence $(τ_{1} ⪯ \dots ⪯ τ_{m})$ by $τ_{j} = ρ_{k_{2 i} + j}$ , where $j = 1, \dots, m$ . This sequence witnesses that $(n, x, ρ_{k_{2 i} + m}) \in F$ , and $ρ_{k_{2 i} + m} ⪯ η$ . □
Lemma 7.8.
If $A_{η} \in K_{ω}$ has a degree, then either there is a computable sequence $(ρ_{0} ⪰ ρ_{1} ⪰ \dots)$ with limit η, or there is $(η_{0} ⪯ η_{1} ⪯ \dots)$ a computable sequence with limit η.
Proof.
Consider the set F and the sequence $(η_{0} ⪯ η_{1} ⪯ \dots)$ as in the previous lemma and its proof. We attempt to effectively construct $(ρ_{0} ⪰ ρ_{1} ⪰ \dots)$ as stated in the lemma. If this fails, we will be able to argue that $(η_{0} ⪯ η_{1} ⪯ \dots)$ is a computable sequence. We proceed in stages, building $ρ_{n}$ at stage n.

Stage n. We enumerate F until we see two triples $(m, x_{0}, y_{0})$ and $(m, x_{1}, y_{1})$ with $x_{0} \neq x_{1}$ and $y_{0} ⪯ y_{1}$ . If $n > 0$ , we also require $ρ_{n - 1} ⪰ y_{1}$ . If we find such a pair of triples, we know that $η ≺ y_{1}$ . Otherwise, we would have $y_{0} ⪯ y_{1} ⪯ η$ , and so by the nature of F, we would have $x_{0} = η_{m} = x_{1}$ . We set $ρ_{n} = y_{1}$ for the first pair of triples we find.

Now, suppose that for every $z ≻ η$ , there is a pair of triples $(m, x_{0}, y_{0})$ and $(m, x_{1}, y_{1})$ as above with $z ⪰ y_{1}$ . Then our construction will always find such a pair, and we will eventually define a $ρ_{n} ⪯ z$ for every such z. So we will have $(ρ_{0} ⪰ ρ_{1} ⪰ \dots)$ with limit η.

Suppose instead there is a $z ≻ η$ such that there is no pair of desired triples with $z ⪰ y_{1}$ . We know that for every m there is a triple $(m, x_{0}, y_{0})$ with $y_{0} ⪯ η ≺ z$ and $x_{0} = η_{m}$ . So it must be that there is no triple $(m, x_{1}, y_{1})$ with $y_{1} ⪯ z$ and $x_{1} \neq η_{m}$ . Then we can compute $η_{n}$ by enumerating F until we see a triple $(n, x, y)$ with $y ⪯ z$ . When we see such a triple, we know that $η_{n} = x$ . □

To finish the proof of the theorem, suppose $A_{η} \in K_{ω}$ has a degree and is random. Then there is either a computable sequence $(η_{0} ⪯ η_{1} ⪯ \dots)$ or a computable sequence $(η_{0} ⪰ η_{1} ⪰ \dots)$ with limit η. As we earlier argued, in the first case $A_{η}$ has a computable copy, and in the second case $A_{η}$ has degree $0^{'}$ . □

We do not know anything about the degrees realised by random structures from B-classes which are neither jumpless nor left-algebraic.
8. A branching class of groups

In this section, we build a branching class of finitely generated groups. We want to define a class $K$ of finite partial groups on a fixed set of generators, in the style of Example 3, so that $K_{ω}$ consists of groups. There are two difficulties. First, $K$ cannot include any finite group, as that would violate the branching condition; nor can it include any finite partial group which only has one extension to an infinite group. Second, there is the problem of effectiveness. The class $K$ must be decidable but because the word problem for groups is undecidable, we cannot decide whether a finite partial atomic diagram can be extended to a group.

Our construction uses ideas from [6], namely the application of small cancellation to code structure into a finitely generated groups. We begin by recalling the basic definitions of small cancellation. For a reference on small cancellation, see Chapter 5 of [14].

A presentation $⟨ S ∣ R ⟩$ is symmetrized if every relator in R is cyclically reduced (which means that every cyclic permutation is reduced) and the relator set R is closed under inverses and cyclic permutation. For the symmetrized presentation $⟨ S ∣ R ⟩$ , a word $u \in F (S)$ is a piece if there are two distinct $r_{1}, r_{2} \in R$ such that u is an initial subword of both $r_{1}$ and $r_{2}$ .

Definition 8.1.
The presentation $⟨ S ∣ R ⟩$ has the $C^{'} (λ)$ small cancellation hypothesis if for each $r \in R$ and every piece u with $r = u v$ , we have $| u | < λ | r |$ . We also say that a presentation satisfies the small cancellation hypothesis if it does after we replace the relators set with its symmetrized closure.

The key lemma on small cancellation groups is Greendlinger’s Lemma. It says that in a small cancellation group, every presentation of the trivial word must share a long subword in common with a relator.
Lemma 8.2 (Greendlinger’s Lemma).

Assume that $G = ⟨ S ∣ R ⟩$ is a $C^{'} (λ)$ small cancellation group with $0 ⩽ λ ⩽ 1 / 6$ . Let w be a non-trivial freely reduced word representing e of G. Then there is a subword v of w and a defining relator r such that v is also a subword of r and such that $| v | > (1 - 3 λ) | r |$ .

We are now ready to define the branching class of groups. Given $x \in {0, 1}^{ω}$ , define the group $G_{x}$ generated by $a = a_{0}$ , b, and c. The group $G_{x}$ is such that it is generated with ${a_{i}}_{i \in ω} \cup {b, c}$ and relations

$u (a_{i}, b) = a_{i + 1}$ , and

$u (a_{i}, c) = e$ for each i with $x (i) = 1$ ,

where

u (s, t) = s t s^{2} t s^{3} t \dots s^{100} t

. A standard argument shows that the group

G_{x}

is a

C^{'} (1 / 10)

small cancellation group. Indeed, the length of each relator is greater than 5000. Let r be a relator, and write

r = u v

with

| u | ⩾ 500

. Then u must contain a subword which looks like one of the following for some k, or the inverse of one of the following:

\begin{matrix} b a_{i}^{k} b a_{i}^{k + 1} b \end{matrix}

\begin{matrix} c a_{i}^{k} c a_{i}^{k + 1} c . \end{matrix}

Suppose that u is one of these two; the case of an inverse of one of these two is similar. The first is only a subword of the relator

u (a_{i}, b) = a_{i + 1}

and its cyclic permutations, and the second is only a subword of the relator

u (a_{i}, c) = e

and its cyclic permutation. Moreover, each of these two types of words only appear in one place as a subword of the corresponding relator (including “wrapping around” from the end of the relator to the beginning). Thus the initial segment u of r cannot be an initial segment of any other cyclic permutation of r, and cannot be an initial segment of any other relator other than r. Thus no relator r has a piece u with

| u | ⩾ \frac{1}{10} | r |

Given a group G generated by ${a_{0}, b, c}$ , let $G [i]$ be the finite partial group consisting of the elements represented by words of length at most i (in $a_{0}$ , b, c). It is important to note that we think of $G_{x}$ as being generated by ${a_{i}}_{i \in ω} \cup {b, c}$ when we think of it as a small cancellation group, but as being generated by ${a_{0}, b, c}$ when we consider the lengths of elements. Our branching class is the class of finite partial groups which arise from the groups $G_{x}$ , where $x \in 2^{ω}$ .

Definition 8.3.

Let $K$ be the class of finite partial groups $G_{x} [i]$ where $x \in 2^{ω}$ and $i \in ω$ . The height function on $K$ is $G_{x} [i] \mapsto i$ .

The next two lemmas show that there is a connection between $G_{x} [i]$ and an initial segment of x, with the length of this initial segment depending on i. These lemmas will show that $K$ is a B-class.

Lemma 8.4.

If $x ↾_{ℓ} = y ↾_{ℓ}$ , then $G_{x} [1958^{ℓ} / 4] = G_{y} [1958^{ℓ} / 4]$ . Moreover, from $x ↾_{ℓ}$ , we can effectively determine the atomic diagram of $G_{x} [1958^{ℓ} / 4]$ .

Using this Lemma, it makes sense to define $G_{x} [i]$ whenever $x \in 2^{< ω}$ and $i ⩽ 1958^{| x |} / 4$ .

Proof.

Given a freely reduced word w in ${a_{i}}_{i \in ω} \cup {b, c}$ , for each $i \in ω$ , let $n_{i}$ be the number of occurrences of $a_{i}$ or $a_{i}^{- 1}$ in w. Define the weight $μ (w)$ to be $\begin{matrix} μ (w) = n_{0} + 1958 n_{1} + 1958^{2} n_{2} + \dots . \end{matrix}$ We will often say “the number of $a_{i}$ ’s” when we mean “the number of occurrences of $a_{i}$ ’s and $a_{i}^{- 1}$ ’s”.

Suppose $w_{1}$ and $w_{2}$ are words in $a_{0}$ , b, c, of length at most $1958^{ℓ} / 4$ , such that $w_{1} = w_{2}$ in $G_{x}$ . We claim that $w_{1} = w_{2}$ in $G_{y}$ . From this and a similar argument reversing the roles of x and y, it will follow that $G_{x} [1958^{ℓ} / 4] = G_{y} [1958^{ℓ} / 4]$ .

Let $w = w_{1} w_{2}^{- 1}$ . Note that $μ (w) < 1958^{ℓ}$ . We will argue that for each non-trivial word v with $μ (v) < 1958^{ℓ}$ , with v equal to the identity in $G_{x}$ , there is a word $v^{'}$ of shorter length than v, with v equivalent to $v^{'}$ in both $G_{x}$ and $G_{y}$ . From this it will follow that $w = e$ in $G_{y}$ , and so $w_{1} = w_{2}$ in $G_{y}$ .

Given v as above, since $v = e$ in $G_{x}$ , by Greendlinger’s Lemma there is a generating relator $r = u_{1} u_{2}$ of $G_{x}$ , with $u_{1}$ a subword of v and $| u_{1} | > (1 - \frac{3}{10}) | r | = \frac{7}{10} | r |$ . We consider a number of cases:

r is an inverse or cyclic permutation of $u (a_{i}, b) = a_{i + 1}$ . Then r is a relator in both $G_{x}$ and $G_{y}$ . Note that $| r | = 5151$ , so $| u_{2} | ⩽ \frac{3}{10} | r | < 1546$ . Thus $u_{2}$ can have at most 1546 $a_{i}$ ’s and one $a_{i + 1}$ . Also, $u_{1}$ has at least 3504 $a_{i}$ ’s (as $u (a_{i}, b) = a_{i + 1}$ has 5050 $a_{i}$ ’s in it). Thus replacing $u_{1}$ by $u_{2}^{- 1}$ in v to obtain $v^{'}$ , we get that the number of $a_{i}$ ’s in v is at least 1958 more than the number of $a_{i}$ ’s in $v^{'}$ , and the number of $a_{i + 1}$ ’s is at most one more in $v^{'}$ than in v. Thus $μ (v^{'}) ⩽ μ (v)$ . Since r was a relator in both $G_{x}$ and $G_{y}$ , v and $v^{'}$ are equivalent in both $G_{x}$ and $G_{y}$ .

r is an inverse or cyclic permutation of $u (a_{i}, c) = e$ . Then $u_{1}$ , and hence v, has at least 3504 $a_{i}$ ’s. Since $\begin{matrix} 1958^{i} (number of a_{i} ’s in v) ⩽ μ (v) < 1958^{ℓ} \end{matrix}$ we have that $i < ℓ$ . Since $x ↾_{ℓ} = y ↾_{ℓ}$ , r is also a relator in $G_{y}$ . Replacing $u_{1}$ in v by $u_{2}^{- 1}$ to get $v^{'}$ , we have that $μ (v^{'}) ⩽ μ (v)$ as $v_{2}$ has at most 1546 $a_{i}$ ’s.

Notice that this procedure also gives a method for determining whether

w_{1} = w_{2}

G_{x}

using only

x ↾_{ℓ}

. □

Lemma 8.5.

From $G_{x} [5150^{ℓ}]$ , we can effectively determine $x ↾_{ℓ}$ .

Proof.

We claim that $x (i) = 1$ iff $u (a_{i}, c) = e$ in $G_{x}$ . If $x (i) = 1$ , then $u (a_{i}, c) = e$ is a defining relator. Assume that $u (a_{i}, c) = e$ in $G_{x}$ . We will show that $x (i) = 1$ . Since $u (a_{i}, c)$ is a reduced word equivalent to e in $G_{x}$ , there is an inverse or cyclic permutation $r = u_{1} u_{2}$ of a defining relator of $G_{x}$ such that $u_{1}$ is a subword of $u (a_{i}, c)$ , and $| u_{1} | ⩾ \frac{7}{10} | r |$ . Then $u_{1}$ must contain at least two instances of $a_{i}$ and at least one instance of c, and so the only option is that $u (a_{i}, c) = e$ is a defining relator of $G_{x}$ and r is an inverse or cyclic permutation of it. This implies that $x (i) = 1$ .

Finally, it suffices to see that for $i < ℓ$ , $u (a_{i}, c)$ is a word of length at most $5150^{ℓ}$ in $a_{0}$ , b, c, in $G_{x}$ . We argue by induction that $a_{i}$ is equivalent to a word of length at most $5150^{i}$ in $G_{x}$ . For $a_{0}$ , this is true trivially. Suppose that we know that $a_{i}$ is equivalent to a word of length at most $5150^{i}$ . Then $a_{i + 1} = u (a_{i}, b)$ is equivalent to a word of length at most $5150^{i + 1}$ . This completes our inductive argument. Then if $i < ℓ$ , $a_{i}$ is equivalent to a word of length at most $5150^{i}$ , and so $u (a_{i}, c)$ is a word of length at most $5150^{i + 1} ⩽ 5150^{ℓ}$ . □

The two lemmas above show that h is a computable height function. Moreover, we can compute $h^{- 1} (i)$ for every i. The other properties of the height function are clear. We show t $K$ is branching. Given a finite partial group $G_{x} [i]$ , choose y such that $y ↾_{i} = x ↾_{i}$ , but $y (i) \neq x (i)$ . Then by Lemma 8.4, $G_{x} [i] = G_{y} [i]$ , but by Lemma 8.5, $G_{x} [5150^{i + 1}] \neq G_{y} [5150^{i + 1}]$ . Thus we have:

Theorem 8.6.

The class $K$ is a branching class. Moreover, each $A \in K_{ω}$ is a group.

Thus we have the following corollary.

Corollary 8.7.

The branching class $K_{ω}$ contains countinuumly many ML-random groups. Some of these ML-random groups are computable in $0^{'}$ .

References

C.S.

Calude, Information and Randomness – an Algorithmic Perspective, 2nd edn, revised and extended, Springer-Verlag, Berlin, 2002.

G.J.

Chaitin, On the length of programs for computing finite binary sequences: Statistical considerations, Journal of the ACM16 (1969), 145–159. doi:10.1145/321495.321506.

Downey and

Hirschfeldt, Algorithmic Randomness and Complexity, Theory and Applications of Computability, Springer, New York.

Erdös and

Spencer, Probabilistic Methods in Combinatorics, Probability and Mathematical Statistics, Vol. 17, Academic Press, New York–London, 1974.

Gromov, Random walk in random groups, Geom. Funct. Anal.13(1) (2003), 73–146. doi:10.1007/s000390300002.

Harrison-Trainor and

M.-C.

Ho, On optimal Scott sentences of finitely generated structures, Proceedings of the American Mathematical Society146 (2018), 4473–4485.

Hodges, Model Theory, Encyclopedia of Mathematics and its Applications, Vol. 42, Cambridge University Press, 1993.

Khoussainov, A quest for algorithmically random infinite structures, II, in: Proceedings of LFCS, 2015.

Khoussainov, A quest for algorithmically random infinite structures, in: Proceedings of LICS-CSL 2014 Conference, Vienna, Austria.

10.

J.F.

Knight, Degrees coded in jumps of orderings, Journal of Symbolic Logic51 (1986), 1034–1042. doi:10.2307/2273915.

11.

Kolmogorov, Three approaches to the quantitative definition of information, Problems of Information Transmission1 (1965), 1–7.

12.

Kučera and

Slaman, Randomness and recursive enumerability, SIAM Journal on Computing31 (2001), 199–211. doi:10.1137/S0097539799357441.

13.

Li and

Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, 3rd edn, Springer-Verlag, 2008, (xx + 792 pp.).

14.

R.C.

Lyndon and

P.E.

Schupp, Combinatorial Group Theory, Springer-Verlag, Berlin, 1977.

15.

A.I.

Mal’cev, Constructive algebras. I, Uspehi Mat. Nauk16(3(99)) (1961), 3–60.

16.

Martin-Löf, The definition of random sequences, Information and Control9(6) (1966), 602–619. doi:10.1016/S0019-9958(66)80018-9.

17.

Nies, Computability and Randomness, Oxford University Press, 2009.

18.

M.O.

Rabin, Computable algebra, general theory and theory of computable fields, Trans. Amer. Math. Soc.95 (1960), 341–360.

19.

L.J.

Richter, Degrees of structures, J. Symbolic Logic46(4) (1981), 723–731. doi:10.2307/2273222.

20.

C.P.

Schnorr, A unified approach to the definition of random sequences, Mathematical Systems Theory5(3) (1971), 246–258. doi:10.1007/BF01694181.

21.

C.P.

Schnorr, The process complexity and effective random tests, in: Proceedings of the Fourth ACM Symposium of Theory of Computing, Vols 1–3, Denver, Colorado, 1972.

22.

Silberman, Addendum to: “Random walk in random groups”, Geom. Funct. Anal.13(1) (2003), 147–177. doi:10.1007/s000390300003.

23.

T.A.

Slaman, Relative to any nonrecursive set, Proceedings of the American Mathematical Society126 (1998), 2117–2122. doi:10.1090/S0002-9939-98-04307-X.

24.

A.K.

Zvonkin and

L.A.

Levin, The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms, Russian Math. Surveys25(6) (1970), 83–124. doi:10.1070/RM1970v025n06ABEH001269.