Problema de detención sin autorreferencia

En el problema de detención, nos interesa saber si hay una máquina Turing que pueda decir si una máquina Turing detiene o no en una entrada dada . Por lo general, la prueba comienza asumiendo que tal existe. Luego, consideramos un caso en el que restringimos a , y luego derivamos una contradicción al usar una instancia de un argumento diagonal. Estoy interesado en cómo sería la prueba si se nos promete que ? ¿Qué pasa con la promesa , donde es funcionalmente equivalente a ? $T$ $M$ $i$ $T$ $i$ $M$ $i \not = M$ $i \not = M^\prime$ $M^\prime$ $M$

computability undecidability halting-problem Bellpeace
fuente

Un consejo: incluso si no está obligado a contestar correctamente preguntas sobre sí mismo o, incluso, sobre 's equivalente a ella, todavía podemos darle de comer un equivalente y ver lo que hace. Como no es computable si es equivalente a , no podrá decir que tiene algo equivalente a sí mismo.

M

$M$

M^{'}

$M'$

M^{'}

$M'$

M^{'}

$M'$

M

$M$

M

$M$

Andrej Bauer

@AndrejBauer ¿Fue solo una pista que me diste y debería resolver mi problema real usando esta pista? Estoy un poco confundido, ya que relaja el problema diciendo "no requiere", donde en mi contexto tengo la promesa de que no será alimentado con un equivalente . Básicamente, me gustaría ver si hay algún tipo de "autorreferencia" que haga que los problemas sean indecidibles. Se pensaba que este es el caso cuando hablamos de lógica e incompletitud.

M

$M$

M^{'}

$M^\prime$

bellpeace

Puedes romper la promesa y alimentar a lo que quieras. No puede decir que rompiste la promesa, de todos modos. Si crees que es trampa, entonces alimentaré cosas que no son equivalentes a porque son como pero con todas las entradas desplazadas por , o algo así.

M

$M$

M

$M$

M

$M$

M

$M$

1

$1$

Andrej Bauer

En realidad, sus preguntas no están bien formuladas. Debe describir la prueba real que tiene en mente y luego especificar qué es exactamente lo que desea evitar. No creo que te refieras a , sino a otra cosa.

i \neq M

$i \neq M$

Andrej Bauer

Respuestas:

Supongamos que HALTS es una TM que lee su entrada como un par y , donde es una codificación TM y es cualquier entrada a esa TM. $M$ $x$ $M$ $x$

Su pregunta es si ¿qué pasaría si asumimos HALTS resolvió el problema de la parada para todas las entradas tal que no es una codificación de un TM que es funcionalmente equivalente a . $\langle M,x \rangle$ $x$ $M$

Afirmo que esto implica una contradicción. Se me ocurrió esto en el acto, así que agradezco cualquier crítica de mi prueba. La idea de la prueba es que, en lugar de diagonalizar algo en sí mismo, hacemos dos TM mutuamente recursivas que se comportan de manera diferente en alguna entrada (por lo tanto, no son funcionalmente equivalentes), pero de lo contrario causan contradicciones.

Supongamos que y son dos TM mutuamente recursivas (es decir, podemos simular, imprimir, etc., la descripción de dentro del programa de y viceversa). Tenga en cuenta que podemos hacer TM recursivas mutuamente a partir del teorema de recursividad. $D_1$ $D_2$ $D_2$ $D_1$

Defina y siguiente manera: en la entrada , si (10 elegidos arbitrariamente), luego acepta y bucles. (Por lo tanto, no son funcionalmente equivalentes). $D_1$ $D_2$ $x$ $|x| < 10$ $D_1$ $D_2$

Entrada dada con , defina para simular HALTS en y si detiene o si bucle. $x$ $|x| \ge 10$ $D_1$ $\langle D_2, x \rangle$ $D_2$ $D_2$

Entrada dada con , defina para simular HALTS en y bucle si detiene o se detiene si se . $x$ $|x| \ge 10$ $D_2$ $\langle D_1, x \rangle$ $D_1$ $D_1$

Luego tenga en cuenta que para cualquier con , (x) se detiene o se repite. Si detiene en la entrada x, entonces sabemos que HALTS ( , x) determinó que detiene en la entrada x. Sin embargo, la detención de en la entrada x implica que HALTS ( , x) se . $x$ $|x| \ge 10$ $D_1$ $D_1$ $D_2$ $D_2$ $D_2$ $D_1$

Si en la entrada bucles, la contradicción sigue de manera similar. $D_1$ $x$

Esto es una contradicción a menos que sea una codificación para una máquina de turing funcionalmente equivalente a o , en cuyo caso HALTS tiene un comportamiento indefinido. Sin embargo, se eligió de forma arbitraria entre todas las cadenas de tamaño superior a . Por lo tanto, queda por demostrar que existe una máquina de Turing con una codificación de tamaño superior a 10 que se comporta de manera diferente a y . Podemos construir tal máquina de manera trivial. QED $x$ $D_1$ $D_2$ $x$ $10$ $D_1$ $D_2$

Pensamientos?

Kurt Mueller
fuente

¿Por qué necesita asegurarse de que y no sean funcionalmente equivalentes?

D_{1}

$D_1$

D_{2}

$D_2$

bellpeace

Creo que tienes razón en que esto no es necesario. Mi intención original era diagonalizar en HALT ( )

⟨ D_{1}, D_{2} ⟩

$\langle D_1, D_2 \rangle$

Kurt Mueller

Sin eso, la prueba es más elegante, pero de todos modos me parece bien y es exactamente lo que necesitaba.

bellpeace

Aún no estás fuera del bosque. Te encuentras con el mismo problema, solo que ahora le das una TM diferente, como entrada, donde has elegido para que sea funcionalmente equivalente a (digamos que agregas una nueva regla a para que movimientos de apertura de son un paso a la derecha, un paso a la izquierda y de lo contrario no realiza cambios). Aún te encontrarás con una contradicción. Puede intentar eliminar todas las TM que son equivalentes a , pero ese es un conjunto indecidible. $M'$ $M'$ $M$ $M$ $M'$ $M$

Actualización . Arregle un esquema de codificación donde denota la descripción bajo ese esquema de una TM y suponga que tenía una TM, donde $\langle\,M\,\rangle$ $M$ $H$

$H(\langle\,M\,\rangle, x)$ no está definido cuando es la codificación de una TM que calcula la misma función parcial que (es decir, y son funcionalmente equivalentes). $x$ $H$ $x$ $H$
Para todas las demás entradas, devuelve verdadero si y solo si detiene. $H(\langle\,M\,\rangle, x)$ $M(x)$

Ahora la construcción de diagonalización habitual todavía resulta en una contradicción. Definir una TM por $Q$

Q(x)=
  if H(<Q>, x) = false
    return true
  else
    loop forever

Claramente, y son funcionalmente no equivalentes, por lo que podemos dejar que y encontrar que detiene si y solo si no se detiene, entonces no puede haber tal TM . $Q$ $H$ $x=\langle\,Q\,\rangle$ $Q(\langle\,Q\,\rangle)$ $H$

Rick Decker
fuente

Y supongamos que tengo una promesa de que no es una MT funcionalmente equivalente a ? ¿Quizás pueda extender mi pregunta en el OP?

i

$i$

M

$M$

bellpeace

Supongamos que se le da tal promesa; Sé que no es computable. He actualizado el OP.

bellpeace

@bellpeace: ¿Cómo se define eso?

$\:$

$\;\;\;\;$

Entrada: un par de enteros de tal manera que no representa un TM funcionalmente equivalente a TM representado por . Salida: si detiene en , contrario. ¿Es este problema decidible?

(M, i)

$(M, i)$

i

$i$

M

$M$

1

$1$

M

$M$

i

$i$

0

$0$

bellpeace

M

$M$

M^{'}

$M^\prime$