Tesis extendida de Turing de la Iglesia

35

Una de las preguntas más discutidas en el sitio ha sido Qué significaría refutar la Tesis de Turing de la Iglesia . Esto se debe en parte a que Dershowitz y Gurevich publicaron una prueba de que la Tesis de Church-Turing es el Boletín de la lógica simbólica en 2008. (No voy a discutir eso aquí, pero para un enlace y comentarios extensos, vea la pregunta original, o - - autopromoción descarada - una entrada de blog que escribí)

Esta pregunta es sobre la Tesis Extendida de Turing de la Iglesia, que, según lo formulado por Ian Parberry, es:

El tiempo en todos los modelos de máquinas "razonables" está relacionado por un polinomio.

Gracias a Giorgio Marinelli, me enteré de que uno de los coautores del artículo anterior, Dershowitz, y un estudiante de doctorado suyo, Falkovich, han publicado una prueba de la Tesis Extendida de Turing de la Iglesia, que acaba de aparecer en el taller Desarrollos de Modelos computacionales 2011 .

Esta mañana acabo de imprimir el periódico y lo he leído, nada más. Los autores afirman que las máquinas de Turing pueden simular cualquier dispositivo computacional secuencial con una sobrecarga polinómica como máximo. La computación cuántica y la computación paralela a gran escala no están explícitamente cubiertas. Mi pregunta se refiere a la siguiente declaración en el documento.

Hemos demostrado, como se ha conjeturado y se cree ampliamente, que cada implementación efectiva, independientemente de las estructuras de datos que use, puede ser simulada por una máquina de Turing, con una sobrecarga polinómica en la complejidad del tiempo.

Entonces, mi pregunta: ¿es esto realmente "ampliamente creído", incluso en el caso de computación secuencial "verdaderamente" sin aleatorización? ¿Qué pasa si las cosas son aleatorias? La computación cuántica sería un contraejemplo probable, si de hecho se puede instanciar, pero ¿hay posibilidades "más débiles" que la cuántica que también serían contraejemplos?

Aaron Sterling
fuente
1
Ha habido una gran discusión sobre la desradiación o la eliminación de los componentes aleatorios de los algoritmos aleatorios. Por ejemplo, ver ( bit.ly/rjx5YZ ). Una vez le hice la pregunta a Lance Fortnow en la teoría del medio oeste sobre la descuantificación y eso no tenía sentido. Pero sí generó una buena discusión aquí ver ( bit.ly/nT0BnK ) Pero hay caminos más fructíferos. Leslie Valiant Turing, ganadora del premio 2011 ( bit.ly/nSyffN ), ofrece un ejemplo de una posibilidad más débil que tiene algo que ver con los algoritmos cuánticos .
Joshua Herman
1
@Joshua, el ACM acaba de publicar la Conferencia Turing 2011 de Valiant (URL: awards.acm.org/… ); Vale la pena verlo. Para una perspectiva aplicada, vea los artículos recientes de JMR de Ilya Kuprov y colaboradores: Algoritmo de simulación de dinámica de espín de escala polinómica basado en la restricción adaptativa de espacio de estado y dinámica de espín de escala polinómica II: Compresión adicional de espacio de estado usando técnicas de subespacio de Krylov y eliminación de pista cero . Esta convergencia lenta de CT / QIT "puro" y "aplicado" es prácticamente importante y también muy divertida.
John Sidles

Respuestas:

44

Rant preparatoria

Tengo que decirte que no veo cómo hablar de "pruebas" de la TC o la TEC añade alguna luz a esta discusión. Tales "pruebas" tienden a ser exactamente tan buenas como las suposiciones sobre las que descansan, en otras palabras, como lo que significan palabras como "cálculo" o "cálculo eficiente". Entonces, ¿por qué no proceder de inmediato a una discusión de los supuestos y prescindir de la palabra "prueba"?

Eso ya estaba claro con el CT original, pero es aún más claro con la TEC --- ya que no solo es "filosóficamente demostrable", ¡sino que hoy en día se cree que es falso! Para mí, la computación cuántica es el contraejemplo enorme y deslumbrante que debería ser el punto de partida para cualquier discusión moderna sobre la TEC, y no algo desviado. Sin embargo, el artículo de Dershowitz y Falkovich ni siquiera toca el control de calidad hasta el último párrafo:

    El resultado anterior no cubre el cómputo paralelo a gran escala, como el cómputo cuántico, ya que postula que hay un límite fijo en el grado de paralelismo, con el número de términos críticos fijados por el algoritmo. La cuestión de la complejidad relativamente [sic] de los modelos paralelos se abordará en el futuro cercano.

