¿Por qué creemos en la tesis de Church-Turing?

Question

La tesis de Church-Turing, que dice que el modelo de la máquina de Turing es al menos tan potente como cualquier ordenador que pueda construirse en la práctica, parece ser aceptada de forma bastante incuestionable en mi exposición a la informática. ¿Por qué? ¿Tenemos más pruebas de su verdad que "nadie ha sido capaz de pensar en un modelo más potente que el de Turing todavía"? Si es así, ¿por qué aceptamos ese argumento como verdad? Me parece que en cualquier otra disciplina matemática, una afirmación como la tesis de Church-Turing cuyo apoyo equivale a "todavía no hemos encontrado un contraejemplo" no sería tomada en serio por la comunidad.

Answer 1

La tesis Church-Turing es creíble porque cada uno modelo de computación que nadie ha ideado hasta ahora ha demostrado ser equivalente a las máquinas de Turing (bueno, o estrictamente más débil, pero eso no interesa aquí). Esos modelos incluyen

1. Funciones recursivas sobre los números enteros
2. El cálculo lambda
3. Lógica combinatoria

y muchos más. De hecho, es difícil imaginar algo parecido a un algoritmo que no pueda ser formalizado en alguno de estos modelos.

La diferencia entre la tesis de Church-Turing y la realidad teoremas es que parece imposible formalizar la tesis Church-Turing. Cualquier formalización de este tipo tendría que formalizar qué función computable arbitraria es lo que requiere un modelo de computación para empezar. Se puede pensar en la tesis de Church-Turing como una especie de metateorema que afirma

Siempre que se elija alguna notación intuitiva de computable y formalizarlo, el modelo de computación resultante es equivalente a las máquinas de Turing, o estrictamente más débil.

Todo el hormigón instancias de este metateorema que han sido encontrado han sido probados. Nosotros hacer saber que todos los modelos de computación enumerados anteriormente son equivalentes. Puesto que no puede demostrar el metateorema, por la razón expuesta anteriormente, por lo que no podemos hacer nada mejor que decir "Bueno, no vemos cómo podría no ser verdad, así que asumiremos que es verdad".

Answer 2

Una nota al margen: creo que es un error identificar la Tesis de Church-Turing con una afirmación sobre lo que las máquinas pueden hacer en la práctica. Algunas reflexiones [si se me perdona la autocita].

(a) Es importante señalar que hay tres niveles de concepto que están en juego aquí cuando hablamos de computación.

1. En el nivel preteórico -y guiado por algunos paradigmas de la computación del mundo real- hay un grupo de ideas incipientes sobre lo que podemos calcular con papel y lápiz, sobre lo que puede calcular un ordenador (en el sentido moderno) y sobre lo que podría calcular un mecanismo en general.

2. Entonces, en lo que podríamos llamar el nivel prototeórico, tenemos, entre otras cosas, una forma ya conocida de seleccionar los hilos del grupo preteórico mientras se idealiza lejos de las limitaciones prácticas de tiempo o cantidad de papel, dándonos la noción de una función efectivamente computable. Por tanto, aquí ya se ha realizado un poco de ordenación teórica, aunque el concepto sigue estando caracterizado de forma algo vaga (¿qué hace que un paso en un procedimiento algorítmico paso a paso sea lo suficientemente "pequeño" como para ser admisible?)

3. Luego, en el nivel totalmente teórico, tenemos conceptos estrechamente caracterizados como el concepto de función recursiva y el concepto de función total computable por Turing.

Sería bastante inverosímil suponer que el incipiente cúmulo de ideas preteóricas del primer nivel fijen algo muy definido. No, la Tesis de Church-Turing entendida de forma sensata, de acuerdo con las intenciones de los primeros padres fundadores, es una opinión sobre las relaciones entre los conceptos del segundo y tercer nivel. La Tesis se pone en marcha después de que se haya realizado un trabajo prototeórico. La afirmación es que las funciones que caen bajo la idea prototeórica de una función efectivamente computable son justamente las que caen bajo el concepto de una función recursiva y bajo el concepto de una función computable por Turing. NB: la Tesis es una afirmación sobre la extensión del concepto de función efectivamente computable.

