Hay varias formulaciones equivalentes de la tesis de Turing-Church (que también se conoce como tesis de Turing, tesis de Church y tesis de Church-Turing). Una formulación de la tesis es que todo cálculo efectivo puede ser realizado por una máquina de Turing.
Métodos efectivos
La tesis de Turing-Church se refiere a la noción de un método efectivo o mecánico en lógica y matemáticas. ‘Efectivo’ y su sinónimo ‘mecánico’ son términos de arte en estas disciplinas: No tienen su significado cotidiano.
Un método, o procedimiento, M, para lograr algún resultado deseado se llama ‘efectivo’ o ‘mecánico’ por si acaso
- M se establece en términos de un número finito de instrucciones exactas (cada instrucción se expresa mediante un número finito de símbolos)
- M, si se lleva a cabo sin error, siempre producirá el resultado deseado en un número finito de pasos
- M puede (en la práctica o en principio) ser realizado por un ser humano sin la ayuda de ninguna maquinaria excepto papel y lápiz
- M no exige perspicacia ni ingenio por parte del ser humano para llevarlo a cabo.
Un ejemplo bien conocido de un método eficaz es la prueba de la tabla de verdad para la tautología.
En la práctica, esta prueba es impracticable para fórmulas que contienen un gran número de variables proposicionales, pero en principio se podría aplicar con éxito a cualquier fórmula del cálculo proposicional, con suficiente tiempo, tenacidad, papel y lápices.
Las afirmaciones de que existe un método eficaz para lograr tal o cual resultado se expresan comúnmente diciendo que existe un método eficaz para obtener los valores de tal o cual función matemática. Por ejemplo, que existe un método eficaz para determinar si una fórmula dada del cálculo proposicional es o no una tautología -por ejemplo, el método de la tabla de verdad- se expresa en jerga funcional diciendo que existe un método eficaz para obtener los valores de una función, llámese T, cuyo dominio es el conjunto de fórmulas del cálculo proposicional y cuyo valor para cualquier fórmula dada x, escrita T(x), es 1 ó 0 según sea o no x una tautología.
La tesis y su historia
La noción de un método eficaz es informal y los intentos de caracterizar la eficacia, como los anteriores, carecen de rigor, ya que el requisito clave de que el método no exige perspicacia ni ingenio queda sin explicar.
Uno de los logros de Turing en su artículo de 1936 fue presentar un predicado formalmente exacto con el que se puede reemplazar el predicado informal ‘puede calcularse por medio de un método efectivo’.
Church hizo lo mismo (1936a).
Los predicados de reemplazo que propusieron Turing y Church eran, a primera vista, muy diferentes entre sí, pero resultaron ser equivalentes, en el sentido de que cada uno selecciona el mismo conjunto de funciones matemáticas.
La tesis de Turing-Church es la afirmación de que este conjunto contiene todas las funciones cuyos valores pueden obtenerse mediante un método que satisfaga las condiciones de efectividad anteriores.
(Claramente, si hubiera funciones cuyo predicado informal fuera verdadero, pero no el predicado formal, entonces este último sería menos general que el primero y, por lo tanto, no podría emplearse razonablemente para reemplazarlo).
Cuando la tesis se expresa en en términos del concepto formal propuesto por Turing, es apropiado referirse a la tesis también como ‘tesis de Turing y mutatis mutandis en el caso de la Iglesia.
El concepto formal propuesto por Turing es el de computabilidad por máquina de Turing . Argumentó a favor de la afirmación (tesis de Turing) de que siempre que haya un método eficaz para obtener los valores de una función matemática, la función puede calcularse mediante una máquina de Turing.
La afirmación inversa se establece fácilmente, ya que un programa de máquina de Turing es en sí mismo una especificación de un método efectivo: un ser humano puede seguir las instrucciones del programa y llevar a cabo las operaciones requeridas sin el ejercicio de ningún ingenio o perspicacia.
Si la tesis de Turing es correcta, entonces hablar sobre la existencia o no de métodos efectivos puede ser reemplazado en matemáticas y lógica por hablar sobre la existencia o no de programas de máquinas de Turing.
Turing expuso su tesis en numerosos lugares, con diversos grados de rigor. La siguiente formulación es una de las más accesibles.
La tesis de Turing : ‘Las LCM [máquinas informáticas lógicas: la expresión de Turing para las máquinas de Turing] pueden hacer cualquier cosa que pueda describirse como “regla general” o “puramente mecánica”.
‘Esto está suficientemente bien establecido que ahora está de acuerdo entre los lógicos que “calculable por medio de un LCM” es la traducción correcta y precisa de tales frases.’ (Ibídem.)
Aquí hay otras dos formulaciones de la tesis de Turing:
Una: *Los “números computables” [los números cuyas representaciones decimales pueden ser generadas progresivamente por una máquina de Turing] incluyen todos los números que naturalmente se considerarían computables.*
Dos: *Mi opinión es que estas operaciones [las operaciones primitivas de una máquina de Turing] incluyen todas las que se utilizan en el cálculo de un número*
Para entender estas afirmaciones exactamente como las pretendía Turing, es necesario tener en cuenta que cuando usa las palabras ‘computadora’, ‘computable’ y ‘computation’ las emplea en relación con calculadoras humanas.
En 1936, las ‘computadoras’ eran empleados humanos que trabajaban de acuerdo con métodos efectivos.
Estas computadoras humanas hacían el tipo de cálculos que hoy en día realizan las máquinas de computación, y muchos miles de ellas se empleaban en establecimientos comerciales, gubernamentales y de investigación. Los números computables y las funciones computables son los números y funciones que pueden ser calculados por computadoras humanas (idealizadas hasta el punto de vivir para siempre y tener acceso a cantidades ilimitadas de papel y lápices).
Turing introdujo su tesis al argumentar que el Entscheidungsproblem o problema de decisión, para el cálculo de predicados, planteado por Hilbert (Hilbert y Ackermann 1928), no tiene solución.
Aquí está el relato de Church sobre el Entscheidungsproblem:
‘Por Entscheidungsproblem de un sistema de lógica simbólica se entiende aquí el problema de encontrar un método efectivo por el cual, dada cualquier expresión Q en la notación del sistema, se pueda determinar si Q es demostrable o no en el sistema.’
La prueba de la tabla de verdad es un método de este tipo para el cálculo proposicional. Turing demostró que, dada su tesis, no puede existir tal método para el cálculo de predicados. Demostró formalmente que no existe una máquina de Turing que pueda determinar, en un número finito de pasos, si una fórmula dada del cálculo de predicados es o no un teorema del cálculo.
Entonces, dada su tesis de que si existe un método efectivo, entonces puede ser llevado a cabo por una de sus máquinas, se deduce que no existe tal método.
Church había llegado al mismo resultado negativo unos meses antes, empleando el concepto de definibilidad lambda en lugar de la computabilidad de la máquina de Turing. Church y Turing descubrieron el resultado con bastante independencia el uno del otro. El método de Turing para obtenerlo es bastante más satisfactorio que el de Church, como el mismo Church reconoció en una revisión del trabajo de Turing:
la computabilidad por una máquina de Turing… tiene la ventaja de hacer evidente inmediatamente la identificación con la efectividad en el sentido ordinario (no definido explícitamente)’
El concepto de función definible por lambda se debe a Church y Kleene (Church 1932, 1936a, 1941, Kleene 1935) y el concepto de función recursiva a Godel y Herbrand (Godel 1934, Herbrand 1932).
La clase de funciones definibles por lambda y la clase de funciones recursivas son idénticas. Esto fue establecido en el caso de funciones de enteros positivos por Church y Kleene (Church 1936a, Kleene 1936).
Después de enterarse de la propuesta de Church, Turing rápidamente estableció que el aparato de definibilidad lambda y su propio aparato de computabilidad son equivalentes (1936: 263ff).
Así, en la propuesta de Church, las palabras ‘función recursiva de enteros positivos’ pueden ser reemplazadas por las palabras ‘función de enteros positivos computable por la máquina de Turing’.
Post se refirió a la identificación de Church de la calculabilidad efectiva con la recursividad como una “hipótesis de trabajo” y criticó a Church con bastante propiedad por enmascarar esta hipótesis como una definición.
Esta, entonces, es la ‘hipótesis de trabajo’ que, en efecto, Church propuso:
La tesis de Church : una función de números enteros positivos es efectivamente calculable solo si es recursiva.
La implicación inversa, que cada función recursiva de números enteros positivos es efectivamente calculable, se conoce comúnmente como lo contrario de la tesis de Church (aunque Church mismo no distinguió así, reuniendo ambas tesis en su ‘definición’).
Si la atención se restringe a funciones de enteros positivos entonces la tesis de Church y la tesis de Turing son equivalentes, en vista de los resultados antes mencionados de Church, Kleene y Turing.
El término ‘tesis de Church-Turing’ parece haber sido introducido por primera vez por Kleene, con una pequeña floritura de sesgo a favor de Church:
Así que las tesis de Turing y Church son equivalentes. Usualmente nos referiremos a ambos como la tesis de Church , o en conexión con una de sus… versiones que trata de las ‘máquinas de Turing’ como la tesis de Church-Turing.
La evidencia para la tesis
Se ha acumulado mucha evidencia para la ‘hipótesis de trabajo’ propuesta por Church y Turing en 1936. Tal vez la revisión más completa se encuentre en los capítulos 12 y 13 de Kleene (1952).
En resumen: (1) Toda función efectivamente calculable que se ha investigado a este respecto ha resultado ser computable por la máquina de Turing. (2) Todos los métodos u operaciones conocidos para obtener nuevas funciones efectivamente calculables a partir de funciones dadas efectivamente calculables son paralelos a los métodos para construir nuevas máquinas de Turing a partir de máquinas de Turing dadas. (3) Todos los intentos de dar un análisis exacto de la noción intuitiva de una función efectivamente calculable han resultado ser equivalentes en el sentido de que se ha demostrado que cada análisis ofrecido selecciona la misma clase de funciones, es decir, aquellas que son computables por Máquina de Turing.
Debido a la diversidad de los diversos análisis, (3) generalmente se considera una evidencia particularmente fuerte. Además de los análisis ya mencionados en términos de definibilidad lambda y recursividad, hay análisis en términos de máquinas de registro (Shepherdson y Sturgis 1963), sistemas canónicos y normales de Post (Post 1943, 1946), definibilidad combinatoria (Schonfinkel 1924, Curry 1929). , 1930, 1932), los algoritmos de Markov (Markov 1960) y la noción de reconocimiento de Godel (Godel 1936, Kleene 1952).
Si bien de vez en cuando ha habido intentos de cuestionar la tesis de Turing-Church (por ejemplo, por Kalmar (1959); Mendelson (1963) responde), el resumen de la situación que presentó Turing en 1948 no es menos cierto hoy: ‘ahora está de acuerdo entre los lógicos que ‘calculable por medio de un LCM’ es la interpretación correcta y precisa’ de la noción informal en cuestión.
Tesis M
Es importante distinguir entre la tesis de Turing-Church y la propuesta diferente de que cualquier cosa que pueda ser calculada por una máquina puede ser calculada por una máquina de Turing. (Las dos proposiciones a veces se confunden.) Gandy (1980) llama a la segunda proposición ‘Tesis M’.
Tesis M: Cualquier cosa que pueda ser calculada por una máquina es computable por máquina de Turing.
La propia tesis M admite dos interpretaciones, según si la frase ‘puede ser calculado por una máquina’ se toma en el sentido estricto de ‘puede ser calculado por una máquina que se ajusta a las leyes físicas (si no a las limitaciones de recursos) de el mundo real’ o en un sentido amplio que hace abstracción de la cuestión de si la máquina nocional en cuestión podría existir o no en el mundo real. La versión restringida de la tesis M es una proposición empírica cuyo valor de verdad se desconoce.
La versión amplia de la tesis M es simplemente falsa.
Se han descrito varias máquinas nocionales que pueden calcular funciones que no son computables por la máquina de Turing (por ejemplo, Abramson (1971), Copeland (1997), (1998c), da Costa y Doria (1991), (1994), Doyle ( 1982), Hogarth (1994), Pour-El y Richards (1979), (1981), Scarpellini (1963), Siegelmann y Sontag (1994), Stannett (1990), Stewart (1991); Copeland y Sylvan (1999) es una encuesta).
Nótese que la tesis de Turing-Church no implica la tesis M; la verdad de la tesis de Turing-Church es consistente con la falsedad de la tesis M (tanto en su forma amplia como estrecha).
Una tesis sobre métodos efectivos -es decir, sobre procedimientos de cierto tipo que puede realizar un ser humano sin la ayuda de una máquina- no tiene ninguna implicación sobre el alcance de los procedimientos que las máquinas son capaces de realizar (ya que, por ejemplo, puede haber, entre el repertorio de operaciones atómicas de una máquina, operaciones que ningún ser humano que esté trabajando con eficacia es capaz de realizar).
La evidencia mencionada anteriormente para la tesis de Turing-Church no es también evidencia para la Tesis M.