Encontré lo anterior altamente engañoso: QC no es un "modelo paralelo" en ningún sentido convencional. En la mecánica cuántica, no hay comunicación directa entre los "procesos paralelos", solo interferencia de amplitudes, pero también es fácil generar un número exponencial de "procesos paralelos". (¡De hecho, uno podría pensar que cada sistema físico del universo lo hace mientras hablamos!) En cualquier caso, sea lo que sea que piense acerca de la interpretación de la mecánica cuántica (o incluso su verdad o falsedad), está claro que requiere un ¡discusión!

Ahora, ¡a tus preguntas (interesantes)!

No, no conozco ningún contraejemplo convincente para la TEC que no sea la computación cuántica. En otras palabras, si la mecánica cuántica hubiera sido falsa (de una manera que todavía mantuviera el universo más "digital" que "analógico" en la escala de Planck --- ver más abajo), entonces la TEC como lo entiendo todavía no sería "demostrable" (ya que aún dependería de hechos empíricos sobre lo que es eficientemente computable en el mundo físico), pero sería una buena hipótesis de trabajo.

La aleatorización probablemente no desafíe la TEC como se entiende convencionalmente, debido a la fuerte evidencia de que P = BPP. (Sin embargo, tenga en cuenta que, si está interesado en configuraciones que no sean problemas de decisión del idioma, por ejemplo, problemas relacionales, árboles de decisión o complejidad de la comunicación, entonces la aleatorización puede marcar una gran diferencia. Y esas configuraciones son perfectamente razonables de las que hablar; simplemente no son las personas que normalmente tienen en mente cuando discuten la TEC).

La otra clase de "contraejemplos" para la TEC que a menudo se menciona implica la computación analógica o "hiper". Mi opinión es que, según nuestra mejor comprensión actual de la física, la computación analógica y la hipercomputación no pueden escalar, y la razón por la que no pueden, irónicamente, ¡es la mecánica cuántica! En particular, aunque todavía no tenemos una teoría cuántica de la gravedad, lo que se sabe hoy sugiere que existen obstáculos fundamentales para ejecutar más de aproximadamente 10 43 pasos de cálculo por segundo o resolver distancias menores de aproximadamente 10 -33 cm.

Finalmente, si quiere asumir fuera de discusión cualquier cosa que pueda ser un desafío plausible o interesante para el TCE, y que solo permita el cálculo en serie, discreto y determinista, ¡ entonces estoy de acuerdo con Dershowitz y Falkovich que sostiene el TCE! :-) Pero incluso allí, es difícil imaginar una "prueba formal" que aumente mi confianza en esa declaración: el problema real, de nuevo, es justo lo que tomamos palabras como "serial", "discreto" y "determinista" para significar .

En cuanto a tu última pregunta:

    La computación cuántica sería un contraejemplo probable, si de hecho se puede instanciar, pero ¿hay posibilidades "más débiles" que la cuántica que también serían contraejemplos?

Hoy en día, hay muchos ejemplos interesantes de sistemas físicos que parecen capaces de implementar algunos de la computación cuántica, pero no todos (dando clases de complejidad que podrían ser intermedias entre BPP y BQP). Además, muchos de estos sistemas pueden ser más fáciles de realizar que un control de calidad universal completo. Véase, por ejemplo, este artículo de Bremner, Jozsa y Shepherd, o este de Arkhipov y yo.

Scott Aaronson
fuente
3
Acerca de "prueba": veo que el programa de investigación Dershowitz et al intenta crear un "ZF para algoritmos", para axiomatizar la noción intuitiva de "algoritmo". Entonces podemos discutir si se incluye la Elección o la Determinación, o la existencia de un gran cardenal, cualesquiera que sean los análogos de esas cosas en la informática. Creo que la forma en que se presenta esta axiomatización depende de los resultados ("mira, podemos probar esta famosa tesis"), pero los autores del artículo de tesis CT intentan proporcionar una justificación histórica de sus suposiciones.
Aaron Sterling
1
@Scott Aaronson Vista interesante e iluminadora sobre el control de calidad. Sólo curioso. ¿Qué se necesitaría para mostrar que el control de calidad no puede ser un contraejemplo?
vs
10
¿Quieres decir que mostrar QC es imposible? Por lo menos, tomaría una revisión seria en nuestra comprensión de la mecánica cuántica. Eso podría significar el descubrimiento de una nueva teoría física que reemplazó a la QM (y por lo tanto restableció la BPP como el límite de la computación), o algún principio aún no descubierto que funciona "encima" o "junto" a la QM que no permitía el control de calidad. De cualquier manera, ¡premios Nobel! :)
Scott Aaronson
Me gusta tu comentario Necesitará cavar más en QC. Soy muy ingenuo en ese tema.
vs
1
Otro modelo cuántico interesante entre la computación cuántica completa y la clásica son los modelos basados ​​en la discordia cuántica, como DQC1.
Marcos Villagra
5

