§ Turing degree

• Lectures on turing degree
• A set $X$ is turing reducible to $Y$ iff oracle access to membership in $Y$ provides decidable membership for $X$. (imagine $Y$ as hovering above $X$, as we are given oracle access to $Y$). This is written as $X \leq_T Y$.
• Two sets are turing equivalent iff $X \leq_T Y$ and $Y \leq_T X$, also written as $X \equiv_T Y$
• Clealy, $\equiv_T$ is an equivalence relation.
• A turing degree is an equivalence class of $\equiv_T$.
• Said differently, it is a maximal strongly connected component of the $\leq_T$ graph.
• Turing degrees have a partial order, where $[X] \leq [Y]$ iff $X \leq Y$ (note that the precise representatives of each class do not matter).
• A set is recursively enumerable in $A$ if it is the domain of some partial function recursive in $A$ (ie, can write a partial function that semidecides membership in $S$ given oracle access to $A$.)
• The jump of a set $A$, written $A'$, is the set of programs $p$ (treated as natural numbers such that $A' \equiv { p | eval^A(p)(p) \downarrow }$, where $\downarrow$ means converges. That is, it's the set of natural numbers $p$ such that when the $p$th program in the enumeration of programs with oracle access to $A$, when evaluated on $p$, converge.
• There is a unique turing degree containing all the computable sets [what does this mean? how is this (computably) a subset of the naturals? ], called $0$ since $0 \leq_T Y$ for all $Y$. That is, oracle access to decision procedure for $0$ gives a decision procedure for $Y$
• $0'$ is the degree of the halting problem.
• The first jump is taken relative to $A \equiv \phi$.
• The join of two sets is given by $A \oplus B \equiv \{ 2n : n \in A \} \cup \{ 2m + 1 : m \in B \}$. Claim that the turing degree of $A \oplus B$ is a LUB of the turing degrees of $A, B$.
• Cutland, N. Computability. Cambridge University