En la teoría de la computabilidad , la tesis de Church-Turing (también conocida como tesis de la computabilidad , [1] la tesis de Turing-Church , [2] la conjetura de Church-Turing , la tesis de Church , la conjetura de Church y la tesis de Turing ) es una tesis sobre la naturaleza de funciones computables . Establece que una función sobre los números naturales puede calcularse mediante un método eficaz si y solo si es computable mediante una máquina de Turing.. La tesis lleva el nombre del matemático estadounidense Alonzo Church y del matemático británico Alan Turing . Antes de la definición precisa de función computable, los matemáticos a menudo usaban el término informal efectivamente calculable para describir funciones que son computables por métodos de papel y lápiz. En la década de 1930, se realizaron varios intentos independientes para formalizar la noción de computabilidad :
Church, [7] Kleene, [8] y Turing [9] [11] demostraron que estas tres clases formalmente definidas de funciones computables coinciden: una función es λ-computable si y solo si es Turing computable, y si y solo si es recursivo general . Esto ha llevado a matemáticos e informáticos a creer que el concepto de computabilidad se caracteriza con precisión por estos tres procesos equivalentes. Otros intentos formales para caracterizar la computabilidad han fortalecido posteriormente esta creencia (ver más abajo ).
Por otro lado, la tesis de Church-Turing establece que las tres clases anteriores de funciones computables definidas formalmente coinciden con la noción informal de una función efectivamente calculable. Aunque la tesis tiene una aceptación casi universal, no puede probarse formalmente ya que el concepto de una calculabilidad efectiva solo se define informalmente.
Desde sus inicios, han surgido variaciones de la tesis original, incluidas afirmaciones sobre lo que una computadora puede realizar físicamente en nuestro universo ( tesis física de Church-Turing ) y lo que se puede calcular de manera eficiente ( tesis de Church-Turing (teoría de la complejidad) ). Estas variaciones no se deben a Church ni a Turing, sino que surgen de trabajos posteriores en teoría de la complejidad y física digital . La tesis también tiene implicaciones para la filosofía de la mente (ver más abajo ).
JB Rosser ( 1939 ) aborda la noción de "computabilidad efectiva" de la siguiente manera: "Claramente, la existencia de CC y RC (pruebas de Church y Rosser) presupone una definición precisa de 'efectivo'. 'Método efectivo' se usa aquí en el sentido bastante especial sentido de un método, cada paso del cual está predeterminado con precisión y que con certeza producirá la respuesta en un número finito de pasos". [12] Así, el adverbio-adjetivo "efectivo" se usa en el sentido de "1a: producir un efecto decidido, decisivo o deseado", y "capaz de producir un resultado". [13] [14]
A continuación, las palabras "efectivamente calculable" significará "producido por cualquier medio intuitivamente 'eficaz'" y "efectivamente computable" significará "producido por una máquina de Turing o un dispositivo mecánico equivalente". Las "definiciones" de Turing dadas en una nota a pie de página en su Ph.D. de 1938 La tesis Sistemas de Lógica Basada en Ordinales , supervisada por Church, son prácticamente los mismos: