¿Hay algún problema específico que se sepa que es indecidible por razones distintas a la diagonalización, la autorreferencia o la reducibilidad?

28

Cada problema indecidible que conozco pertenece a una de las siguientes categorías:

  1. Problemas que son indecidibles debido a la diagonalización (autorreferencia indirecta). Estos problemas, como el problema de detención, son indecidibles porque podría usar un supuesto decisor para el lenguaje para construir una TM cuyo comportamiento conduce a una contradicción. También podría agrupar muchos problemas indecidibles sobre la complejidad de Kolmogorov en este campo.

  2. Problemas que son indecidibles debido a la autorreferencia directa. Por ejemplo, se puede demostrar que el lenguaje universal es indecidible por la siguiente razón: si fuera decidible, entonces sería posible usar el teorema de recursión de Kleene para construir una TM que tenga su propia codificación, pregunte si aceptará su propia entrada. , entonces hace lo contrario.

  3. Problemas que son indecidibles debido a las reducciones de los problemas indecidibles existentes. Buenos ejemplos aquí incluyen el problema de correspondencia posterior (reducción del problema de detención) y el problema Entscheidungs.

Cuando enseño la teoría de la computabilidad a mis alumnos, muchos alumnos también se dan cuenta de esto y, a menudo, me preguntan si hay algún problema que podamos probar que no se pueda resolver sin finalmente remontarse a algún tipo de truco de autorreferencia. Puedo demostrar de manera no constructiva que hay infinitos problemas indecidibles por un simple argumento de cardinalidad que relaciona el número de TM con el número de idiomas, pero esto no da un ejemplo específico de un lenguaje indecidible.

¿Se sabe que algunos idiomas son indecidibles por razones que no se enumeran anteriormente? Si es así, ¿qué son y qué técnicas se usaron para mostrar su indecidibilidad?

computability proof-techniques undecidability templatetypedef
fuente
@EvilJS Comprendí que la prueba de indecidibilidad implicaba la capacidad de simular TM, aunque ¿quizás estoy equivocado?
templatetypedef
Puede decir que el teorema de Rice podría no encajar en ninguna de estas categorías, pero la prueba del teorema sí.
Ryan
1
@EvilJS Ese es un buen punto. Realmente, lo que estoy buscando aquí es si hay alguna técnica fundamentalmente diferente que podamos usar. Sería bueno, por ejemplo, si alguien identificara un problema como indecidible en un caso en el que ese problema no tiene una relación conocida con la autorreferencia de TM o un argumento de tipo Godeling. Si lo mejor que podemos hacer es "descubrimos esto hace mucho tiempo, luego nos dimos cuenta de que es más fácil demostrarlo de otra manera", que en cierto sentido sería una respuesta: las tres técnicas anteriores explican fundamentalmente todas las pruebas de indecidibilidad que conocemos.
templatetypedef
2
La función de castor ocupado crece demasiado rápido para que cualquier programa pueda calcularla. Concretamente, puede definir una función como una más el número más grande calculado por un programa de longitud como máximo . ¿Eso cuenta como diagonalización? F(norte)norte
Yuval Filmus
1
@YuvalFilmus Tal vez estoy siendo demasiado estricto aquí, pero eso me parece un argumento de tipo diagonal: estás construyendo una función que se define como diferente de todas las funciones calculadas por TM.
templatetypedef

Respuestas:

10

Sí, hay tales pruebas. Se basan en el teorema de base baja .

Vea esta respuesta a ¿Hay alguna prueba de la indecidibilidad del problema de detención que no depende de autorreferencia o diagonalización? pregunta sobre teoría para más.

Kaveh
fuente
Si alguien está interesado en técnicas avanzadas en teoría de la computabilidad, consulte los libros de Robert I. Soare Conjuntos y grados recursivamente enumerables y Teoría y aplicaciones de la computabilidad .
Kaveh
Corríjame si me equivoco, pero ¿la prueba del teorema de la base baja no implica aplicar un funcional a sí mismo y preguntar si no produce un valor? Si es así, ¿no es solo una capa de indirección sobre un argumento diagonal?
templatetypedef
@templatetypedef, no soy un experto pero hasta donde entiendo no. Ver, por ejemplo, la página 109 en el libro de Soare.
Kaveh
@templatetypedef, ps1: hay cierta vaguedad en la pregunta sobre lo que consideramos diagonalización. Si no tenemos cuidado, podemos expandir lo que consideramos diagonalización cada vez que vemos algo que no era. Tome, por ejemplo, métodos de prioridad o cualquier método general de construcción de objetos, parte por parte, para evitar ser igual a cualquier objeto de una clase dada.
Kaveh
2
@David, :) Abro la página del libro que quiero compartir, hago clic en el botón Compartir en la parte superior y elimino los parámetros excepto el idy pgdel enlace.
Kaveh
0

