¿Qué significaría refutar la tesis de Church-Turing?

83

Perdón por el título pegadizo. Quiero entender, ¿qué se debe hacer para refutar la tesis de la Iglesia-Turing? ¡En algún lugar que leí es matemáticamente imposible hacerlo! ¿Por qué?

Turing, Rosser, etc., utilizaron diferentes términos para diferenciar entre: "lo que se puede calcular" y "lo que se puede calcular mediante una máquina de Turing".

La definición de Turing de 1939 con respecto a esto es: "Usaremos la expresión" función computable "para referirnos a una función calculable por una máquina, y dejamos que" efectivamente calculable "se refiera a la idea intuitiva sin identificación particular con ninguna de estas definiciones".

Entonces, la tesis de Church-Turing se puede enunciar de la siguiente manera: cada función efectivamente calculable es una función computable.

Entonces, de nuevo, ¿cómo se verá la prueba si uno refuta esta conjetura?

computability proofs hypercomputation András Salamon
fuente
1
Consulte el apéndice en este excelente (pero difícil de leer) artículo de L. Levin arxiv.org/PS_cache/cs/pdf/0203/0203029v16.pdf
user2471
ver también la aplicabilidad de la tesis de Church-Turing a modelos interactivos de computación
vzn

Respuestas:

5

La tesis de Church-Turing ha sido probada para todos los propósitos prácticos.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.146.5402

Dershowitz y Gurevich, Boletín de lógica simbólica, 2008.

(Esta referencia discute la historia del trabajo de Church y Turing, y argumenta a favor de una separación entre la "Tesis de Church" y la "Tesis de Turing" como afirmaciones lógicas distintas, luego las prueba a ambas, dentro de una axiomatización intuitiva de la computabilidad).

Aaron Sterling
fuente
24
Estoy un poco preocupado por esta respuesta. Puede dar una impresión equivocada a las personas que la tesis de la Iglesia-Turing ha sido probada, cuando en realidad no lo ha sido (y me imagino que la mayoría de la gente piensa que no se puede probar).
Emil
55
Este será mi último comentario aquí, pero creo que es posible que desee preguntar por qué un sitio como este es necesario si todo lo que tenemos que hacer es mirar los libros de texto. Arora y Barak son grandes investigadores, pero no son lógicos, ni investigadores de teoría de la complejidad (de todos modos escribieron un libro de complejidad, aunque esta no era su área principal de investigación), ni expertos en semántica de lenguaje de programación (que fue la motivación original para máquinas de estado abstracto). La sabiduría convencional no es necesariamente cierta y, al final del día, tenemos que pensar por nosotros mismos.
Aaron Sterling
8
Si Dershowitz y Gurevich probaron las tesis de Church y Turing, también demostraron que en el futuro no podremos construir una computadora que realice infinitos pasos computacionales en tiempo finito, ver por ejemplo arxiv.org/abs/gr-qc/ 0104023 que discute tales posibilidades.
Andrej Bauer
50
Como se entiende normalmente, la tesis de Church-Turing no es una propuesta formal que pueda probarse. Es una hipótesis científica, por lo que puede ser "refutada" en el sentido de que es falsable. Cualquier "prueba" debe proporcionar una definición de computabilidad, y la prueba es tan buena como esa definición. Estoy seguro de que Dershowitz-Gurevich tiene una buena prueba, pero el verdadero problema es si la definición realmente cubre todo lo computable. Respondiendo "¿se puede refutar?" decir "ha sido probado" es engañoso. Se ha demostrado bajo una definición razonable (¡falsable!) De computabilidad.
Ryan Williams
47
El artículo de Dershowitz-Gurevich no dice nada sobre computación probabilística o cuántica. Escribe un conjunto de axiomas sobre la computación y prueba la tesis de Church-Turing asumiendo esos axiomas. Sin embargo, nos queda justificar estos axiomas. Estos axiomas no cubren ni la computación probabilística ni la cuántica (admiten esto para la computación probabilística, y no mencionan la computación cuántica en absoluto), por lo que es bastante claro para mí que estos axiomas son realmente falsos en el mundo real, aunque la Iglesia-Turing La tesis es probablemente cierta.
Peter Shor el
60

