Problema de detención sin autorreferencia

10

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 ?M i T i M i M i M TMiTiMiMiM MMM

Bellpeace
fuente
2
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 MMMMMMM
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. MM
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 MMMMM1
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. iM
Andrej Bauer

Respuestas:

7

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.x M xMxMx

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 .x MM,xxM

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 2 D 2 D 1D1D2D2D1

Defina y siguiente manera: en la entrada , si (10 elegidos arbitrariamente), luego acepta y bucles. (Por lo tanto, no son funcionalmente equivalentes).D 2 x | x | < 10 D 1 D 2D1D2x|x|<10D1D2

Entrada dada con , defina para simular HALTS en y si detiene o si bucle.| x | 10 D 1D 2 , x D 2 D 2x|x|10D1D2,xD2D2

Entrada dada con , defina para simular HALTS en y bucle si detiene o se detiene si se .| x | 10 D 2D 1 , x D 1 D 1x|x|10D2D1,xD1D1

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|10D1D1D2D2D2D1

Si en la entrada bucles, la contradicción sigue de manera similar.D1x

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. QEDxD1D2x10D1D2

Pensamientos?

Kurt Mueller
fuente
¿Por qué necesita asegurarse de que y no sean funcionalmente equivalentes? D1D2
bellpeace
Creo que tienes razón en que esto no es necesario. Mi intención original era diagonalizar en HALT ( )D1,D2
Kurt Mueller
Sin eso, la prueba es más elegante, pero de todos modos me parece bien y es exactamente lo que necesitaba.
bellpeace
2

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.MMMMMM


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, dondeMMH

  • H(M,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).xHxH
  • Para todas las demás entradas, devuelve verdadero si y solo si detiene.M ( x )H(M,x)M(x)

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

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 .H x = QHQ ( x=QHQ(Q)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? MiM
bellpeace
1
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? i M 1 M i 0(M,i)iM1Mi0
bellpeace
1
MM