Lowness for isomorphism and degrees of genericity

Abstract

A Turing degree d is said to be low for isomorphism if whenever two computable structures are d-computably isomorphic, then they are actually computably isomorphic. We construct a real that is 1-generic and low for isomorphism but not computable from a 2-generic and thus provide a counterexample to Franklin and Solomon’s conjecture that the properly 1-generic degrees are neither low for isomorphism nor degrees of categoricity.

Keywords

Computability isomorphism genericity lowness

1. Introduction

A set A is low for a relativizable class $C$ if using it as an oracle does not reduce the class at all, that is, if $C^{A} = C$ . This term was first introduced in pure computability theory in 1972 with respect to Turing functionals [12]. Since then, lowness has been studied in “applied” subfields of computability theory such as algorithmic randomness [7] and computational learning theory [11], and it was studied for the first time in the context of computable structure theory by Franklin and Solomon [8]. Here, Franklin and Solomon defined the notion of lowness for isomorphism. We write that $A$ is d-computably isomorphic to $B$ ( $A ≅_{d} B$ ) if there is an isomorphism from $A$ to $B$ that is computable from d.

Definition 1.1.
[8] A degree d is low for isomorphism if for every pair of computable structures $A$ and $B$ , if $A ≅_{d} B$ , then $A ≅_{0} B$ .

Informally, d is low for isomorphism if, whenever it can compute an isomorphism between two computable structures, no oracle is actually necessary to do so because they are already computably isomorphic.

While Franklin and Solomon did not develop a full characterization of this notion, they obtained both positive and negative partial characterizations, mainly in terms of category and measure. We recall that a real A is n-generic if it either meets or strongly avoids every $Σ_{n}^{0}$ subset of $2^{< ω}$ ; that is, if for every such S, there is some $σ ≺ A$ such that either $σ \in S$ or no extension of σ is in S. A real is weakly n-generic if it meets every dense $Σ_{n}^{0}$ subset of $2^{< ω}$ ; that is, if for every such S, some initial segment of the real is in S [10]. If a real is n-generic (or weakly n-generic), we may say it is large with respect to category. If a real is random, on the other hand, it is large with respect to measure. For any reasonably defined randomness notion $R$ , the class of $R$ -random reals is conull; we refer the interested reader to [5,9] for definitions.

Franklin and Solomon proved that every Cohen 2-generic degree is low for isomorphism but that no Martin-Löf random degree is [8]. Therefore, this class of degrees is large with respect to category but small with respect to measure. Both of these bounds were found to be optimal: Franklin and Solomon showed that there was a weakly 2-generic degree that is not low for isomorphism and a computably random degree that is. However, the question remained as to whether any degree that was generic and low for isomorphism must necessarily be at least 2-generic.

We may also consider the degrees of categoricity, which form an interesting contrast with the degrees that are low for isomorphism. A Turing degree d is a degree of categoricity if some computable structure $A$ is c-computably categorical if and only if $c ⩾_{T} d$ [6]. We can thus see that the degrees of categoricity form something of a dual to those that are low for isomorphism. Furthermore, very little is known about the degrees of categoricity: the only known examples are d.c.e. in and above $0^{(α)}$ for some α [3,4,6], and no hyperimmune-free degree but $0$ is a degree of categoricity [1]. However, every degree of categoricity is known to be hyperarithmetic [3]. Therefore, the class of degrees of categoricity is conull as well.

Franklin and Solomon suggested that an attempt at understanding these notions could be made by studying the gap between them: the degrees that are neither degrees of categoricity nor low for isomorphism. They proposed the properly 1-generic degrees as a possible such class [8].

In this paper, we show that this conjecture is false: that there is a properly 1-generic degree d that is low for isomorphism. In fact, we must prove something stronger: since the degrees that are low for isomorphism are downwards closed, to prove a novel result, we must show that there is a 1-generic degree that is both not computable from any 2-generic degree and low for isomorphism.
2. The result