Hay un punto sutil que rara vez veo mencionado en este tipo de discusiones y que creo que merece más atención.

Supongamos, como sugiere Andrej, que alguien construye un dispositivo que computa de manera confiable una función que ninguna máquina de Turing puede calcular. ¿Cómo sabríamos que la máquina en realidad está calculando ?fff

Obviamente, ningún número finito de valores de entrada / salida sería suficiente para demostrar que la máquina está calculando en lugar de alguna otra función computable de Turing que concuerde con en ese conjunto finito. Por lo tanto, nuestra creencia de que la máquina está computando debería basarse en nuestras teorías físicas de cómo está funcionando la máquina. Si observa algunas de las propuestas concretas para hipercomputadoras, encontrará que, efectivamente, lo que hacen es llevar una teoría física de vanguardia y extrapolar esa teoría al infinito.f ffff. Bien, bien, pero ahora supongamos que construimos el hipercomputador y le preguntamos si alguna vez se detendrá una máquina Turing que busca una contradicción en ZFC. Supongamos además que el hipercomputador responde "No". ¿Qué concluimos? ¿Llegamos a la conclusión de que el hipercomputador ha "calculado" la consistencia de ZFC? ¿Cómo podemos descartar la posibilidad de que ZFC sea realmente inconsistente y acabamos de realizar un experimento que ha falsificado nuestra teoría física?

Una característica crucial de la definición de Turing es que sus supuestos filosóficos son muy débiles. Asume, como debe ser, ciertas características simples de nuestra experiencia cotidiana, como la estabilidad básica del mundo físico y la capacidad de realizar operaciones finitas de manera confiable, repetible y verificable. Estas cosas todo el mundo acepta (¡fuera de un aula de filosofía, eso es!). La aceptación de un hipercomputador, sin embargo, parece requerir que aceptemos una extrapolación infinita.de una teoría física, y toda nuestra experiencia con la física nos ha enseñado a no ser dogmáticos sobre la validez de una teoría en un régimen que está mucho más allá de lo que podemos verificar experimentalmente. Por esta razón, me parece altamente improbable que se desarrolle algún tipo de consenso abrumador de que cualquier hipercomputador específico sea simplemente computación en lugar de hipercomputación , es decir, que haga algo que pueda llamarse "computación" solo si acepta alguna controversia filosófica o controvertida. supuestos físicos sobre extrapolaciones infinitas.

Otra forma de decirlo es que refutar la tesis de Church-Turing requeriría no solo construir el dispositivo que Andrej describe, sino también demostrar a satisfacción de todos que el dispositivo está funcionando como se anuncia. Si bien no es inconcebible, esta es una tarea difícil. Para las computadoras de hoy, la naturaleza finitaria de la computación significa que si no creo en el resultado de la "computación" de una computadora en particular, en principio puedo llevar a cabo una secuencia finita de pasos de una manera totalmente diferente para verificar el resultado. Este tipo de "respaldo" al sentido común y la verificación finita no está disponible si tenemos dudas sobre un hipercomputador.

