¿Se podría "resolver" el problema de detención escapando a una descripción de cómputo de nivel superior?

21

Recientemente escuché una analogía interesante que afirma que la prueba de Turing de la indecidibilidad del problema de detención es muy similar a la paradoja de barbero de Russell.

Así que me pregunté: los matemáticos finalmente lograron hacer que la teoría de conjuntos sea coherente al pasar de la formulación ingenua del campo de Cantor a un sistema de axiomas más complejo (teoría de conjuntos de ZFC), haciendo importantes exclusiones (restricciones) y adiciones en el camino.

Entonces, ¿tal vez sería posible intentar obtener una descripción abstracta de la computación general que sea más poderosa y más expresiva que las máquinas de Turing, y con la que se pueda obtener una prueba existencial o incluso un algoritmo para resolver el problema de detención para una arbitraria maquina de Turing?

H2CO3
fuente
1
Bienvenido a Computer Science Stack Exchange. Lea cs.stackexchange.com/tour.si aún no lo ha hecho. --- ¿Qué probaste para un modelo más poderoso que TM? ¿Qué te está bloqueando?
babou
2
@babou Por el contrario, necesitas un modelo menos potente.
Yuval Filmus
2
@YuvalFilmus Bueno, el OP está pidiendo un modelo más poderoso, no uno más débil. --- con disculpas por H2CO3 ... Mi pregunta fue en realidad una broma, ya que es una pregunta estándar cuando la gente envía su tarea como pregunta. Por supuesto, no era apropiado aquí, ya que nadie espera que encuentre un modelo así. Espero que no lo tomes demasiado ácidamente.
babou
1
Puede que desee leer sobre Hipercomputación en.wikipedia.org/wiki/Hypercomputation .
Eric Towers

Respuestas:

15

Realmente no puedes comparar. La teoría de conjuntos ingenua tenía paradojas que fueron eliminadas por la teoría de conjuntos de ZFC. La teoría tiene que ser mejorada para lograr consistencia, ya que una suposición básica del trabajo científico es que la consistencia es alcanzable (de lo contrario, el razonamiento se convierte en un negocio arriesgado). Supongo que los matemáticos esperaban que fuera posible y trabajaron para resolver el problema.

No existe tal situación con la teoría de la computación y el problema de detención. No hay paradoja, no hay inconsistencia. Sucede que no hay una máquina de Turing que pueda resolver el problema de detención de TM. Es simplemente un teorema, no una paradoja.

Por lo tanto, puede ser que algún avance en nuestra comprensión del universo conduzca a modelos de computación más allá de lo que podemos imaginar ahora. El único evento de este tipo, en una forma muy débil, que permanece dentro del reino TM, posiblemente fue la computación cuántica. Aparte de este ejemplo muy débil que toca la complejidad (¿cuánto tiempo lleva?) En lugar de la computabilidad (¿es factible?), Dudo que alguien en este planeta tenga una pista de que la computabilidad más allá de TM es de esperar.

Además, el problema de la detención es una consecuencia directa del hecho de que las máquinas de Turing se pueden describir mediante un texto finito, una secuencia de símbolos. Esto es realmente cierto para todo nuestro conocimiento (hasta donde sabemos), y es por eso que el discurso y los libros son tan importantes. Esto es cierto para todas nuestras técnicas para describir pruebas y cálculos.

Entonces, incluso si tuviéramos que encontrar una manera de extender la forma en que calculamos, digamos con las máquinas T +. O significaría que hemos encontrado una manera de expresar el conocimiento más allá de escribir un documento finito, en cuyo caso todo esto queda fuera de mi jurisdicción (reclamo incompetencia absoluta) y probablemente de cualquier otra persona. O aún sería expresable en documentos finitos, en cuyo caso tendría su propio problema de detención para las máquinas T +. Y volverías a hacer la pregunta.

En realidad, esa situación existe a la inversa. Algunos tipos de máquinas son más débiles que las máquinas de Turing, como los autómatas limitados lineales (LBA). Sin embargo, son bastante potentes, pero se puede demostrar exactamente como se hace para TM que LBA no puede resolver el problema de detención de LBA. Pero TM puede resolverlo para LBA.

Finalmente, puede imaginar modelos computacionales más potentes introduciendo Oracle, que son dispositivos que pueden dar respuestas a problemas específicos y que un TM puede llamar para obtener respuestas, pero desafortunadamente no existe físicamente. Tal oracle-extended TM es un ejemplo de la máquina T + que consideré anteriormente. Algunos de ellos pueden resolver el problema de detención de TM (abstractamente, no de manera real), pero no pueden resolver su propio problema de detención, incluso de manera abstracta.