Theorem 2.1.
There is a 1-generic real that is low for isomorphism that is not computable from any 2-generic.

We begin with a general discussion of the requirements we will have to satisfy and the ways in which we will do this. First, let ${⟨ A_{j} ⟩}_{j \in ω}$ be an effective listing of all partial computable structures. We must ensure that the real G we build is 1-generic, that it is not computed by a 2-generic, and that it is low for isomorphism. We denote these requirements as follows:
${ONE}_{e}$ :
G either meets or avoids the $Σ_{1}^{0}$ set $W_{e}$ .
${TWO}_{i}$ :
There is a $Σ_{2}^{0}$ set $X_{i}$ such that if $Φ_{i}^{Y} = G$ , then Y neither meets nor avoids $X_{i}$ .
${IM}_{⟨ i, j_{1}, j_{2} ⟩}$ :
If $Φ_{i}^{G}$ is an isomorphism between $A_{j_{1}}$ and $A_{j_{2}}$ , then $A_{j_{1}} ≅_{0} A_{j_{2}}$ .

The first kind of requirement is finitary and the easiest one to satisfy: we can ensure that G is 1-generic through a standard finite injury approach. If we find at some stage that we can extend our finite approximation to G in such a way that we meet $W_{e}$ , we do so, injuring later requirements; otherwise, we satisfy it automatically.

We will satisfy the second requirement by breaking it up into subrequirements: ${TWO}_{⟨ i, τ ⟩}$ :
If there is a $Y ≻ τ$ with $Φ_{i}^{Y} = G$ , then Y does not meet $X_{i}$ and there is a string $ρ ≻ τ$ with $ρ \in X_{i}$ .
By working to meet each subrequirement, we will construct the set $X_{i}$ . Our action to meet a subrequirement is also finitary but somewhat complicated to describe.

Suppose that we have a finite approximation g to our real and that we now wish to act to satisfy ${TWO}_{⟨ i, τ ⟩}$ . We attempt to locate a string ρ extending τ with the property that there is no Y extending ρ with $Φ_{i}^{Y} = G$ . We reserve the next bit b (at position $| g |$ ) for our use. At first we require that $G (b) = 0$ . If at some stage we see a ρ extending τ with $Φ_{i}^{ρ} ⪰ g^{⌢} 0$ , this is our desired ρ. We ensure that there is no Y extending ρ with $Φ_{i}^{Y} = G$ by requiring that $G (b) = 1$ . Thus, our action for this subrequirement is finitary.

Our construction will take place on a priority tree, and there will be various ${TWO}_{⟨ i, τ ⟩}$ strategies on the tree. We will define $X_{i}$ to be made up of the ρ which are selected by a ${TWO}_{⟨ i, τ ⟩}$ strategy that is not later injured during the construction. As we are performing a $0^{″}$ -construction, this will be a $Σ_{2}^{0}$ set.

If there is a Y extending τ with $Φ_{i}^{Y} = G$ , we will argue that the ${TWO}_{⟨ i, τ ⟩}$ -strategy along the true path will see the desired extension ρ of τ, and this ρ will be in $X_{i}$ , so Y cannot avoid $X_{i}$ .

Alternately, if Y meets $X_{i}$ , then we can find an initial segment ρ at which this happens and consider the $Φ_{i, τ}$ -strategy that put ρ into $X_{i}$ . If the strategy is not on the true path, we will show that this Y cannot compute our real G; if the strategy is on the true path, we will use the bit b as a witness to show that, once again, $Φ_{i}^{Y}$ cannot compute G.

The third kind of requirement allows us to ensure that G is actually low for isomorphism. This requirement must be treated in an infinitary way. To do this, we will take our finite approximation to G and look for longer and longer extensions of it that would produce a partial isomorphism via $Φ_{i}$ . While we are looking for such an extension, we restrain G to pass through the previously located extension. If we find such an extension, we move to the infinite outcome as we temporarily drop the restraint. Then we return to the finite outcome and begin searching for a longer extension.