Timothy Chow
fuente
1
Tim, claramente, la tesis de Church-Turing puede ser refutada por la demostración exitosa de un modelo de computación efectiva que trascienda el alcance común de los modelos equivalentes identificados por Church y Turing. Uno puede discutir lo inconcebible que podría ser, pero creo que eso es lo que se necesitaría. (Tenga en cuenta que evito "probar" y "refutar" en este contexto)
Orcmid
2
@Neel: Estás malentendido mi punto. Estoy diciendo que si la computadora física X realiza un cálculo que involucra n pasos, entonces, en principio, puedo verificar el cálculo realizando n pasos de una manera que no se base en teorías físicas sofisticadas. Es cierto que no puedo realizar pasos, pero tampoco lo puede hacer la computadora física X, así que eso es irrelevante para mi punto. 22250
Timothy Chow
66
@Neel: Por el contrario, mi punto es precisamente que es perfectamente razonable dudar de la sofisticada física subyacente a una computadora, ya sea una que exista hoy o una hipercomputadora del futuro. Una razón importante por la que toleramos las computadoras de hoy es que tienen la tarea de realizar cálculos finitos que, en principio, podemos imitar sin una física sofisticada. Pero construya un hipercomputador cuya exactitud dependa inherentemente de extrapolar teorías físicas infinitamente más allá de los regímenes accesibles experimentalmente, y no tenemos forma de saber si el cálculo es correcto o si nuestras teorías han salido mal.
Timothy Chow
66
@orcmid: la física debe ingresar la imagen en alguna parte; de lo contrario, ¿qué nos va a impedir declarar que todas las funciones son computables? Para merecer el nombre, un "cálculo" debe ser algo que podamos imaginar que realmente se lleve a cabo. Es por eso que las propuestas de hipercomputadoras se esfuerzan por explicar cómo podrían construirse físicamente. Mi punto es que deberíamos llevar el experimento mental un paso más allá: frente a una supuesta hipercomputadora, ¿cómo podríamos saber que realmente funciona como se anuncia? Si no pudiéramos saberlo, ¿sería realmente legítimo referirse a sus resultados como "cálculos"?
Timothy Chow
1
Esto es interesante, tal vez no podamos saber realmente que la máquina está computando f, porque solo estamos completando Turing. Tal vez se necesitaría un observador de hipercomputación para comprobar que un objeto de hipercomputación realmente está hipercomputando oO
guillefix
58

Si bien parece bastante difícil probar la tesis de la Iglesia-Turing debido a la naturaleza informal de la "función efectivamente calculable", podemos imaginar lo que significaría refutarla. Es decir, si alguien construye un dispositivo que (de manera confiable) calculó una función que no puede ser calculada por ninguna máquina de Turing, eso refutaría la tesis de Church-Turing porque establecería la existencia de una función efectivamente calculable que no es computable por una máquina de Turing.

Andrej Bauer
fuente
1
¿En qué sentido alguien debe "construir" la máquina? Vivimos en un mundo finito que solo puede contener computadoras que son estrictamente más débiles que las máquinas de Turing. ¿Quizás deba inventar una nueva caracterización lógica intuitivamente atractiva? ¿Cómo puede ser?
Vag
2
Y nuestro universo cada vez más restringido que Finito teórica Estado Mashines debido a la acotación de masa / energía por la constante de hormigón y Bremmermann límite pespmc1.vub.ac.be/ASC/Bremer_limit.html por lo que no existe cálculos que FSM grande imaginarios puede hacer, pero equipos físicos no puede (problemas de transcomputación).
Vag
2
Sería necesario, por supuesto, que un ser humano pueda simular la máquina, para refutar la tesis original de Turing que identifica la calculabilidad efectiva con la calculabilidad humana.
Carl Mummert
35

Desaprobar la tesis de la Iglesia-Turing parece realmente extremadamente improbable y conceptualmente muy difícil de imaginar. Hay varios "mundos físicos hipotéticos" que están en cierta tensión con la tesis de la Iglesia-Turing (pero si la contradicen es una pregunta filosófica interesante por sí misma). Un artículo de Pitowsky " La tesis de la iglesia física y la complejidad física computacional", Iyun 39, 81-99 (1990) trata sobre estos mundos físicos hipotéticos. Véase también el documento de Itamar Pitowsky y Oron Shagrir: " The Church-Turing Thesis and Hyper Computation ", Minds and Machines 13, 87-101 (2003). Oron Shagrir ha escrito varios artículos filosóficos sobre la tesis de Church-Turing en su página web . (Ver también esta publicación de blog ).

