Para ser más específico, ¿existe un problema de decisión de $P$ que
Sí!
Podemos definir una relación de equivalencia en los problemas de decisión: $A\equiv_T B$ si $a$ calcula $B$ y $B$ calcula $A$. De esta forma se define el orden parcial de Turing grados: problemas de decisión ordenado por la relativa reducibilidad.
Las propiedades de este orden parcial han sido ampliamente estudiados. Algunos resultados son:
Dado cualquier valor distinto de cero (= no el grado de la computables conjuntos) de Turing grado $d$, $\hat{d}$, que es incomparable con $d$ (esto responda a tu pregunta).
De hecho, cualquier grado de Turing está contenida en una antichain de grados de magnitud continuo.
Cada grado de Turing está por encima de sólo countably muchos grados, por lo que la "altura" de Turing grados es de $\omega_1$; en el caso de CH falla, esto significa que el poset de Turing grados son "más amplio" que el que es "alto."
Turing grados formar un superior semilattice - dado los problemas de decisión de $A, B\subseteq\omega$, la combinación de sus grados es el grado de $\{2n: n\in A\}\cup\{2n+1: n\in B\}$. Por otra parte, este semilattice no tiene ningún elemento de la parte superior (a causa de Turing salto).
Sin embargo, su existir Turing grados de $d, \hat{d}$ sin mayor límite inferior.
Por otra parte, no trivial infinitas combinaciones nunca existe (Pareja Exacta Teorema): dado un conjunto infinito de grados, $D$, si $D$ es trivial (= no tiene un subconjunto finito de $D_0$ tal que $\forall d\D\existe d_0\en D_0(d\le_T d_0)$) y $a$ es un límite superior de $D$, entonces existe un grado $b$, que también es un límite superior de $D$, y que es incomparable con $un$; por otra parte, $\{d: d\le un, d\le b\}=D$.
Si $A'$ y $B$ son el freno a los problemas de $A$ y $B$ y $\le_T B$, entonces $A'\le_T B'$. Esto significa que el salto puede ser pensado como una operación sobre títulos, no solo establece. Resulta que esta operación es definible sólo en términos de los pedidos parciales! Este fue un resultado sorprendente; ver https://math.berkeley.edu/~slaman/charlas/sw.pdf.
A la inversa de la anterior viñeta falla muy mal: el salto no es inyectiva, y, de hecho, dado cualquier grado $d$ por encima de la detención problema, hay un mínimo grado $\hat{d}$ cuyo salto es de $d$. (Mínimo aquí significa, "no $\ge_T$ cualquier grado, excepto a sí misma y el grado de conjuntos computables.)
Esto es todo sobre el global de la teoría de Turing grados; también la gente se ha estudiado ampliamente el local de la teoría especial de subclases de Turing grados. El más conocido de esta clase es la clase de los grados de los dominios de las funciones computables, la c.e. grados. Por supuesto, el grado de la detención problema es la máxima c.e. grado, por lo que en este contexto la respuesta a su pregunta es "no"; sin embargo, dado cualquier c.e. grado que no es el grado de la detención problema o la computables conjuntos, hay un incomparable c.e. grado. Este es el Friedberg-Muchnik Teorema, y su prueba fue un precursor del método de forzamiento en la teoría de conjuntos.
Permítanme terminar diciendo mi favorito dos preguntas abiertas acerca de Turing grados:
¿El poset de todos los Turing grados tiene alguna que no sea trivial automorfismos?
¿El poset de c.e. grados tiene alguna que no sea trivial automorfismos?
De vuelta en el día, tanto en las licenciaturas, las estructuras que se creía muy homogénea, con un montón de automorfismos; el tema de puro computabilidad teoría post-1955ish, sin embargo, fue todo lo contrario: el de Turing/c.e. los grados son estructuralmente rica, con un montón de definibles subclases, y en el hecho de que ahora se cree que ambos parcial de las órdenes son rígidos. Todo lo que se conoce en la actualidad, sin embargo, es que la automorphism grupos son en la mayoría de los contables.
Finalmente, dijo que la respuesta a su pregunta es "sí", me explico un sentido en el que la respuesta a su pregunta es "no". El único "natural" funciones crecientes en el Turing grados que han sido descubiertos hasta ahora son (esencialmente) recorre de Turing saltar. Martin conjeturó que
(1) Suponiendo ZF+AD, cada aumento de la función es (tal vez cuando restringidas para el conjunto $\{d: d>c\}$ $c$; es decir, "en un cono") de una iteración de el salto.
(2) Suponiendo que ZFC, Cada Borel función que es una cuestión de grado-invariante y el aumento es una iteración de el salto, en un cono.
Actualmente débil versiones de Martin conjetura se ha demostrado que, a pesar de que el conjetura es todavía muy abierto.
El artículo de la Wikipedia sobre el grado de Turing afirma que por cada grado cero no es una incomparable grado. En su caso, esto significa que hay un cierto grado incomparable con 0', y cualquier miembro de este título responde a su pregunta.
Aunque el dado respuestas son correctas (y bastante completa y explicativa), yo diría que la respuesta a tu pregunta es no.
Para ser más claros, la detención problema no es específico de problema, pero una clase de problemas, uno para cada máquina (o clase de máquinas) $X$.
Cada superior (onu)decidability problema es sólo una versión de una de detener problema para una máquina adecuada de $X$. El hecho de que hay máquinas que calculan más de otras máquinas (e.g a través de oráculos), se refleja en sus correspondientes detener los problemas.
En este sentido, no undecidability problema es diferente detener el problema (y la respuesta a tu pregunta es no y ya se ha insinuado, en este sentido, otra respuesta).
Sin embargo, si uno se refiere a un específico detener problema (e.g para el clásico de la máquina de turing universal), a continuación, como ya se ha dicho hay undecidability problemas que puede ser denominado como más difícil (me.e turing grados, etc..)
Algunas referencias (relacionados con la primera respuesta):
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