If, for the ${IM}_{⟨ i, j_{1}, j_{2} ⟩}$ -strategy along the true path, we are infinitely often able to find a longer extension which extends the isomorphism via $Φ_{i}$ , then this is a computable sequence, so the resulting isomorphism is computable. If we eventually stop finding such extensions, then our restraint on G ensures that G cannot compute an isomorphism via $Φ_{i}$ .
2.1. Construction

We define our priority tree T recursively:

$⟨ ⟩ \in T$ ;

If $σ \in T$ with $| σ | = 3 e$ , then σ is a ${ONE}_{e}$ -node, and both $σ^{⌢} 0$ and $σ^{⌢} 1$ are in T with $σ^{⌢} 1 < σ^{⌢} 0$ ;

If $σ \in T$ with $| σ | = 3 e + 1$ , then σ is a ${TWO}_{e}$ -node, and both $σ^{⌢} 0$ and $σ^{⌢} 1$ are in T with $σ^{⌢} 1 < σ^{⌢} 0$ ;

If $σ \in T$ with $| σ | = 3 e + 2$ , then σ is a ${IM}_{e}$ -node, and $σ^{⌢} m \in T$ for $m \in ω \cup {\infty}$ , with $σ^{⌢} \infty < \dots < σ^{⌢} 1 < σ^{⌢} 0$ .

For every node σ in the priority tree which is visited at any point in the construction, we will define a string $g_{σ} \in 2^{< ω}$ . This is the finite initial segment of G that σ must work beyond – it is the restraint that σ inherits from its parent. We begin with $g_{⟨ ⟩} = ⟨ ⟩$ .

At every stage s we will visit an increasing sequence of nodes on the tree, beginning with $⟨ ⟩$ . When we visit a node σ, we will act according to its strategy for that stage. If $| σ | < s$ , this action will include choosing some m such that $σ^{⌢} m$ is the next node to visit at stage s. At this or a previous stage, the action for σ will have defined $g_{σ^{⌢} m} \in 2^{< ω}$ with $g_{σ^{⌢} m} ⪰ g_{σ}$ . Once we have visited a node σ with $| σ | = s$ , the stage will end and we will proceed to stage $s + 1$ .

Now we give the details of each node’s strategy.

2.2. Strategy for ${ONE}_{e}$ -nodes

Suppose σ is a ${ONE}_{e}$ -node which is visited at stage s. We can immediately define $g_{σ^{⌢} 0} = g_{σ}$ . If we have defined $g_{σ^{⌢} 1}$ at a previous stage, then there is no action to take for σ, and $σ^{⌢} 1$ is the next node to be visited.

If we have not yet defined $g_{σ^{⌢} 1}$ , we look for a $ρ ⪰ g_{σ}$ with $ρ \in W_{e, s}$ . If there is such a ρ, we define $g_{σ^{⌢} 1} = ρ$ , and $σ^{⌢} 1$ is the next node to be visited. If there is no such ρ, then $σ^{⌢} 0$ is the next node to be visited.

2.3. Strategy for ${TWO}_{e}$ -nodes

Suppose σ is a ${TWO}_{e}$ -node which is visited at stage s, where $e = ⟨ i, τ ⟩$ . We can immediately define $g_{σ^{⌢} 0} = g_{σ}^{⌢} 0$ and $g_{σ^{⌢} 1} = g_{σ}^{⌢} 1$ .

We then look for a $ρ ⪰ τ$ with $| ρ | < s$ and $Φ_{i}^{ρ} ⪰ g_{σ}^{⌢} 0$ . If there is such a ρ, then $σ^{⌢} 1$ is the next node to be visited. If there is no such ρ, then $σ^{⌢} 0$ is the next node to be visited.