La tesis efectiva o eficiente de Church-Turing es una afirmación infinitamente más fuerte que la afirmación original de Church-Turing que afirma que cada computación posible puede ser simulada de manera eficiente por una máquina de Turing. Las computadoras cuánticas demostrarán que la tesis eficiente de Church-Turing es inválida (módulo de algunas conjeturas matemáticas de complejidad computacional y módulo de la "interpretación asintótica"). Creo que la conjetura eficiente de Church-Turing fue formulada por primera vez en 1985 por Wolfram, el artículo se cita en el documento de Pitowsky vinculado anteriormente. De hecho, ni siquiera necesita computadoras cuánticas universales para refutar la tesis de CT eficiente, y es una línea de investigación interesante (que Aaronson, entre otros estudios) propone proponer una demostración tan simple como sea posible de la superioridad computacional de los sistemas cuánticos.

También es un problema interesante si hay formas más simples de demostrar la superioridad computacional de las computadoras cuánticas en presencia de ruido, en lugar de tener una tolerancia a fallas cuánticas total (que permite el cálculo cuántico universal). (Scott A. también está interesado en este problema).

Gil Kalai
fuente
¿Pensé que las máquinas de Turing podían simular computadoras cuánticas? (Con gran pérdida de eficiencia, por supuesto.) (Editar: ah, me di cuenta de que dijiste la "Tesis de CT efectiva" - ¿es esta la tesis de que los TM pueden simular cualquier dispositivo de computación de manera eficiente?)
Emil
55
Creo que Gil está hablando de la tesis "extendida" de Church-Turing (que él llama la tesis "efectiva" de Church-Turing) de que todo lo que es eficientemente computable en la naturaleza también es computable en una máquina Polytime Turing.
Ryan Williams
2
Agregué una oración para aclararlo.
Gil Kalai
Gil, gracias por esta excelente publicación. Para expresar un punto de vista de ingeniería de sistemas cuánticos, los humanos existimos en un universo ruidoso en el que (en ausencia de corrección de errores) el ECT es empíricamente cierto, en el sentido de que los procesos dinámicos cuánticos pueden simularse eficientemente a través de formalismos en los que (efectivamente) la superposición cuántica es una aproximación local, en el mismo sentido que la geometría euclidiana es una aproximación local a la geometría riemanniana. ¿La naturaleza adopta flujos cuánticos similares, para computarse de manera eficiente? Esa es una pregunta abierta ... y muy interesante en mi humilde opinión.
John Sidles 01 de
Inspirado por la publicación de Gil y por la publicación de Timothy Chow (abajo), he promovido el comentario anterior a una pregunta formal de TCS: "¿Cuál es el papel apropiado de la validación en el muestreo cuántico, la simulación y las pruebas de Turing de Iglesia Extendida (ECT)? " Gracias Gil y Timothy.
John Sidles
24

Según tengo entendido, la "imposibilidad" de probar o refutar la tesis es que no existe una definición formal de "efectivamente calculable". Hoy, consideramos que es precisamente "computable por una máquina de Turing", pero eso plantea la pregunta.

Se han estudiado modelos de cómputo que son estrictamente más potentes que una máquina de Turing. Consulte http://en.wikipedia.org/wiki/Hypercomputation para ver algunos ejemplos. O simplemente tome una máquina Turing con un oráculo para el problema de detención de las máquinas Turing. Tal máquina tendrá su propio problema de detención, pero puede resolver el problema de detención original perfectamente. Por supuesto, no tenemos tal oráculo, pero no hay nada matemáticamente imposible sobre la idea.

Evgenij Thorstensen
fuente
Gracias por la respuesta. Entonces, ¿crear una función que sea matemáticamente realizable (pero no físicamente) por algún modelo pero no por una máquina de Turing no refuta la tesis?
1
Dershowitz y Gurevich 2008 axiomatizan "efectivamente calculable" mediante el uso de máquinas de estado abstractas.
Aaron Sterling el
44
Entonces, están definiendo otro modelo de cómputo y demostrando que es equivalente a los existentes, ¿no es así? ¿Por qué ese modelo computacional es más confiable que los existentes?
Blaisorblade
Podríamos usar el poder humano como un oráculo, ideando una prueba formal para la (no) terminación. Mal tiempo de ejecución, sin embargo ...
Raphael
10