babou
fuente
Asumiendo que ZFC es consistente, todavía está incompleto, es decir, hay oraciones que no podemos probar ni refutar de ZFC, y esto está íntimamente relacionado con el problema de detención no solucionable, si la detención fuera solucionable podríamos probar o refutar todas las oraciones. Esto es matemática, y esto no es una inconsistencia a resolver, sino también un teorema (Gödel)
Hernan_eche
@Hernan_eche Bueno ... sí y ... ¿qué ...? Si cree que la inconsistencia no es peor que la incompletitud, ese es su juicio personal. Dudo que la mayoría de los matemáticos estén de acuerdo. Es posible que no le gusten las TM que no terminan. ¿Pero le gustaría que terminaran siempre, diciendo a veces sí y a veces no, en la misma entrada? ¿Qué pensarías de la respuesta? Y si piensas que no es determinismo ... piénsalo dos veces.
babou
He comentado solo para dejar en claro que Computer Science y Math luchan con los mismos problemas, para evitar que los lectores malinterpreten la respuesta como si las matemáticas se resolvieran, sus problemas básicos con ZFC y detener el problema eran solo un problema de informática, ese no es el caso, Hay una correspondencia uno a uno entre lo incompleto y el problema de detención, es el mismo problema. No creo que lo incompleto sea peor o mejor que la inconsistencia, pero creo que lo incompleto se convertirá en inconsistencia si desea construir sistemas de orden superior.
Hernan_eche
17

Bueno, siempre puede considerar una máquina Turing equipada con un oráculo para el problema normal de detención de la máquina Turing. Es decir, su nueva máquina tiene una cinta especial, en la que puede escribir la descripción de una máquina de Turing normal y su entrada y preguntar si esa máquina se detiene en esa entrada. En un solo paso, obtienes una respuesta, y puedes usarla para realizar más cálculos. (No importa si se trata de un solo paso o no: sería suficiente si se garantizara que estuviera en un número finito de pasos).

Sin embargo, hay dos problemas con este enfoque.

  1. Las máquinas de Turing equipadas con tal oráculo no pueden decidir su propio problema de detención: la prueba de Turing de la indecidibilidad del problema de detención común puede modificarse fácilmente a esta nueva configuración. De hecho, existe una jerarquía infinita, conocida como los "grados de Turing", generada al dar al siguiente nivel de la jerarquía un oráculo para el problema de detención del anterior.

  2. Nadie ha sugerido alguna manera de que tal oráculo pueda implementarse físicamente. Todo está muy bien como un dispositivo teórico, pero nadie tiene idea de cómo construir uno.

Además, tenga en cuenta que ZFC es, en cierto sentido, más débil que la teoría de conjuntos ingenua, no más fuerte. ZFC no puede expresar la paradoja de Russell, mientras que la ingenua teoría de conjuntos sí. Como tal, una mejor analogía sería preguntar si el problema de detención es decidible para modelos de computación más débiles que las máquinas de Turing. Por ejemplo, el problema de detención de los autómatas finitos deterministas (DFA) es decidible, ya que se garantiza que los DFA se detendrán por cada entrada.

David Richerby
fuente
Creo que su propio problema de detención es solucionable por cualquier familia de autómatas si es trivial, es decir, si todos se detienen o ninguno lo hace (lo que puede considerarse extraño en este caso).
babou
1
@babou: ¿qué pasa con los autómatas donde la máquina 0 realiza un bucle para siempre, la máquina 1 genera FALSO si su entrada es 0, de lo contrario, es VERDADERO y luego se detiene. Todas las otras máquinas emiten FALSO y luego se detienen. ¿Es esa una familia de autómatas en la que el programa 1 resuelve el problema de detención no trivial? ¿O no se trata siquiera de una familia de autómatas, debido a la falta de alguna propiedad, por ejemplo, algún tipo de composición?
Steve Jessop
@SteveJessop Bueno, usted (y Davis Richerby) probablemente tengan razón en cierto sentido. Lo que me molesta es que este es un ejemplo artificial. Usted construye una familia muy débil de tal manera que una máquina en la familia resulta ser un factor decisivo para toda la familia. Pero, como sospecha usted mismo (vea su comentario sobre la composición), puede haber alguna propiedad de cierre básica que falta para que el problema pueda ser trivializado. No tengo una respuesta lista, y estoy de acuerdo en que mi comentario necesita más calificación sobre lo que constituye una familia de autómatas, pero su contraejemplo no me convence.
babou
3