2.4. Strategy for ${IM}_{e}$ -nodes

Suppose σ is an ${IM}_{e}$ -node which is visited at stage s, where $e = ⟨ i, j_{1}, j_{2} ⟩$ . We can immediately define $g_{σ^{⌢} 0} = g_{σ}^{⌢} 0$ and $g_{σ^{⌢} \infty} = g_{σ}^{⌢} 1$ .

We define a length-of-agreement function $ℓ (e, s, ρ)$ to be the greatest $n ⩽ s$ such that:

The atomic diagrams of $A_{j_{1}}$ and $A_{j_{2}}$ have converged up to n by stage s;

$A_{j_{1}} ↾ n \subseteq dom Φ_{i}^{ρ}$ ;

$A_{j_{2}} ↾ n \subseteq range Φ_{i}^{ρ}$ ; and

$Φ_{i}^{ρ}$ is a partial isomorphism from $A_{j_{1}}$ to $A_{j_{2}}$ .

Let $k < \infty$ be greatest with $g_{σ^{⌢} k}$ defined, and let $t ⩽ s$ be the stage at which $g_{σ^{⌢} k}$ was defined. We look for a $ρ ≻ g_{σ^{⌢} k}$ with $| ρ | < s$ and $ℓ (e, s, ρ) > ℓ (e, t, g_{σ^{⌢} k})$ . If there is such a ρ, then we define $g_{σ^{⌢} (k + 1)} = ρ$ , and $σ^{⌢} \infty$ is the next node to be visited. If there is no such ρ, then $σ^{⌢} k$ is the next node to be visited.

2.5. The true path

Define the true path $TP$ by setting $TP ↾ n$ to be the lexicographically leftmost node $σ \in T$ with $| σ | = n$ and σ is visited infinitely often during the construction. It is straightforward to see that this is a path through T. We write $ν ⩽ TP$ to indicate that ν is on or to the left of the true path. Note that ${ν | ν ⩽ TP}$ is a $Σ_{2}^{0}$ set; indeed, $\begin{matrix} ν ⩽ TP ⟺ (\exists s) (\forall t > s) [the node of length | ν | visited at stage t is ⩾ ν] . \end{matrix}$

For every i, define the set $X_{i}$ as: $\begin{matrix} X_{i} = {ρ | there is a ν ⩽ TP which is a {TWO}_{⟨ i, τ ⟩} -node with g_{ν} defined, ρ ⪰ τ and Φ_{i}^{ρ} ⪰ g_{ν}^{⌢} 0} . \end{matrix}$ Note that $X_{i}$ is a $Σ_{2}^{0}$ set.

Define $\begin{matrix} G = ⋃_{σ ≺ TP} g_{σ} . \end{matrix}$

2.6. Verification

Lemma 2.2.
If $ν ⩽ TP$ but $ν ⊀ TP$ (so ν is strictly to the left of the true path), then $g_{ν}$ is either not defined or $g_{ν} ⊀ G$ .
Proof.
Assume $g_{ν}$ is defined. Let σ be the meet of ν and TP. So there are some $m_{0}, m_{1}$ with $σ^{⌢} m_{1} ⪯ ν$ , $σ^{⌢} m_{0} ≺ TP$ and $σ^{⌢} m_{1} < σ^{⌢} m_{0}$ . Since $g_{ν}$ is defined, it follows that $g_{σ^{⌢} m_{1}}$ is defined.

Suppose σ is a ${ONE}_{e}$ -node. Then $σ^{⌢} m_{1} < σ^{⌢} m_{0}$ requires $m_{1} = 1$ and $m_{0} = 0$ . Since $g_{σ^{⌢} m_{1}} = g_{σ^{⌢} 1}$ is defined, our action for σ ensures that $σ^{⌢} 1 = σ^{⌢} m_{1}$ is on the true path, contrary to our choice of σ. Thus σ cannot be a ${ONE}_{e}$ -node.