Esta respuesta está destinada a complementar la respuesta de Scott Aaronson (con la que estoy de acuerdo principalmente).

Desde una perspectiva de ingeniería, es sorprendente que el artículo de Dershowitz / Falkovich use la palabra "aleatorio" solo en el sentido de "memoria de acceso aleatorio", y además, el artículo no usa la palabra "muestra" (o ninguno de sus variantes) en absoluto. Más bien, el enfoque del análisis de Dershowitz / Falkovic se limita exclusivamente al cálculo de funciones numéricas.

Esta limitación es sorprendente porque la gran mayoría de los recursos computacionales STEM modernos (me atreveré a decir) no respetan la restricción a las funciones numéricas, sino que se dedican a generar muestras a partir de distribuciones (por ejemplo, dinámica molecular, flujo de fluido turbulento, propagación de fracturas). , sistemas de espín ruidosos tanto clásicos como cuánticos, ondas que se propagan a través de medios aleatorios, etc.

Por lo tanto, si la "Tesis extendida de Turing de la Iglesia" (ECT) va a tener una relevancia sustancial para los cálculos STEM definidos de manera amplia, tal vez se deba levantar la restricción exclusiva a las funciones numéricas, y se debe dar una declaración generalizada de la ECT, que abarca el muestreo cálculos (y su validación y verificación).

¿Esta versión del TCE generalizada al muestreo aún estaría dentro del alcance de TCS como se concibe tradicionalmente? La respuesta aparentemente es "sí", según las preguntas frecuentes de TCS Stack Exchange :

Le remitimos a la descripción del Grupo de Interés Especial de ACM sobre Algoritmos y Teoría de la Computación (SIGACT) ... TCS cubre una amplia variedad de temas, incluida la computación probabilística ... El trabajo en este campo [TCS] a menudo se distingue por su énfasis en matemática técnica y rigor.
Estas consideraciones sugieren que, para que sean relevantes para los cálculos prácticos de STEM, los análisis de la TEC deberían incluir consideraciones explícitas de validación y verificación de muestras ... y podemos anticipar razonablemente que esta extensión de la TEC estaría asociada tanto a hermosos teoremas matemáticos como a para estimular las percepciones físicas.

John Sidles
fuente
0

ECTT{0,1,+,×}ECTT, que dice que este predicado de razonabilidad se satisface exactamente con aquellos modelos que tienen una traducción de tiempo polinómica a una máquina de Turing. Como axioma, no es falsable en el sentido de que nuestra teoría sea capaz de contradecirlo, siempre que la teoría sea coherente, pero la solidez de nuestra teoría es falsable: posiblemente existe un modelo razonable de cálculo que no está relacionado con Máquinas de Turing por una traducción de tiempo polinómica. Permitir que este descubrimiento hipotético pueda implicar un cambio en el pensamiento sobre lo que es razonable, así es como veo el lado formal. Parece trivial en retrospectiva, pero creo que es un punto importante delinear las matemáticas de todo lo demás.

ECTTBPPPECTTPBPPBPPECTTPECTTPBQPECTTECTTBPPBQPP

Por ejemplo, supongamos que afirmo haber construido una máquina que factoriza números y que su tiempo de ejecución satisface un límite polinómico particular. La máquina está en una caja, introduce el número escrito en una cinta de papel e imprime los factores. No hay duda de que funciona, ya que lo he usado para ganar los desafíos de RSA, confiscar criptomonedas, factorizar grandes cantidades de su elección, etc. ¿Qué hay en la caja? ¿Es un nuevo tipo de computadora sorprendente, o es una computadora ordinaria que ejecuta algún tipo de software nuevo y sorprendente?

ECTTECTT

ECTTEXPTIMEPCTC=PSPACEECTTPPSPACE

PNPECTTPPCTCP=NPECTTECTTNP3SATP

EXPTIMEECTTEXPTIMEPECTT

ECTTP=BPPECTTPBQP

ECTT{}ECTT{}

ECTT

Dan Brumleve
fuente
1020