¿P contiene idiomas incomprensibles? (Wiki de la comunidad TCS)

Respuesta: no conocida

Muchas gracias a todos los que ayudaron a refinar esta pregunta y las definiciones asociadas.

Las definiciones de esta wiki proporcionaron el punto de partida para la wiki TCS más reciente " ¿Contiene P lenguajes cuya existencia es independiente de PA o ZFC? (Wiki de la comunidad TCS) ".

Se prefiere el wiki más reciente porque sus definiciones y nomenclatura son sustancialmente más sofisticadas que las de este wiki más antiguo.

En particular, la nomenclatura de esta wiki más antigua incomprensible lenguajes comprensibles y TMs es suplantada en la nueva wiki por críptico gnostic . Además de los detalles de definición, que sin embargo son importantes, los dos wikis abordan una clase similar de preguntas. $\Leftrightarrow$ $\Leftrightarrow$

Más respuestas son bienvenidas

Se aceptan más respuestas (no hace falta decirlo), y es probable que sea apropiado realizar más ajustes de definición. Una lección principal ha sido que esta clase de preguntas es difícil de formular y aún más difícil de responder rigurosamente.

Como antecedentes, la respuesta de Sasho Nikolov fue calificada como "aceptada", ya que proporcionó una formulación que capturó la intención de la pregunta: la respuesta a la pregunta es (aparentemente) desconocida.

La valiosa respuesta de Philip White motivó la definición gradual de TMs que son incomprensibles, versus fuertemente incomprensibles, versus canónicamente incomprensibles (según la lista "definiciones graduadas de incomprensibilidad" a continuación).

La siguiente declaración de la pregunta incorpora provisionalmente valiosas ideas y sugerencias proporcionadas por Tsuyoshi Ito, Marzio De Biasi, Huck Bennett, Ricky Demer, Peter Shor, y también una valiosa publicación en el blog de Luca Trevisan .

Definicion formal

Las máquinas de Turing incomprensibles se definen (dentro de ZFC) de la siguiente manera:

D1 Dada una máquina de Turing M que probablemente se detiene para todas las cadenas de entrada, M se llama incomprensible si la siguiente afirmación no es demostrable ni refutable para al menos un número real semidefinido positivo : $r$

Declaración: el tiempo de ejecución de M es con respecto a la longitud de entrada ${O}(n^r)$ $n$

Por el contrario, M se llama comprensible si no es incomprensible.

Decidible ambiguo

La entrada de Wikipedia " Problema indecidible: ejemplos de declaraciones indecidibles " revisa de manera concisa los diferentes sentidos del término "indecidible" que son habituales en la literatura teórica de la prueba versus la teoría de la computabilidad. Con el fin de evitar la ambigüedad, las definiciones y preguntas formuladas emplean exclusivamente la terminología "ni demostrable ni refutable".

Otras referencias a este respecto son las notas del curso de Jeremy Avigad " Incompleteza a través del problema de detención ", el ensayo del blog de Scott Aaronson " El teorema de Rosser a través de las máquinas de Turing " y la publicación del blog de Luca Trevisan. Dos preguntas interesantes .

Sobre la existencia de máquinas de Turing incomprensibles

La existencia de máquinas incomprensibles de Turing se deriva concretamente de una construcción de Emmanuele Viola y, en general, del marco teórico de la complejidad de Juris Hartmanis. En particular, la construcción de Viola proporciona, a través de los métodos de las notas del curso de Jeremy Avigad (según tengo entendido), el siguiente lema:

Lema [Implicación de Viola]
(si un lenguaje L es aceptado por un TM comprensible) (L es aceptado por un TM incomprensible). $\to$

Respetando la naturalidad al definir la incomprensibilidad

Es natural preguntarse si la implicación inversa a la Implicación de Viola es verdadera.

Las consideraciones de naturalidad requieren que la implicación inversa se plantee cuidadosamente, ya que el comentario de Philip White a continuación muestra cómo reducir trivialmente TMs incomprensibles a TMs comprensibles a través de polilimitadores , que son módulos computacionales que (en efecto) "rellenan" el tiempo de ejecución de una máquina incomprensible. como para reducirlo a una máquina comprensible.

En particular, es natural exigir que no " enmascaremos estéticamente viejos elementos de incomprensibilidad introduciendo nuevos elementos de incomprensibilidad ". El desafío clave asociado con la pregunta formulada es "¿Existe una definición natural de incomprensibilidad?" ... que (dada la discusión aquí de TCS) quizás deberíamos considerar como una meta-pregunta no trivial que puede tener más de una respuesta natural.

Con miras a este principio rector de la naturalidad, las definiciones graduadas de incomprensibilidad se especifican de la siguiente manera.