Suppose σ is a ${TWO}_{e}$ -node. Then $σ^{⌢} m_{1} < σ^{⌢} m_{0}$ requires $m_{1} = 1$ and $m_{0} = 0$ . By our action for σ, $g_{σ^{⌢} m_{1}} = g_{σ}^{⌢} 1$ and $g_{σ^{⌢} m_{0}} = g_{σ}^{⌢} 0$ . Since $G ≻ g_{σ^{⌢} m_{0}}$ and $g_{ν} ⪰ g_{σ^{⌢} m_{1}}$ , the lemma follows.

Finally, suppose σ is an ${IM}_{e}$ -node. Then $σ^{⌢} m_{1} < σ^{⌢} m_{0}$ requires $m_{1} > m_{0}$ , in the usual ordering of $ω \cup {\infty}$ . If $m_{1} \neq \infty$ , then by our action for σ, after the stage at which $g_{σ^{⌢} m_{1}}$ becomes defined, $σ^{⌢} m_{0}$ will never again be visited. This contradicts our assumption that $σ^{⌢} m_{0} ≺ TP$ . So it must be that $m_{1} = \infty$ . Again by our action for σ, $g_{σ^{⌢} \infty} = g_{σ}^{⌢} 1$ . Also, observe that $g_{σ^{⌢} (k + 1)} ≻ g_{σ^{⌢} k}$ for all k and $g_{σ^{⌢} 0} = g_{σ}^{⌢} 0$ . So $G ≻ g_{σ^{⌢} m_{0}} ≻ g_{σ}^{⌢} 0$ , and $g_{ν} ⪰ g_{σ^{⌢} m_{1}} = g_{σ}^{⌢} 1$ . The lemma follows. □
Lemma 2.3.
G cannot be computed from a 2-generic.
Proof.
To prove this lemma, it is sufficient to show that for any i and Y such that $Φ_{i}^{Y} = G$ , Y cannot be 2-generic. In fact, we will show that such a Y can neither meet nor avoid $X_{i}$ .

Suppose that Y avoids $X_{i}$ . We fix a $τ ≺ Y$ at which this happens, let $e = ⟨ i, τ ⟩$ , and let $σ = TP ↾ (3 e + 1)$ . Then by definition of $X_{i}$ , there is no $ρ ⪰ τ$ with $Φ_{i}^{ρ} ⪰ g_{σ}^{⌢} 0$ . In particular, it must be that $Φ_{i}^{Y} (| g_{σ} |) \neq 0$ . But if there is no such ρ, then $σ^{⌢} 0$ will always be the next node visited after σ is visited, meaning $σ^{⌢} 0$ is on the true path. So $g_{σ^{⌢} 0} = g_{σ}^{⌢} 0 ≺ G$ . Thus $Φ_{i}^{Y} (| g_{σ} |) \neq G (| g_{σ} |)$ , and $Φ_{i}^{Y} \neq G$ .

Now we suppose that Y does meet $X_{i}$ . We fix an initial segment ρ at which Y meets $X_{i}$ and consider the ${TWO}_{⟨ i, τ ⟩}$ -node ν that witnesses $ρ \in X_{i}$ . By definition, $ν ⩽ TP$ , $g_{ν}$ is defined and $Φ_{i}^{ρ} ⪰ g_{ν}^{⌢} 0$ . But if ν is strictly to the left of the true path, then by Lemma 2.2, $g_{ν}$ is not an initial segment of G, so $Φ_{i}^{Y} \neq G$ .

