scratch

§ Turing Degree

created 2022-09-25 · last edited 2023-04-02
  • Lectures on turing degree
  • A set XXX is turing reducible to YYY iff oracle access to membership in YYY provides decidable membership for XXX. (imagine YYY as hovering above XXX, as we are given oracle access to YYY). This is written as X≤TYX \leq_T YX≤T​Y.
  • Two sets are turing equivalent iff X≤TYX \leq_T YX≤T​Y and Y≤TXY \leq_T XY≤T​X, also written as X≡TYX \equiv_T YX≡T​Y
  • Clealy, ≡T\equiv_T≡T​ is an equivalence relation.
  • A turing degree is an equivalence class of ≡T\equiv_T≡T​.
  • Said differently, it is a maximal strongly connected component of the ≤T\leq_T≤T​ graph.
  • Turing degrees have a partial order, where [X]≤[Y][X] \leq [Y][X]≤[Y] iff X≤YX \leq YX≤Y (note that the precise representatives of each class do not matter).
  • A set is recursively enumerable in AAA if it is the domain of some partial function recursive in AAA (ie, can write a partial function that semidecides membership in SSS given oracle access to AAA.)
  • The jump of a set AAA, written A′A'A′, is the set of programs ppp (treated as natural numbers such that A′≡p∣evalA(p)(p)↓A' \equiv { p | eval^A(p)(p) \downarrow }A′≡p∣evalA(p)(p)↓, where ↓\downarrow↓ means converges. That is, it's the set of natural numbers ppp such that when the pppth program in the enumeration of programs with oracle access to AAA, when evaluated on ppp, 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 000 since 0≤TY0 \leq_T Y0≤T​Y for all YYY. That is, oracle access to decision procedure for 000 gives a decision procedure for YYY
  • 0′0'0′ is the degree of the halting problem.
  • The first jump is taken relative to A≡ϕA \equiv \phiA≡ϕ.
  • The join of two sets is given by A⊕B≡{2n:n∈A}∪{2m+1:m∈B}A \oplus B \equiv \{ 2n : n \in A \} \cup \{ 2m + 1 : m \in B \}A⊕B≡{2n:n∈A}∪{2m+1:m∈B}. Claim that the turing degree of A⊕BA \oplus BA⊕B is a LUB of the turing degrees of A,BA, BA,B.
  • Cutland, N. Computability. Cambridge University
❦
Newer ৪ Blog ৪ Older