¿Existe un par de máquinas de Turing 'ortogonales' que no se detienen?

Question

Voy a explicar lo que quiero decir por ortogonal, que es probablemente una mala elección de palabras por mi parte.

Dadas dos máquinas de Turing $\lambda $$\tau$, y dos entradas de $i$$j$. vamos a decir $\tau(i) \preceq \lambda(j)$, si hay una prueba de $P$, lo que indica que $\tau(i)$ detiene si $\lambda(j)$ se detiene. Como un ejemplo de hasta donde podría haber $\tau(i) \preceq \lambda(i)$. Por ejemplo, $\lambda$ puede simplemente realizar el cálculo de $1+1$, y, a continuación, ejecute $\tau(i)$.

A lo que me refiero es ortogonal noncomparable virtud de la presente orden. Que es ¿existe un par de máquinas de turing $\lambda$ $\tau$ e insumos $i$$j$, donde ni la $\lambda(j) \preceq \tau(i)$ ni $\tau(i) \preceq \lambda(j)$

Yo creo que se puede demostrar que para una fija no frenar $\tau(i)$, no podemos tener a $\tau(i) \preceq \lambda(j)$ todos los $\lambda(i)$. Desde entonces podríamos usar esto para crear una máquina para resolver la paralización problema, mediante la enumeración de las pruebas hasta encontrar una prueba de que $\tau(i) \preceq \lambda(j)$. La existencia de una prueba, a continuación, nos da ese $\lambda(j)$ no se puede detener como $\tau(i)$ no.

Sin embargo, este resultado es mucho más débil que mi objetivo.

Answer 1

Sí.

En primer lugar, por supuesto, usted debe decidir sobre una teoría en la cual la prueba de $P$ es para ser llevado a cabo. Vamos a llamar a esta $T$, y se supone que $T$ es verdadera y bien portados suficiente para que el conjunto de consecuencias de $T$ es recursivamente enumerable. Por ejemplo, $T$ podría ser PA o ZFC.

Ahora vamos a $P$ ser el siguiente programa (en algunos adecuado formalismo):

1. Leer la entrada $K$.
2. Búsqueda de todas las consecuencias de $T$.
3. La primera vez que una consecuencia de la forma $$ T\vdash K\text{ run with input }K\text{ does }not\text{ output }n $$ para un número $n$, detener y salida de $n$.

Ahora, si ejecutamos $P$ con sí mismo como entrada, no siempre va a terminar, porque sólo puede terminar si se ha demostrado (en la verdadera teoría de la $T$) que no lo es, de hecho, a punto de hacer.

Por otro lado, para cada $n$ es consistente con $T$ que $P(P)$ salidas $n$ -- porque de lo contrario $T$ probaría (por contradicción) que $P(P)\ne n$ que $n$, lo que significaría que $P(P)$ no puede divergir, lo que contradice el argumento de que esta justo encima.

Ahora vamos a $\tau$ ser una máquina que (ignora su entrada y) simula la ejecución de $P$ sobre sí misma, y termina iff $P(P)$ salidas 1.

Deje $\lambda$ ser la máquina que simula la ejecución de $P$ sobre sí misma, y termina iff $P(P)$ 2 salidas.

Ahora, ya que es consistente con $T$ que $P(P)=1$, $T$ no va a ser capaz de demostrar "$\tau\text{ halts}\Rightarrow \lambda\text{ halts}$". A la inversa, ya que es consistente con $T$ que $P(P)=2$, $T$ no se puede demostrar "$\lambda\text{ halts}\Rightarrow\tau\text{ halts}$".

(Esta construcción es ligeramente simplificada a partir de la discusión al final de la sección 4.2 de Pudlák, Fundamentos Lógicos de la Matemática y de la Complejidad Computacional, que atribuye la idea original de Mostowski).