Las pruebas de hipercomputación generalmente asumen la validez del límite de Bekenstein, que establece un límite particular en la cantidad de información que puede contener una cantidad finita de espacio. Existe controversia sobre este límite, pero creo que la mayoría de los físicos lo aceptan.

Si el límite de Bekenstein se viola gravemente, y no hay límite en la cantidad de información contenida en una región en particular (por ejemplo, un agujero negro o un grabado infinitamente fino y robusto), y existen mecanismos arbitrariamente refinables para examinar el contenido de ese región (digamos, al examinar cuidadosamente la radiación emitida cuando un objeto cuidadosamente construido cae en el agujero negro, o al pasar un lápiz sobre los surcos del grabado), se puede suponer que ya existe un artefacto que codifica un oráculo que se detiene. .

Todo es muy poco probable, pero muestra que la afirmación de que la hipercomputación es imposible no es una verdad matemática, sino que se basa en la física. Es decir que Andrej tiene razón cuando dice que podemos imaginar lo que significaría refutar [la tesis de Church-Turing]. Es decir, si alguien construyó un dispositivo que (de manera confiable) calculó una función que ninguna máquina de Turing no puede calcular .

Charles Stewart
fuente
El límite de Bekenstein puede mantenerse pero la hipercomputación aún podría ser posible.
András Salamon
@ András: En principio sí: necesitamos mucha más teoría física para que un argumento negativo funcione. Pero los intentos de "describir" la maquinaria de hipercomputación que he visto todos la violan.
Charles Stewart el
¿Los que involucran bucles cerrados cerca de agujeros negros violan el límite?
András Salamon
@ András: No sé a qué te refieres. La teoría de cuerdas es generalmente compatible con el límite de Bekenstein.
Charles Stewart
Me refiero a cosas como arxiv.org/abs/gr-qc/0209061 que en lugar de depender de la teoría de cuerdas, "solo" supone que uno puede enviar cálculos al pasado.
András Salamon
9

Con respecto a la Tesis Extendida de Turing de la Iglesia (que significa "Una máquina de Turing probabilística puede simular eficientemente cualquier función físicamente computable"):

Una posibilidad es la diferencia entre las computadoras clásicas y cuánticas. Específicamente la pregunta, "¿Hay una tarea que las computadoras cuánticas pueden realizar que las computadoras clásicas no pueden hacer?" Un informe reciente de ECCC de Scott Aaronson (ver Conjetura 9 en la página 5) destaca una conjetura que, si se prueba, proporcionaría evidencia sólida contra la Tesis Extendida de Turing de la Iglesia.

Si uno refutara la Tesis Extendida de Turing de la Iglesia, podría verse así, específicamente, al demostrar una tarea eficientemente computable que una máquina de Turing (clásica) no puede calcular eficientemente.

Daniel Apon
fuente
2
Para aclarar, la computación cuántica solo pone en tela de juicio la Tesis de Turing de la Iglesia Eficiente / Extendida / Fuerte que establece que todos los modelos de computación realizables pueden simularse en una máquina de Turing en tiempo polinomial. La tesis normal de Church-Turing no impone restricciones a la eficiencia. Las computadoras cuánticas no tienen la esperanza de derrocar esta versión porque una máquina Turing puede simplemente simular todas las ramas exponencialmente de una computación cuántica en tiempo finito.
Ian
Sí, gracias por esto. He corregido mi uso descuidado de los dos términos.
Daniel Apon
Hmmm ... pero de acuerdo con las definiciones estándar, no ha TCE ya se ha refutado de manera concluyente? Alice: "Aquí hay una muestra de dígitos binarios verdaderamente aleatorios calculados por mi red óptica cuántica (un modo)". Bob: "Aquí hay una muestra de dígitos pseudoaleatorios calculados por una máquina clásica de Turing". Alice: "Lo siento Bob ... tu muestra es algorítmicamente compresible, y la mía no lo es. ¡Por lo tanto, mis datos demuestran que la TEC es falsa!" Hablando formalmente, el razonamiento de Alice es impecable. Sin embargo, en ausencia de pruebas de validación de las afirmaciones de Alice, ¿deberíamos estar satisfechos?
John Sidles 01 de
4