Now suppose ν is on the true path. Then ρ is precisely the sort of string we are searching for in the strategy for ν. So at any stage $s > | ρ |$ at which ν is visited, $ν^{⌢} 1$ will be the next node visited. So $ν^{⌢} 1 ≺ TP$ , and so $g_{ν^{⌢} 1} = g_{ν}^{⌢} 1 ≺ G$ . But then $Φ_{i}^{Y} \neq G$ . □
Lemma 2.4.
Each requirement of the form ${ONE}_{e}$ is met.
Proof.
Fix e, and let $σ = TP ↾ (3 e)$ . If $g_{σ^{⌢} 1}$ is ever defined, then $g_{σ^{⌢} 1} \in W_{e}$ and $σ^{⌢} 1 ≺ TP$ by construction, so G meets $W_{e}$ at $g_{σ^{⌢} 1}$ .

So suppose now that $g_{σ^{⌢} 1}$ is never defined, and that $g_{σ}$ does not avoid $W_{e}$ . Then there is a $ρ ⪰ g_{σ}$ with $ρ \in W_{e}$ , and so at some sufficiently late stage s we will see $ρ \in W_{e, s}$ while acting for the strategy for σ. At this stage, we will define $g_{σ^{⌢} 1} = ρ$ , contrary to our assumption. □
Lemma 2.5.
Each requirement of the form ${IM}_{e}$ is met.
Proof.
Fix $e = ⟨ i, j_{1}, j_{2} ⟩$ and let $σ = TP ↾ (3 e + 2)$ , and suppose $A_{j_{1}}$ and $A_{j_{2}}$ are total structures and $Φ_{i}^{G}$ is an isomorphism from $A_{j_{1}}$ to $A_{j_{2}}$ .

First suppose there were some $k < \infty$ with $σ^{⌢} k ≺ TP$ , and let t be the stage at which $g_{σ^{⌢} k}$ is defined. Since $σ^{⌢} k$ is visited infinitely often, by construction $g_{σ^{⌢} (k + 1)}$ must never be defined. But for some sufficiently large n and s, $G ↾ n ≻ g_{σ^{⌢} k}$ and $ℓ (e, s, G ↾ n) > ℓ (e, t, g_{σ^{⌢} k})$ . So our action for σ will define $g_{σ^{⌢} (k + 1)} = G ↾ n$ , contrary to our previous statement.

So it must be that $σ^{⌢} \infty ≺ TP$ . But in that case the sequence ${⟨ g_{σ^{⌢} k} ⟩}_{k \in ω}$ is a total computable increasing sequence, and $⋃_{k \in ω} Φ_{i}^{g_{σ^{⌢} k}}$ is a computable isomorphism between $A_{j_{1}}$ and $A_{j_{2}}$ . □

These lemmas suffice to prove Theorem 2.1: Lemma 2.4 shows that G must be 1-generic, Lemma 2.5 shows that G must be low for isomorphism, and Lemma 2.3 shows that G must not be computable from a 2-generic and thus that it is not only properly 1-generic but that its lowness for isomorphism is not due to being in the downwards closure of a 2-generic.
3. Parting thoughts

Franklin and Solomon’s results indicated that the degrees that are low for isomorphism are resistant to a straightforward characterization. For instance, they showed that there are degrees that are low for isomorphism and degrees that are not in each of the following classes: minimal degrees, hyperimmune degrees, and hyperimmune-free degrees [8]. However, as mentioned in the introduction of this paper, they also showed that some classes of degrees, including the 2-generic degrees, contain only degrees that are low for isomorphism and that some other classes, including the Martin-Löf random degrees, contain only degrees that are not. While it was already known that there are properly 1-generic degrees that are low for isomorphism since every 2-generic degree computes a properly 1-generic degree and the degrees that are low for isomorphism are closed downward, we have constructed a properly 1-generic degree that is nontrivially low for isomorphism. We have therefore shown that there is no level of Cohen genericity at which lowness for genericity only holds when it is required to by higher levels and thus that lowness for isomorphism is not a straightforward notion with respect to genericity, either.

We should note that the situation is more complicated when one considers weak genericity as well. We have not addressed the question of whether a degree that is low for isomorphism and properly 1-generic must be computable from a weakly 2-generic. While we see no reasonable way to adapt our construction and replace “2-genericity” with “weak 2-genericity” in Theorem 2.1, we cannot rule it out as a possibility.

