Para $x, y\in 2^\omega$, decir $x$ es totalmente reducible a $y$ - y escribir "$x\le_{Tot}y$" - si existe alguna máquina de Turing $\Phi_e$ que es total en cada oracle (es decir, $\Phi_e^z$ es total para todos los $z\in 2^\omega$) tal que $\Phi_e^y=x$.
Es un puro ejercicio* para mostrar que $\le_{Tot}$ no es el mismo estándar de Turing reducibilidad, $\le_T$. Por otro lado, comparte algunas propiedades básicas:
$\le_{Tot}$ es un preorder en $2^\omega$ con el contable predecesor de la propiedad.
La inducida por la estructura de las titulaciones $\mathcal{T}=2^\omega/\equiv_{Tot}$ es superior semilattice (con la habitual combinación).
$\mathcal{T}$ tiene pareja exacta de la propiedad (el argumento habitual aún funciona).
Y algunas otras propiedades básicas, también.
Estoy interesado en todo lo que se conoce acerca de la poset $\mathcal{T}$, y, en particular, la comparación de $\mathcal{T}$ con el estándar poset de Turing grados $\mathcal{D}=2^\omega/\equiv_T$. Ya que hay un montón de posibles preguntas aquí, permítanme preguntar específicamente:
Qué $\mathcal{T}$ tiene más límites inferiores de los pares de elementos?
Por supuesto, glbs de pares de elementos que no siempre existen en $\mathcal{D}$, pero como lo que yo puedo decir que la prueba no se aplican inmediatamente a $\mathcal{T}$.
*Fix $x$ no computable y deje $\Phi_c$ ser el oráculo de la máquina que, con oracle $z$ y de entrada de $n$, paradas y salidas de 0 si "$01^{2n}0$" ocurre antes de"$01^{2n+1}0$"$z$, y se detiene y salidas de 1 si "$01^{2n+1}0$" ocurre antes de"$01^{2n}0$"$z$. Podemos construir una $y$ tal que $\Phi_c^y=x$ pero $x\not\le_{Tot}y$, por diagonalizing en contra de todos los total-en-todos-los oráculos de índice. Dejando $e$ ser un índice, y después de haber construido algunas segmento inicial $y_s$$y$, podemos "agregar suficiente 0s": hay algo de $k$ tal que $\Phi_e^{y_s^\smallfrown 0^k}(m)\downarrow\not=x(m)$ algunos $m$ (desde $x$ es no computable). La reducción de la $\Phi_c$ ignora las cadenas de ceros, por lo que podemos alternar entre la codificación de $x$ a $y$ y la adición de cadenas largas de ceros a diagonalize contra total-en-todos-los oráculos de las reducciones.
