Questions tagged [turing-degrees]
Relating to the Turing degrees or Turing reducibility.
18 questions
4 votes
1 answer
289 views
A universal ordering on the sets in a (Turing) degree
Do all the Turing degrees agree, in a definable (hyperarithmetic? arithmetic?) way, on an ordering of their representatives? I'll make this precise below but roughly the question is whether there is ...
- 3,967
6 votes
0 answers
202 views
Have you seen this variation of Medvedev reducibility?
In what follows, $A, B$ will denote subsets of $\mathbb{N}^{\mathbb{N}}$, i.e., sets of total functions $\mathbb{N} \to \mathbb{N}$ (maybe assume them to be inhabited to avoid any headaches about the ...
- 38k
8 votes
3 answers
754 views
Model of ZFC In Which Martin's Cone Theorem Fails?
Is it known to be consistent with ZFC for there to exist a Turing degree invariant projective set which neither contains nor is disjoint from a cone? What about in $L$, i.e., is it known that (the ...
- 3,967
5 votes
1 answer
211 views
Recursive linear orders given by Kleene-Brouwer order
The Kleene-Brouwer order $<_{KB}$ transforms a computable tree $T$ on $\omega^{< \omega}$ into a computable linear order (mapping infinite paths through $T$ into infinite descending sequences). ...
- 3,967
2 votes
1 answer
184 views
Equivalence of Non-Standard Ordinal Notations
Suppose I have a computable linear order $<_{KB}$ that has no infinite descending hyperarithmetic sequence but has some infinite descending sequence and a non-standard notation $\alpha$. That is, ...
- 3,967
5 votes
1 answer
290 views
The problem of degrees below $0''$ not c.e. in a set below $0'$
I remember reading somewhere in a paper by Shore if I am not mistaken about a very interesting problem in computability. It basically asks if there is any degree in the interval $[0', 0'']$ that is ...
- 1,391
7 votes
1 answer
777 views
What is the flaw in Cooper's argument?
Lately I have been studying in the subject of degree theory, specifically definability results related to $\mathcal{D}$. A famous conjecture in the field due to Slaman and Woodin is that the only ...
- 1,391
5 votes
1 answer
309 views
Splitting 0' into two 1-generic reals
I have come across multiple research papers where they have mentioned that two 1-generic reals $x$ and $y$ can be constructed such that $x \oplus y \equiv_{T} \textbf{0}'$, where $\textbf{0}'$ is the ...
user527095
8 votes
2 answers
722 views
Turing degrees of sets separating two computably inseparable sets (theorems and antitheorems)
Let $A\subseteq\mathbb{N}$ be the set of Gödel codes of theorems of Peano arithmetic, and $B\subseteq\mathbb{N}$ be the set of codes of antitheorems (i.e, refutable statements, statements whose ...
- 38k
6 votes
1 answer
278 views
Is there an injective homomorphism on the Turing degrees?
I know that the existence of a non-trivial automorphism of the Turing degrees is a long-standing open problem. I am curious to know if something is known about (non-trivial) injective homomorphisms (...
- 342
3 votes
0 answers
105 views
What are all the order types of maximal chains of $\Delta^0_2$ sets?
A set of natural numbers is $\Delta^0_2$ if it’s computable from the halting set. Consider the quasi-order/pre-order of all $\Delta_0^2$ sets ordered by $m$-reduction, or equivalently consider the ...
- 4,573
2 votes
1 answer
170 views
$\Pi^0_2$ singleton forming minimal pair with $0''$
Is there a $\Pi^0_2$ singleton that forms a minimal pair with $0''$? That is, is there a set $X$ such that $X$ is the unique solution to $\forall x \exists y \phi(X|_y, x)$, $X$ and $0''$ are ...
- 3,967
1 vote
2 answers
207 views
Double Posner-Robinson Join (or a cupping analog of minimal pair)
Are there incompatible degrees $D_0, D_1 <_T 0'$ such that for all $X$ if $D_0 \oplus X \equiv_T D_1 \oplus X \equiv_T 0'$ then $X \equiv_T 0'$? So kinda like a cupping analog of a minimal pair. ...
- 3,967
1 vote
1 answer
140 views
Double Hop Inversion Theorem
The hop $H_e$ is defined by $H_e(X) = X \oplus W_e^{X}$. A 2-REA operator (or double hop) $J_{\langle e,i\rangle}$ is defined by $J_{\langle e,i\rangle}(X) = H_e(H_i(X))$ By a famous result from ...
- 3,967
1 vote
0 answers
58 views
Are the $\omega$-generic arithmetic degrees downward closed
A degree is $\alpha$-generic if it has representative that is $\alpha$-generic. Are the $\omega$-generic arithmetic degrees (i.e. the degree structure induced by arithmetic reproducibility) downward ...
- 3,967
3 votes
1 answer
125 views
Does every arithmetic degree below $0^\omega$ have a representative computable in $0^\omega$?
Suppose that $A \leq_a 0^\omega$ (i.e. $A$ is arithmetic in $0^\omega$) does there exist $\widehat{A} \equiv_a A$ with $\widehat{A} \leq_T 0^\omega$ [1]? More generally, say that a set $X$ is aT-...
- 3,967
2 votes
3 answers
199 views
Incompatible degrees $a,b$ s.t. $x < a$ implies $x \leq b$
Are there incompatible Turing degrees $a,b$ s.t any degree computable in $a$ either computes $a$ or is computed by $b$? Obviously, if $a$ was above $b$ then $a$ would be a strong minimal cover of $b$. ...
- 3,967
9 votes
2 answers
3k views
Is Turing degree actually useful in real life? [closed]
In theoretical computer science, we classify problems according to their Turing degree. Is there any practical application of this? Edit: Given that we cannot explicitly and mechanically understand ...