(b) Hay otros hilos en el batiburrillo preteórico de ideas sobre la computación que los recogidos en la idea de la computabilidad efectiva: en particular, está la idea de lo que una máquina puede computar y podemos hacer algo de ordenación prototeórica de ese hilo también. Pero la Tesis de Church-Turing no trata de esta idea. No debe confundirse con la afirmación totalmente diferente de que una máquina física sólo puede calcular funciones recursivas, es decir, la afirmación de que cualquier mecanismo de cálculo posible (interpretado en sentido amplio) no puede calcular más que una máquina de Turing. Porque tal vez podría haber una configuración física que, de una forma u otra, no se limitara a obtener un resultado después de un número finito de pasos deterministas y, por tanto, pudiera hacer más que cualquier máquina de Turing. O, al menos, si un "hiperordenador" de este tipo es imposible, eso no puede establecerse simplemente argumentando la tesis de Church-Turing.

Hagamos una pausa en este importante punto y explorémoslo un poco más. Es sabido que el Entscheidungsproblem no puede ser resuelto por una máquina de Turing. En otras palabras, no hay ninguna máquina de Turing a la que se le pueda dar (el código de) una wff arbitraria de primer orden, y que entonces decida, en un número finito de pasos, si es una wff válida o no. Sin embargo, aquí hay una especificación simple para una hipercomputadora no Turing que podría usarse para decidir la validez.

Imagina una máquina que toma como entrada el (número de Gödel para la) wff $\varphi$ que se va a comprobar su validez. A continuación, comienza a enumerar efectivamente (números para) los teoremas de una teoría formal axiomatizada adecuada de la lógica de primer orden. Vamos a Supongamos que nuestro ordenador enciende una luz cuando enumera un teorema que coincide con $\varphi$ . Ahora, nuestro ordenador imaginado se acelera mientras trabaja. Realiza una operación en el primer segundo, una segunda operación en el siguiente medio segundo, una tercera en el siguiente cuarto de segundo, una cuarta en el siguiente octavo de segundo, y así sucesivamente. Por lo tanto, al cabo de dos segundos ha realizado un número infinito de tareas, enumerando y comprobando cada teorema para ver si coincide con $\varphi$ ¡! Así que si la luz del ordenador parpadea en dos segundos, $\varphi$ es válido; si no, no. En resumen, podemos utilizar nuestra máquina de aceleración salvaje para decidir la validez, porque puede recorrer un número infinito de pasos en un tiempo finito.

Ahora bien, es muy razonable pensar que tales máquinas aceleradoras son una mera fantasía de filósofos, físicamente imposibles y que no deben tomarse en serio. Pero en realidad no es tan sencillo. Por ejemplo, podemos describir estructuras espacio-temporales consistentes con la Relatividad General que aparentemente tienen la siguiente característica. Podríamos enviar un ordenador "ordinario" en una trayectoria hacia una singularidad espacio-temporal. De acuerdo con su propio tiempo, es un ordenador no acelerado, que avanza uniformemente, calculando para siempre y sin llegar nunca a la singularidad. Pero según nosotros -¡qué alegría la de la relatividad! - tarda un tiempo finito antes de desaparecer en la singularidad, acelerando a medida que avanza. Supongamos que configuramos nuestro ordenador para que nos envíe una señal si, mientras enumera los teoremas lógicos de primer orden, llega a $\varphi$ . Entonces obtendremos la señal en un tiempo acotado por si acaso $\varphi$ es un teorema. Así que nuestro ordenador cayendo hacia la singularidad puede ser usado para decidir la validez. Ahora bien, hay complicaciones bastante fascinantes sobre si esta fantasiosa historia funciona realmente dentro de la Relatividad General. Pero no importa. Lo importante es que la cuestión de si podría existir este tipo de montaje físico de Turing -donde (desde nuestro punto de vista) se ejecuta un número infinito de pasos- no tiene nada que ver con la Tesis de Church-Turing propiamente dicha. Porque ésta es una afirmación sobre la computabilidad efectiva, sobre lo que se puede hacer en un número finito de pasos siguiendo un algoritmo.