Definiciones graduadas de incomprensibilidad

D2 Decimos que una máquina de Turing M es eficiente si tiene un exponente de tiempo de ejecución tal que el lenguaje L que M acepta no sea aceptado por ninguna otra TM que tenga un exponente de tiempo de ejecución menor que . $r$ $r$

D3 Decimos que un lenguaje L es incomprensible si es aceptado por (a) al menos una máquina de Turing M es eficiente e incomprensible, y además (b) no hay un TM eficiente y comprensible que pueda ser comprobado (en ZFC) L.

D4 Decimos que una TM incomprensible es fuertemente incomprensible si el lenguaje que acepta es incomprensible.

D5 Decimos que una TM fuertemente incomprensible es canónicamente incomprensible si es eficiente.

Estas definiciones aseguran que cada lenguaje incomprensible sea aceptado por al menos una TM que es canónicamente incomprensible, y además, en vista de D3 (a) y D3 (b) , no existe una reducción trivial de polilimitadores de una TM canónicamente incomprensible a una TM comprensible que probablemente reconoce el mismo idioma.

Las tres preguntas formuladas

Q1 ¿La clase de complejidad P contiene lenguajes incomprensibles?

P2 ¿Se puede representar concretamente al menos un idioma incomprensible? (Si es así, proporcione un ejemplo constructivo).

P3 ¿Se puede representar concretamente al menos una TM canónicamente incomprensible? (Si es así, proporcione un ejemplo constructivo).

Motivación

Las propiedades incomprensibles de la clase de complejidad P obstruyen la comprensión de una amplia clase de problemas que (para el proponente original de esta pregunta ) incluyen el Rompecabezas de isleños de ojos azules de Terry Tao, el Juego de elección de urna de Dick Lipton y Ken Regan , y su hibridación en El contexto de la paradoja de Newcomb a través del juego Newcomb de ventaja equilibrada .

Como dice la monografía de Juris Hartmanis Cálculos factibles y propiedades de complejidad demostrables (1978):

Los resultados sobre la complejidad de los algoritmos cambian radicalmente si consideramos solo las propiedades de los cálculos que pueden probarse formalmente.

La lucha por construir definiciones y postulados bien planteados que capturen la visión de Hartmanis nos ayuda a comprender mejor que la clase de complejidad P tiene algunos lenguajes extremadamente peculiares, que son reconocidos por máquinas Turing extremadamente peculiares, cuyas propiedades somos (en la actualidad ) muy lejos de agarrar. Llama la atención que, en un sentido completamente riguroso, actualmente no se sabe si la clase de complejidad P es comprensible.

Muchas gracias a todos los que han contribuido con comentarios y respuestas.

cc.complexity-theory complexity-classes turing-machines decidability revs John Sidles
fuente

Defina el término "(una máquina de Turing) de manera decidible en P."

Tsuyoshi Ito

En el problema establecido en la definición de "incomprensible en P", ¿cuál es exactamente la entrada? ¿La máquina de Turing es parte de la entrada o está fija? Además, ¿cómo se especifica un número real como una cadena?

Tsuyoshi Ito

La definición no tiene sentido, me temo. La reducción de Viola muestra que cuando la máquina Turing es parte de la entrada junto con , su tiempo de ejecución es indecidible. Pero si sacamos la máquina de Turing de la entrada y arreglamos un idioma para cualquier máquina de Turing, entonces el problema se vuelve decidible (porque se nos permite construir una TM decisiva específicamente para una máquina de Turing ).

r

$r$

M

$M$

Sasho Nikolov

Como Sasho explicó de manera preventiva, el problema planteado en la definición de "incomprensible" en la revisión 4 es decidible para cada M. Me temo que está cometiendo un error elemental aquí. Si aún tiene problemas para entenderlo, esta publicación de Raphael y el enlace pueden ser útiles. He votado para cerrar esto como una pregunta no real.

Tsuyoshi Ito

Tu definición sigue siendo mala. Dada una máquina de Turing incomprensible en P, puede convertirla en una máquina de Turing comprensible en P colocando un temporizador que cuente los pasos de , y si no se detiene para entonces, la detiene y la rechaza. Para cualquier máquina de Turing incomprensible en P, hay una y una que la convertirán en una máquina de Turing comprensible que acepte el mismo lenguaje. Por supuesto, no puede probar que acepta el mismo lenguaje, y no puede encontrar los valores correctos de C y k , pero no veo cómo puede incorporar esto en su definición.

C n^{k}

$Cn^k$

C

$C$

k

$k$

Peter Shor

Respuestas:

(Me retiro como ya no es relevante la parte de la respuesta que solo explica por qué no hay instancias indecidibles de un problema / no hay algoritmos de polytime con límite de tiempo no controlable)

Ahora la pregunta ha cambiado a una pregunta sobre TMs cuyo tiempo de ejecución es demostrable en alguna teoría lógica. Para cualquier teoría lógica (lo suficientemente potente) , existe una máquina cuyo tiempo de ejecución es polinómica pero tanto la frase "el tiempo de ejecución de es polinómica" y su negación no se puede probar en . En particular, eso significa que hay Polytime TMs cuyo tiempo de ejecución limitado no se puede probar en ZFC. Esto debería seguir a la reducción de Viola con algunos trucos adicionales como en la publicación del blog de Scott. Pero en lugar de resolver esto, mira el último comentario de Luca en esta publicación de blog . En cierto modo, Luca responde tu pregunta aquí. Él muestra que: $T$ $M$ $M$ $T$

existe una máquina polytime tal que ZFC no puede probar que no toma tiempo exponencial $M$ $M$
para cualquier máquina polytime existe una máquina que decide el mismo lenguaje y cuyo tiempo de ejecución es demostrablemente (en ZFC, por ejemplo) polinomial (la simple simulación que demuestra esto también fue ofrecida por Peter Shor en un comentario) $M$ $M'$

Por lo tanto, parece que la respuesta a su pregunta es "no": cualquier lenguaje decidible en polytime por alguna máquina es decidido por una máquina polytime demostrable. Pero tal vez tu pregunta debería ser:

¿existe una máquina de polytime tal que cualquier máquina que decida el mismo idioma o no se pueda probar (en ZFC) para decidir el mismo idioma que o no se pueda probar (en ZFC) que se ejecute en tiempo polinómico? $M$ $M'$ $M$

Sospecho que la respuesta es sí, pero en este momento no tengo más tiempo para dedicarlo.

Sasho Nikolov
fuente

------ Hay dos sentidos distintos de la palabra indecidible en matemáticas y ciencias de la computación. El primero de ellos es el sentido teórico de la prueba utilizado en relación con los teoremas de Gödel, el de una declaración que no es demostrable ni refutable en un sistema deductivo específico. ... Debido a los dos significados de la palabra indecidible, el término independiente a veces se usa en lugar de indecidible para el sentido "ni demostrable ni refutable".

John Sidles

Gracias Sasho! También llegué a esta apreciación, pero el postulado puede modificarse mediante la distinción de Wikipedia: "Hay dos sentidos distintos de la palabra indecidible en matemáticas y ciencias de la computación. El primero de ellos es el sentido teórico de la prueba utilizado en relación con los teoremas de Gödel, la de una declaración que no es ni demostrable ni refutable en un sistema deductivo específico ... Debido a los dos significados de la palabra indecidible, el término independiente a veces se usa en lugar de indecidible para el sentido 'ni demostrable ni refutable' ". Por lo tanto, espero aclarar la pregunta más tarde hoy.

John Sidles

Impulsado en gran parte por sus reflexivos comentarios, el atributo ambiguo "decidible" ahora ha sido reemplazado por el atributo (con suerte inequívoco) "ni demostrable ni refutable". Por lo cual se agradece su ayuda y se agradece.

John Sidles

por favor revise mi respuesta actualizada

Sasho Nikolov

Gracias Sasho Yo también tengo que tomar un descanso hasta mañana, sin embargo, en la primera lectura, su sugerencia final parece muy fructífera, y espero responderla pronto. Gracias de nuevo.

John Sidles

Solo un comentario extenso tratando de interpretar la pregunta.

Dada una máquina de Turing que $M$ ~~se promete detener~~se detiene en todas las cadenas de entrada; se llama incomprensible si y solo si al menos uno $M$ ~~número real semidefinido positivo~~entero el siguiente $r$ ~~pregunta~~el problema de decisión es indecidible (es decir, es imposible construir un algoritmo único que siempre conduzca a una respuesta correcta de sí o no): $Q_{M,r}$

OPCIÓN 1

$Q_{M,r}(n)$ = "¿ detiene en menos de pasos en todas las entradas de longitud ?" $M$ $n^r$ $n$

Trivialmente decidible (finito cadenas y siempre se detiene por hipótesis) no hay TM incomprensibles $2^n$ $M$ $\Rightarrow$

OPCION 2

$Q_{M,r}$ = "¿ es el tiempo de ejecución ?" $M$ $O(n^r)$

Trivialmente decidible (1 o 0) no hay TM incomprensibles $\Rightarrow$

Y si pregunta: "Ok, pero ¿podemos calcular el valor 1 o 0 para construir el algoritmo que responde a la pregunta de la Opción 2?", Entonces volvemos a esto:

$Q_{r}(M)$ = "¿ es el tiempo de ejecución ?" que es indecidible (usando la definición estándar de indecidible) como lo muestra Emanuele. Pero en esta versión, M es una entrada del problema y no la fija para la que está definiendo la noción de " incomprensible ". $M$ $O(n^r)$ $M$

Marzio De Biasi
fuente

Marzo, gracias por esta respuesta y por tu comentario anterior. El término ambiguo "decidible" ya se ha eliminado --- significaba cosas diferentes para diferentes comunidades --- a favor del lenguaje teórico de la prueba "ni demostrable ni refutable". A la cola de aclarar las enmiendas para la versión editada de mañana de la pregunta (que con suerte será la última presentación rigurosa de la pregunta) , se agregará la frase "Para todos los n ", según su Opción 1. Y finalmente, se extiende el agradecimiento y las gracias. a usted y a todos, por ayuda para plantear la pregunta de manera rigurosa y clara.

John Sidles

@JohnSidles: ok, y en tu nueva versión no olvides revisar la conexión entre ... es incomprensible si la declaración < runtime is > no es demostrable ni refutable en T ... " y la respuesta de Emanuele Viola, que trata sobre el "indecidible" (definición estándar de CS) * problema de decisión * <Is runtime ?>

M

$M$

M

$M$

O (n^{r})

$O(n^r)$

M

$M$

O (n^{r})

$O(n^r)$

Marzio De Biasi

Marzo, ok y gracias. Además, para establecer la "Implicación de Viola", tenemos que adjuntar el argumento de la Sección 3 de las notas del curso de Jeremy Avigad (como se vincula en la pregunta) a la construcción de Viola ... la pregunta enmendada aclarará este punto. Huelga decir que el proceso de aclarar definiciones ha sido 10X ++ más arduo de lo que originalmente anticipé ... lo que tal vez sea el punto principal de la pregunta. Gracias de nuevo.

John Sidles

La respuesta a su pregunta # 1 es definitivamente "no". Como creo que alguien señaló en la sección de comentarios (muy extensa), podría agregar fácilmente una "polilimitación" a una máquina. Es decir, incluso si no sabe qué es r, si adivina un número entero mayor que r (esto es definitivamente posible, obviamente), podría configurar una máquina aérea que simule su máquina de Turing "incomprensible" y forzarla para dejar de funcionar en tiempo polinómico ... sin cambiar el idioma que acepta la máquina de Turing. De esta manera, podría convertir cualquier máquina de Turing de tiempo polinomial "incomprensible" en una máquina de Turing de tiempo polinomial "comprensible", lo que significa que no hay lenguaje en P que pueda decidirse por máquinas de Turing exclusivamente "incomprensibles".

Espero que esto ayude. A menos que haya malinterpretado completamente su pregunta y su intención, mi respuesta es ciertamente correcta; No es en absoluto una pregunta abierta.

Philip White
fuente

Por cierto, si desea un buen ejemplo de un candidato para lo que llama un algoritmo "incomprensible", consulte scholarpedia.org/article/Universal_search . El algoritmo de búsqueda universal para resolver SAT se adhiere a su definición de incomprensible si P = NP es formalmente independiente.

Philip White

¿Sabes algo sobre la pregunta final de mi respuesta? Creo que esa es la única pregunta que todavía no es obviamente trivial ... para mí eso es

Sasho Nikolov

@Philip White, la definición está cuidadosamente construida para evadir la construcción que usted proporciona. Porque suponiendo que el tiempo de ejecución de M es indecidible para algún exponente r , y adivinamos un valor r ' > r , e instalamos un r' -polylimiter en una máquina modificada M 'que reconoce el mismo lenguaje que M, luego para M' la declaración "el tiempo de ejecución de M 'es O (n ^ r) con respecto a la longitud de entrada n" aún es indecidible. Sin embargo, estoy de acuerdo en que debemos pensar cuidadosamente si TODOS los juegos de gato y ratón con polilimitadores especificados en Oracle están excluidos (como es la intención) --- ¡y por eso voté su respuesta!

John Sidles

Ah, y dado que el comentario de Sasho se superpuso al mío, permítanme expresar mi aprecio por la última pregunta en la respuesta de Sasho , que (según mi comprensión actual) obstruye ingeniosamente la introducción de polilimitadores derivados de oráculos. Como antes, tendré que pensar en esto por un día o dos. Gracias de nuevo, Philip.

John Sidles

Lo siento, debería haber leído la respuesta de Sasho Nikolov con más cuidado; Acabo de ver la palabra "sí", oops. Veré la última pregunta en un momento y veré si tengo algo útil que decir.

Philip White