We may also consider notions similar to lowness for isomorphism. Csima defined a degree d to be low for categoricity if every computable d-computably categorical structure is computably categorical [2]. Lowness for isomorphism is immediately seen to imply lowness for categoricity; it remains an open problem whether the converse holds. Thus our 1-generic G is low for categoricity, and it demonstrates that attempting to separate the two notions at the level of Cohen 1-generics would be extremely difficult.

One could also consider the question of separating notions for lowness for isomorphism for classes of structures. A degree d is low for isomorphism for a class $C$ if for every pair of structures $A$ and $B$ in $C$ , if $A$ is d-computably isomorphic to $B$ , then $A$ and $B$ are already computably isomorphic. This notion was defined in [8] and investigated further in [13] for classes such as linear orders and equivalence structures. The results for these classes often mirror those for the general case or are somehow trivial, and it would be interesting to know whether this trend continues when 1-genericity is considered.

Footnotes

Acknowledgements

The authors would like to thank the Institute for Mathematical Sciences of the National University of Singapore for supporting their stay there during the Algorithmic Randomness program in June 2014.

References

B.A.

Anderson and

B.F.

Csima, Degrees that are not degrees of categoricity, Notre Dame J. Formal Logic 57(3) (2016), 389–398.

Csima, Degrees of categoricity and related notions, BIRS Computable Model Theory Workshop (2013).

B.F.

Csima,

J.N.Y.

Franklin and

R.A.

Shore, Degrees of categoricity and the hyperarithmetic hierarchy, Notre Dame J. Formal Logic 54(2) (2013), 215–231. doi:10.1215/00294527-1960479.

B.F.

Csima and

Harrison-Trainor, Degrees of categoricity on a cone via η-systems, J. Symbolic Logic 82(1) (2017), 325–346. doi:10.1017/jsl.2016.43.

R.G.

Downey and

D.R.

Hirschfeldt, Algorithmic Randomness and Complexity, Springer, Berlin 2010.

E.B.

Fokina,

Kalimullin and

Miller, Degrees of categoricity of computable structures, Arch. Math. Logic 49(1) (2010), 51–67. doi:10.1007/s00153-009-0160-4.

J.N.Y.

Franklin, Lowness and highness properties for randomness notions, in: Proceedings of the 10th Asian Logic Conference,

Arai et al., eds, World Scientific, Singapore 2010, pp. 124–151.

J.N.Y.

Franklin and

Solomon, Degrees that are low for isomorphism, Computability 3(2) (2014), 73–89.

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

10.

Odifreddi, Classical Recursion Theory. Number 125 in Studies in Logic and the Foundations of Mathematics, North-Holland, Amsterdam 1989.

11.

T.A.

Slaman and

R.M.

Solovay, When oracles do not help, in: Fourth Annual Workshop on Computational Learning Theory, Morgan Kaufman., Los Altos, CA, 1991, pp. 379–383.

12.

Soare, The Friedberg–Muchnik theorem re-examined, Canadian J. of Math. 24 (1972), 1070–1078. doi:10.4153/CJM-1972-110-4.

13.

J.D.

Suggs, On Lowness for Isomorphism as Restricted to Classes of Structures, PhD thesis, University of Connecticut, 2015.

Lowness for isomorphism and degrees of genericity

Abstract

Keywords

1. Introduction

2.2. Strategy for ONE e -nodes

2.3. Strategy for TWO e -nodes

2.4. Strategy for IM e -nodes

2.5. The true path

2.6. Verification

Footnotes

Acknowledgements

References

2.2. Strategy for ${ONE}_{e}$ -nodes

2.3. Strategy for ${TWO}_{e}$ -nodes

2.4. Strategy for ${IM}_{e}$ -nodes