Los siguientes documentos de Selim Akl pueden ser de interés y relevantes para la discusión:

Akl, SG, "Tres contraejemplos para disipar el mito de la computadora universal", Parallel Processing Letters, vol. 16, núm. 3, septiembre de 2006, págs. 381 - 403.

Akl, SG, "Incluso las máquinas de aceleración no son universales", International Journal of Unconventional Computing, vol. 3, núm. 2, 2007, págs. 105 - 121.

Nagy, M. y Akl, SG, "El paralelismo en el procesamiento de información cuántica derrota a la computadora universal", Cartas de procesamiento paralelo, número especial sobre problemas computacionales no convencionales, vol. 17, núm. 3, septiembre de 2007, págs. 233 - 262.

Aquí está el resumen del primero:

Se muestra que el concepto de computadora universal no puede realizarse. Específicamente, se exhiben instancias de una función computable F que no se puede calcular en ninguna máquina U que sea capaz de realizar solo un número finito y fijo de operaciones por paso. Esto sigue siendo cierto incluso si la máquina U está dotada de una memoria infinita y la capacidad de comunicarse con el mundo exterior mientras intenta calcular F. También es cierto si, además, U tiene una cantidad de tiempo indefinida para calcular F. Este resultado se aplica no solo a los modelos de computación idealizados, como la Máquina de Turing y similares, sino también a todas las computadoras de uso general conocidas, incluidas las computadoras convencionales existentes (tanto secuenciales como paralelas), así como a las no convencionales contempladas como como computadoras biológicas y cuánticas.

Massimo Cafaro
fuente
¿Puede proporcionar un enlace al primer documento que no está detrás de un muro de pago? ¿Cuál es su definición de "función computable"? Según la definición estándar (hay una máquina de Turing que calcula la función) su reclamo es, por definición, falso ...
Christopher Monsanto
Te acabo de enviar el papel por correo electrónico.
Massimo Cafaro
Aquí está uno de estos documentos: research.cs.queensu.ca/home/akl/techreports/even.pdf . Más aquí: research.cs.queensu.ca/Parallel/projects.html . No hay una definición real de una "computadora" en el documento, solo una descripción ondulada a mano. Presumiblemente, esa descripción ondulada a mano puede formalizarse con un poco de trabajo, utilizando el modelo de máquina Turing o algo similar como base.
Sasho Nikolov
Matemáticamente, el teorema principal es una trivialidad: usted define la tarea computacional para requerir que las operaciones se realicen por el tiempo . Luego, debido a que el número de operaciones realizadas por la computadora por paso de tiempo se define como máximo como una constante , defina . Por lo tanto, la mano es definir un "problema" inusual. Luego hay un montón de filosofar por qué eso es supuestamente interesante. Creo que no lo es. Pero las personas son libres de desperdiciar sus vidas como quieran. Solo espero que esta persona no esté supervisando a los estudiantes para que trabajen en esto. t c W ( t ) > c tW(t)tcW(t)>ct
Sasho Nikolov
-6

¿Cómo puede ser verdad? Una computadora clásica no puede simular eficientemente una computadora cuántica. Existen algoritmos cuánticos que proporcionan una velocidad exponencial sobre las computadoras clásicas que ejecutan algoritmos clásicos: el algoritmo de Shor es uno.

Robert McGwier
fuente
3
1) Puede haber un algoritmo clásico de factorización polytime. No conocemos uno, pero su existencia es totalmente consistente con el estado de la teoría de la complejidad. 2) La tesis original de Church-Turing es sobre computabilidad, no sobre computabilidad eficiente .
Sasho Nikolov