Answer 3

La tesis de Church-Turing afirma que el informal La noción de una función que puede ser calculada por un algoritmo (efectivo) es precisamente la misma que la formal noción de función recursiva. Como la noción previa es informal, no se puede dar una prueba formal de esta equivalencia. Pero se pueden presentar argumentos informales que apoyen la tesis. Por ejemplo, todos los intentos conocidos de modelar formalmente esta noción informal de computabilidad han conducido precisamente a la misma clase de funciones recursivas, ya sea a través de lambda-calculus, los sistemas postales, los algoritmos de Markov, la lógica combinatoria, etc. Esta notable confluencia respalda firmemente la importancia de esta clase de funciones.

Cabe destacar que la máquina de Turing fue ideada por Turing no como como un modelo de cualquier tipo de ordenador físicamente realizable, sino como un límite ideal de lo que es computable por un humano calculando en un paso a paso mecánico de manera que no se recurra a la intuición. Este punto Este punto está muy mal entendido: véase Sieg [1] para una excelente exposición sobre éste y otros temas relacionados.

Las limitaciones de finitud postuladas por Turing para sus Máquinas de Turing se basan en las limitaciones postuladas del aparato sensorial humano. Un análisis al estilo de Turing de los dispositivos informáticos físicamente realizables y tesis análogas de Church-Turing no llegó hasta mucho después (1980) gracias a Robin Gandy, con limitaciones basadas en las leyes de la física. Como dice Odifreddi en la p. 51 de [2] (biblia de la Teoría de la Recursión Clásica)

Las máquinas de Turing son dispositivos teóricos, pero se han diseñado con con la vista puesta en las limitaciones físicas. En particular, hemos incorporado en nuestro modelo restricciones procedentes de: (a) el ATOMISMO, asegurando que la cantidad de información que se puede codificar en cualquier configuración de de la máquina (como sistema finito) está acotada; y (b) la RELATIVIDAD, al excluyendo las acciones a distancia, y haciendo que el efecto causal se propague a través de las interacciones locales. Gandy [1980] ha demostrado que la noción de máquina de Turing es lo suficientemente general como para subsumir, en un sentido preciso sentido, cualquier dispositivo de computación que satisfaga limitaciones similares.

y en la página 107: (Una teoría general de dispositivos discretos y deterministas)

El análisis (Church [1957], Kolmogorov y Uspenskii [1958], Gandy [1980]) parte de los supuestos del atomismo y la relatividad. El primero reduce la estructura de la materia a un conjunto finito conjunto de partículas básicas de dimensiones acotadas, y justifica así la posibilidad teórica de desmantelar una máquina hasta un conjunto de constituyentes básicos. La segunda impone un límite superior (la velocidad de la de la luz) a la velocidad de propagación de los cambios causales, y por tanto justifica la posibilidad teórica de reducir el efecto causal producido en un instante $t$ en una región acotada del espacio $V$ a las acciones producidas por las regiones cuyos puntos están dentro de la distancia $ct$ de algún punto $V$ . Por supuesto, los supuestos no tienen en cuenta sistemas que son continuos, o que permiten una acción ilimitada a distancia (como los sistemas gravitacionales newtonianos).