Esta no es exactamente una respuesta afirmativa, sino un intento de hacer algo cercano a lo que se solicita a través de un ángulo creativo. ahora hay bastantes problemas en física que están "muy distantes" de las formulaciones matemáticas / teóricas de indecidibilidad, y parecen cada vez más "remotos" y "tienen poca semejanza" con las formulaciones originales que involucran el problema de detención, etc .; por supuesto, utilizan el problema de detención en la raíz, pero las cadenas de razonamiento se han vuelto cada vez más distantes y también tienen un fuerte aspecto / naturaleza "aplicado". desafortunadamente todavía no parece haber grandes encuestas en esta área. Un problema reciente que fue "sorprendentemente" demostrado indecidible en física que ha atraído mucha atención:

La brecha espectral, la diferencia de energía entre el estado fundamental y el primer estado excitado de un sistema, es fundamental para la física cuántica de muchos cuerpos. Muchos problemas abiertos desafiantes, como la conjetura de Haldane, la cuestión de la existencia de fases líquidas de espín topológico con espacios vacíos y la conjetura de huecos de Yang-Mills, se refieren a huecos espectrales. Estos y otros problemas son casos particulares del problema general de la brecha espectral: dado el hamiltoniano de un sistema cuántico de muchos cuerpos, ¿está vacío o sin huecos? Aquí demostramos que este es un problema indecidible. Específicamente, construimos familias de sistemas de espín cuántico en una red reticular bidimensional con interacciones de vecino vecino, invariablemente traslacionales, para las cuales el problema del espacio espectral es indecidible. Este resultado se extiende a la indecidibilidad de otras propiedades de baja energía,

lo que parece observar en la pregunta es que todas las pruebas de indecidibilidad (informalmente) tienen una cierta estructura "autorreferencial", y esto se ha demostrado formalmente en matemáticas aún más avanzadas, de modo que tanto el problema de Turing como el teorema de Godels pueden ser visto como instancias del mismo fenómeno subyacente. ver por ejemplo:

El teorema de detención, el teorema de Cantor (el no isomorfismo de un conjunto y su conjunto de poder) y el teorema de incompletitud de Goedel son todas instancias del teorema del punto fijo de Lawvere, que dice que para cualquier categoría cerrada cartesiana, si hay un mapa epimórfico e: A → (A⇒B), entonces cada f: B → B tiene un punto fijo.

También hay una larga meditación sobre este tema de la interconexión (¿intrínseca?) de autorreferencialidad e indecidibilidad en los libros de Hofstadter. Otra área donde los resultados de indecidibilidad son comunes e inicialmente algo "sorprendentes" es con los fenómenos fractales. La apariencia transversal / importancia de los fenómenos indecidibles en la naturaleza es casi un principio físico reconocido en este punto, observado por primera vez por Wolfram como "principio de equivalencia computacional" .

vzn
fuente
otra "/ sorprendente aplica" zonas de indeterminación: embaldosados aperiódicos , eventual estabilización en Conway juego de la vida ( autómatas celulares )
VZN
3
Tengo entendido que las pruebas de que todos estos problemas son indecidibles se reducen a reducciones del problema de detención. ¿Eso es incorrecto?
templatetypedef
la respuesta básicamente admite que (todos los resultados conocidos de indecidibilidad pueden reducirse al problema de detención). su pregunta está casi redactada como una conjetura, y no tengo conocimiento de ningún conocimiento en conflicto, y veo mucha evidencia circunstancial a favor de ella. pero lo más parecido a una prueba formal conocida es aparentemente las formulaciones de indecidibilidad de punto fijo (no parece haber otras formulaciones formales de "autorreferencial"). Otra forma de decirlo todo es que la integridad y la indecidibilidad de Turing son dos puntos de vista de esencialmente el mismo fenómeno.
vzn