La tesis de Church-Turing se refiere al concepto de un método eficiente, sistemático o mecánico en lógica, matemáticas e informática. Está formulada como una descripción del concepto intuitivo de computabilidad y, en relación con las funciones recursivas generales, se la denomina con más frecuencia tesis de Church. También se refiere a la teoría de las funciones computables por computadora. La tesis apareció en la década de 1930, cuando aún no existían las computadoras. Más tarde recibió su nombre del matemático estadounidense Alonso Church y su colega británico Alan Turing.
Eficiencia del método para lograr el resultado
El primer dispositivo que se parecía a una computadora moderna fue el Bombie, una máquina creada por el matemático inglés Alan Turing. Se utilizó para descifrar mensajes alemanes durante la Segunda Guerra Mundial. Pero para su tesis y formalización del concepto de algoritmo utilizó máquinas abstractas, más tarde llamadas máquinas de Turing. Presentaciones de tesisinterés tanto para matemáticos como para programadores, ya que esta idea inspiró a los creadores de las primeras computadoras.
En la teoría de la computabilidad, la tesis de Church-Turing también se conoce como la conjetura sobre la naturaleza de las funciones computables. Establece que para cualquier función computable algorítmicamente sobre números naturales, existe una máquina de Turing capaz de calcularla. O, en otras palabras, hay un algoritmo adecuado para ello. Un ejemplo bien conocido de la efectividad de este método es la prueba de la tabla de verdad para probar la tautología.
Una forma de lograr cualquier resultado deseado se denomina "eficaz", "sistemática" o "mecánica" si:
- El método se especifica en términos de un número finito de instrucciones exactas, cada instrucción se expresa usando un número finito de caracteres.
- Se ejecutará sin errores, producirá el resultado deseado en un cierto número de pasos.
- El método puede ser realizado por un ser humano sin ayuda con cualquier equipo que no sea papel y lápiz
- No requiere comprensión, intuición o ingenio por parte de quien realiza la acción
Anteriormente en matemáticas, el término informal "efectivamente computable" se usaba para referirse a funciones que se pueden calcular con lápiz y papel. Pero la noción misma de computabilidad algorítmica era más intuitiva que cualquier cosa concreta. Ahora se caracterizó por una función con argumento natural, para la cual existe un algoritmo de cálculo. Uno de los logros de Alan Turing fuerepresentación de un predicado formalmente exacto, con cuya ayuda sería posible reemplazar el informal, si se utiliza la condición de eficiencia del método. Church hizo el mismo descubrimiento.
Conceptos básicos de funciones recursivas
El cambio de predicados de Turing, a primera vista, parecía diferente al propuesto por su colega. Pero como resultado resultaron ser equivalentes, en el sentido de que cada uno de ellos selecciona el mismo conjunto de funciones matemáticas. La tesis de Church-Turing es la afirmación de que este conjunto contiene todas las funciones cuyos valores se pueden obtener por un método que satisfaga las condiciones de eficiencia. Había otra diferencia entre los dos descubrimientos. Fue que Church consideró solo ejemplos de números enteros positivos, mientras que Turing describió su trabajo como cubriendo funciones computables con una integral o variable real.
Funciones recursivas comunes
La formulación original de Church establece que el cálculo se puede hacer usando el cálculo λ. Esto es equivalente a usar funciones recursivas genéricas. La tesis de Church-Turing cubre más tipos de computación de lo que se pensó originalmente. Por ejemplo, relacionados con autómatas celulares, combinadores, máquinas de registro y sistemas de sustitución. En 1933, los matemáticos Kurt Gödel y Jacques Herbrand crearon una definición formal de una clase llamada funciones recursivas generales. Utiliza funciones donde es posible más de un argumento.
Crear un métodoλ-cálculo
En 1936, Alonso Church creó un método de determinación llamado cálculo λ. Estaba asociado con los números naturales. Dentro del cálculo λ, el científico determinó su codificación. Como resultado, se les llama números de la Iglesia. Una función basada en números naturales se denominó λ-computable. Había otra definición. La función de la tesis de Church se llama λ-computable bajo dos condiciones. La primera sonaba así: si se calculaba sobre elementos Church, y la segunda condición era la posibilidad de ser representado por un miembro del cálculo-λ.
También en 1936, antes de estudiar el trabajo de su colega, Turing creó un modelo teórico para las máquinas abstractas que ahora llevan su nombre. Podían realizar cálculos manipulando los caracteres de la cinta. Esto también se aplica a otras actividades matemáticas que se encuentran en la informática teórica, como la computación probabilística cuántica. La función de la tesis de Church solo se comprobó más tarde utilizando una máquina de Turing. Inicialmente, se basaron en el cálculo λ.
Computabilidad de funciones
Cuando los números naturales se codifican apropiadamente como secuencias de caracteres, se dice que una función en números naturales es computable por Turing si la máquina abstracta encontró el algoritmo requerido e imprimió esta función en una cinta. Tal dispositivo, que no existía en la década de 1930, en el futuro sería considerado una computadora. La máquina abstracta de Turing y la tesis de Church anunciaron una era de desarrollodispositivos de cómputo Se comprobó que las clases de funciones formalmente definidas por ambos científicos coinciden. Por lo tanto, como resultado, ambas declaraciones se combinaron en una sola. Las funciones computacionales y la tesis de Church también tuvieron una fuerte influencia en el concepto de computabilidad. También se convirtieron en una herramienta importante para la lógica matemática y la teoría de la demostración.
Justificación y problemas del método
Hay puntos de vista contradictorios sobre la tesis. Se recogieron numerosas pruebas para la "hipótesis de trabajo" propuesta por Church y Turing en 1936. Pero todos los métodos u operaciones conocidos para descubrir nuevas funciones efectivamente computables a partir de las dadas estaban conectados con métodos de construcción de máquinas, que entonces no existían. Para probar la tesis de Church-Turing, se parte del hecho de que todo modelo realista de computación es equivalente.
Debido a la variedad de diferentes análisis, esto generalmente se considera una evidencia particularmente fuerte. Todos los intentos de definir con mayor precisión la noción intuitiva de una función efectivamente computable resultaron ser equivalentes. Todos los análisis que se han propuesto han demostrado distinguir la misma clase de funciones, es decir, aquellas que son computables por las máquinas de Turing. Pero algunos modelos computacionales resultaron ser más eficientes en términos de tiempo y uso de memoria para diferentes tareas. Posteriormente se observó que los conceptos básicos de las funciones recursivas y la tesis de Church son bastante hipotéticos.
Tesis M
Es importante distinguir entre la tesis de Turing y la afirmación de que todo lo que puede ser calculado por un dispositivo informático puede ser calculado por su máquina. La segunda opción tiene su propia definición. Gandhi llama a la segunda oración "Tesis M". Dice así: "Todo lo que puede ser calculado por un dispositivo puede ser calculado por una máquina de Turing". En el sentido estricto de la tesis, es una proposición empírica cuyo valor de verdad se desconoce. La Tesis de Turing y la "Tesis M" a veces se confunden. La segunda versión es en general incorrecta. Se han descrito varias máquinas condicionales que pueden calcular funciones que no son computables por Turing. Es importante notar que la primera tesis no implica la segunda, pero es consistente con su falsedad.
Implicación inversa de la tesis
En la teoría de la computabilidad, la tesis de Church se usa como una descripción de la noción de computabilidad por una clase de funciones recursivas generales. El estadounidense Stephen Kleene dio una formulación más general. Llamó parcialmente recursivas a todas las funciones parciales computables por algoritmos.
La implicación inversa se conoce comúnmente como la tesis inversa de Church. Se encuentra en el hecho de que toda función recursiva de enteros positivos se evalúa eficientemente. En un sentido estricto, una tesis simplemente denota tal posibilidad. Y en un sentido más amplio, se abstrae de la cuestión de si esta máquina condicional puede existir en él.
Ordenadores cuánticos
Los conceptos de funciones computables y la tesis de Church se convirtieron en un descubrimiento importante para las matemáticas, la teoría de máquinas y muchas otras ciencias. Pero la tecnología ha cambiado mucho y sigue mejorando. Se supone que las computadoras cuánticas pueden realizar muchas tareas comunes en menos tiempo que las modernas. Pero quedan preguntas, como el problema de la detención. Una computadora cuántica no puede responderla. Y, según la tesis de Church-Turing, ningún otro dispositivo informático tampoco.