El análisis de Gandy muestra que el comportamiento es recurrente, para cualquier DISPOSITIVO CON UN LÍMITE FIJO EN LA COMPLEJIDAD DE SUS POSIBLES (en el sentido de que tanto los niveles de construcción conceptual a partir de los de los constituyentes, como el número de constituyentes en cualquier parte estructurada de cualquier configuración, están acotados), Y CONJUNTOS FIJOS CONJUNTOS FINITOS Y DETERMINISTAS DE INSTRUCCIONES PARA LA ACCIÓN LOCAL Y GLOBAL (las primeras dicen cómo determinar el efecto de una acción en las partes estructuradas sobre las partes estructuradas, el segundo cómo ensamblar los efectos locales efectos locales). Además, el análisis es óptimo en el sentido de que, cuando Cuando se precisa, cualquier relajación de las condiciones es compatible con cualquier comportamiento, por lo que proporciona una descripción suficiente y necesaria descripción del comportamiento recursivo.

Hay que tener en cuenta que el artículo de Gandy de 1980 [3] se considera difícil incluso por algunos conocedores. Puede que le resulte útil leer primero los artículos de [4] de J. Shepherdson y A. Makowsky.

[1] Sieg, Wilfried. Procedimientos mecánicos y experiencia matemática.
pp. 71--117 en Mathematics and mind. Papers from the Conference on the Philosophy of Mathematics celebrada en el Amherst College, Amherst, Massachusetts, 5-7 de abril de 1991. Editado por Alexander George. Logic Comput. Philos., Oxford Univ. Press, Nueva York, 1994. ISBN: 0-19-507929-9 MR 96m:00006 (Revisor: Stewart Shapiro) 00A30 (01A60 03A05 03D20)

[2] Odifreddi, Piergiorgio. Teoría de la recursión clásica.
Teoría de funciones y conjuntos de números naturales. Con un prólogo por G. E. Sacks. Studies in Logic and the Foundations of Mathematics, 125. North-Holland Publishing Co., Amsterdam-Nueva York, 1989. xviii+668 pp. ISBN: 0-444-87295-7 MR 90d:03072 (Revisor: Rodney G. Downey) 03Dxx (03-02 03E15 03E45 03F30 68Q05)

[3] Gandy, Robin. Tesis de Church y principios para los mecanismos.
El Simposio Kleene. Actas del Simposio celebrado en la Universidad de Wisconsin, Madison, Wisconsin, 18-24 de junio de 1978. Editado por Jon Barwise, H. Jerome Keisler y Kenneth Kunen. Studies in Logic and the Foundations of Mathematics, 101. North-Holland Publishing Co., Amsterdam-Nueva York, 1980. xx+425 pp. ISBN: 0-444-85345-6 MR 82h:03036 (Revisor: Douglas Cenzer) 03D10 (03A05)

[4] La máquina universal de Turing: un estudio de medio siglo. Segunda edición.
Editado por Rolf Herken. Computerkultur [Cultura informática], II. Springer-Verlag, Viena, 1995. xvi+611 pp. ISBN: 3-211-82637-8 MR 96j:03005 03-06 (01A60 03D10 03D15 68-06)

Answer 4

Tenemos algo más que ejemplos para justificar la tesis de Church-Turing. El documento original de Turing contiene un argumento detallado de que cualquier función que pueda ser calculada algorítmicamente por un ser humano puede ser calculada por una máquina de Turing. La cuestión de si este argumento es una "prueba formal" pasa por alto que el argumento de Turing es exactamente el tipo de argumento que se necesita para justificar la afirmación. De hecho, una motivación clave para seguir definiendo las máquinas de Turing en la computabilidad (en lugar de utilizar sólo modelos más convenientes de computación) es que las máquinas de Turing son el modelo que más se presta a una justificación de la tesis de Church-Turing, porque se inspiran directamente en el método de un ordenador humano algorítmico.

Answer 5

La idea es que se puede escribir un intérprete para cualquier Lenguaje de Programación utilizando Máquinas de Turing, es decir, existe una Máquina de Turing que interpretará cualquier programa escrito en cualquier Lenguaje de Programación y lo ejecutará.

Se cree porque todos los lenguajes de programación deben ser ejecutables por un ordenador y todo lo que hace un ordenador es comparar caracteres y establecer valores basados en qué es igual a qué y eso es lo que hacen las máquinas de Turing.