All Questions
Tagged with computability-theory turing-degrees
12 questions
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 ...
- 4,713
7
votes
1
answer
716
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 ...
- 21.3k
5
votes
1
answer
246
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 ...
- 1,422
6
votes
1
answer
230
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 (...
CommunityBot
- 1
8
votes
2
answers
586
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 ...
- 3,073
3
votes
0
answers
72
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,597
2
votes
1
answer
118
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 ...
- 4,201
1
vote
2
answers
142
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.
...
- 4,201
1
vote
1
answer
109
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 ...
- 12.9k
1
vote
0
answers
37
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,029
3
votes
1
answer
92
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,029
2
votes
3
answers
140
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$. ...