Advertencia: una respuesta filosófica / sin rigor

Esto podría ser un poco "filosófico", pero creo que se ajusta al espíritu de su pregunta.

Una máquina no repetible

Una piedra angular de la prueba del problema de detención es que una máquina de Turing se comporta como una función: para la misma entrada siempre da la misma salida. Si elimina esta propiedad, no tiene que lidiar con el problema de detención "general", en el sentido de que la máquina puede descubrir sus propias propiedades. Pero también pierde muchas de las propiedades teóricas deseables de tal máquina.

Eliminar propiedades

Es un poco como pasar de la teoría de conjuntos a la teoría de categorías: pierdes algunas de las "paradojas" al perder las limitaciones. Pero el resultado es mucho más difícil de manejar.

En este caso significa: no tendría idea si la máquina le presenta el resultado "correcto". Tan pronto como pueda decidir qué resultado es correcto, debe lidiar con algún tipo de "problema de detención" aplicando la máquina a sí mismo y construyendo una contradicción. Entonces, tal máquina probablemente no sería muy útil.

stefan.schwetschke
fuente
1
Gracias, esa cosa de "máquina no repetible" suena bastante interesante, en realidad. No me siento lo suficientemente competente como para decir cómodamente algo de sabiduría sobre programas inteligentes de autoinspección (porque mi instinto es que todavía se pueden expresar como máquinas de Turing), pero creo que pueden ser muy útiles para algunos problemas.
H2CO3
1
¿Cómo daría un ejemplo de no repetibilidad? ¿Cómo definirías la detención en ese caso? Una gran dificultad es que, cuando intentas definir un modelo de cálculo extraño, generalmente gedanken, tienes que definir el significado de la detención, y qué tipo de entrada se supone que la máquina de decisión debe analizar, y posiblemente algunas otras cosas no triviales. Véase, por ejemplo, el caso del no determinismo . Sin mencionar el tema de lo que puede considerarse un modelo computacional (probablemente no una colección ad hoc de máquinas).
babou
1
@ H2CO3 Una máquina no repetible es solo una especie de "experimento Gedanken" sobre qué propiedad tiene que sacrificar para salir del "problema general de detención" (construir una contradicción dejando que la máquina se inspeccione a sí misma). Obtendrá una máquina que a veces es correcta, pero no sabe cuándo. Es como el programa que calcula los números de lotería para la próxima semana. Puedo proporcionarle fácilmente dicho programa. Lo difícil es que usted decida cuál de los muchos programas que le daré es el correcto ...
stefan.schwetschke
2

El problema de detención no se formuló para expresar las limitaciones de las máquinas de Turing, sino para expresar una limitación de todos los sistemas lógicos que se pueden expresar utilizando un número finito de símbolos. Una vez que un sistema lógico tiene la capacidad de expresar las soluciones a problemas de cierta complejidad, también tendrá la capacidad de expresar problemas que no puede resolver. Cualquier extensión de un sistema lógico suficiente para expresar soluciones a todos los problemas que antes no podía resolver también incluirá la capacidad de expresar nuevos problemas que no puede resolver.

Dada cualquier especificación particular de "Máquina de Turing mejorada", sería posible especificar una "Máquina de Turing súper mejorada" que podría examinar un programa para el ETM e informar si se detendría, pero el SETM solo podría analizar programas para ETM: no podría analizar los programas SETM. No hay forma de definir una máquina que pueda analizar los programas por sí misma y determinar si se detienen porque el hecho de agregar nuevas funciones crearía nuevos requisitos para un autoanalizador, y no hay forma de hacer que las funciones "se pongan al día" con los requisitos .

Super gato
fuente
1

Dichas máquinas se han previsto y se denominan máquinas super-Turing . Varias clases principales de máquinas de super-turing son

  • Máquinas de números reales (es decir, computadoras analógicas)
  • Máquinas de Turing con tiempo infinito
  • Máquina de turing no determinista

No todas las máquinas de super-turing pueden resolver el problema de detención (las máquinas de turing no deterministas, en particular, no pueden). Sin embargo, las máquinas conceptuales se han creado, al menos en experimentos mentales.

Cort Ammon - Restablece a Monica
fuente