Hispanopedia Wiki
Articulo de referencia

Tesis de Church-Turing

En la teoría de la computabilidad , la tesis de Church-Turing {{Cite journal |last=Soare |first=Robert I. |date=2009-09-01 |title=Turing oracle machines, online computing, and t...

Hispanopedia WikiContenido en espanolLectura gratuita

En la teoría de la computabilidad , la tesis de Church-Turing [ a ] es una tesis sobre la naturaleza de las funciones computables . Afirma que una función sobre los números naturales puede calcularse mediante un método efectivo si y solo si es computable por 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 solían usar el término informal «efectivamente calculable» para describir las funciones que se pueden calcular mediante métodos de lápiz y papel. En la década de 1930, se hicieron varios intentos independientes para formalizar la noción de computabilidad :

  • En 1933, Kurt Gödel , junto con Jacques Herbrand , formalizó la definición de la clase de funciones recursivas generales : la clase más pequeña de funciones (con un número arbitrario de argumentos) que es cerrada bajo composición , recursión y minimización , e incluye cero , sucesor y todas las proyecciones .
  • En 1932–33, [ 3 ] Alonzo Church creó un método para definir funciones llamado cálculo λ . Dentro del cálculo λ, definió una codificación de los números naturales llamada numerales de Church . Una función sobre los números naturales se denomina λ-computable si la función correspondiente sobre los numerales de Church puede representarse mediante un término del cálculo λ.
  • En 1935–36, [ 7 ] Alonzo Church formalizó el concepto de funciones efectivamente calculables al proponer que son funciones recursivas generales o, equivalentemente, funciones λ-definibles.
  • En 1936, antes de conocer el trabajo de Church, [ 12 ] Alan Turing creó un modelo teórico para máquinas, ahora llamadas máquinas de Turing, que podían realizar cálculos a partir de entradas manipulando símbolos en una cinta. Dada una codificación adecuada de los números naturales como secuencias de símbolos, una función sobre los números naturales se denomina computable por Turing si alguna máquina de Turing calcula la función correspondiente sobre los números naturales codificados. Turing propuso que las funciones efectivamente calculables se definieran como aquellas que son computables por Turing.

Church, [ 13 ] Kleene , [ 14 ] y Turing [ 15 ] [ 17 ] demostraron que estas tres clases de funciones computables definidas formalmente coinciden: una función es λ-computable si y solo si es Turing computable, y si y solo si es recursiva general . Esto ha llevado a matemáticos e informáticos a creer que el concepto de computabilidad se caracteriza con precisión mediante estos tres procesos equivalentes. Otros intentos formales de caracterizar la computabilidad han reforzado posteriormente esta creencia (véase más adelante ).

Por otro lado, la tesis de Church-Turing afirma que las tres clases de funciones computables definidas formalmente coinciden con la noción informal de función efectivamente calculable. Si bien la tesis goza de una aceptación casi universal, no puede demostrarse formalmente, ya que el concepto de calculabilidad efectiva solo se define de manera informal.

Desde su concepción, han surgido variaciones de la tesis original, incluyendo afirmaciones sobre lo que una computadora puede realizar físicamente en nuestro universo ( tesis física de Church-Turing ) y lo que se puede computar eficientemente ( 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 (véase más adelante ).

Declaración en palabras de Church y Turing

JB Rosser ( 1939 ) aborda la noción de "computabilidad efectiva" de la siguiente manera: "Claramente, la existencia de CC y RC [es decir, las pruebas de Church y Rosser de la afirmación de que no existe un método efectivo para decidir la verdad] presupone una definición precisa de 'efectivo'. 'Método efectivo' se usa aquí en el sentido bastante especial de un método cuyos pasos están predeterminados con precisión y que tiene la certeza de producir la respuesta en un número finito de pasos". [ 18 ] Así, el adverbio-adjetivo "efectivo" se usa en el sentido de "1a: que produce un efecto decidido, decisivo o deseado", y "capaz de producir un resultado". [ 19 ] [ 20 ] 

En lo sucesivo, las palabras «efectivamente calculable» significarán «producido por cualquier medio intuitivamente “efectivo”» y «efectivamente computable» significarán «producido por una máquina de Turing o un dispositivo mecánico equivalente». Las «definiciones» de Turing, que aparecen en una nota a pie de página de su tesis doctoral de 1938, Sistemas de lógica basados ​​en ordinales , dirigida por Church, son prácticamente las mismas:

† Usaremos la expresión "función computable" para referirnos a una función calculable por una máquina, y dejaremos que "efectivamente calculable" se refiera a la idea intuitiva sin una identificación particular con ninguna de estas definiciones. [ 21 ]

La tesis puede enunciarse como: Toda función efectivamente calculable es una función computable . [ 22 ] Church también afirmó que "Ningún procedimiento computacional se considerará un algoritmo a menos que pueda representarse como una máquina de Turing". [ 23 ]

Turing lo expresó de esta manera:

Se afirmó  que «una función es efectivamente calculable si sus valores pueden hallarse mediante algún proceso puramente mecánico». Podemos tomar esto literalmente, entendiendo que mediante un proceso puramente mecánico se refiere a uno que podría ser realizado por una máquina. El desarrollo  conduce a  una identificación de la computabilidad con la calculabilidad efectiva. [ † es la nota a pie de página citada anteriormente.] [ 21 ]

Historia

Uno de los problemas importantes para los lógicos en la década de 1930 fue el Entscheidungsproblem de David Hilbert y Wilhelm Ackermann , [ 24 ] que planteaba si existía un procedimiento mecánico para separar las verdades matemáticas de las falsedades matemáticas. Esta búsqueda requería que la noción de "algoritmo" o "calculabilidad efectiva" se definiera, al menos lo suficientemente bien como para que la búsqueda pudiera comenzar. [ 25 ] Pero desde el principio, los intentos de Alonzo Church comenzaron con un debate que continúa hasta el día de hoy. [ 26 ] ¿Debía la noción de "calculabilidad efectiva" ser (i) un "axioma o axiomas" en un sistema axiomático, (ii) simplemente una definición que "identificaba" dos o más proposiciones, (iii) una hipótesis empírica que debía verificarse mediante la observación de eventos naturales, o (iv) simplemente una propuesta para argumentar (es decir, una "tesis")?

Aproximadamente entre 1930 y 1952

En el curso del estudio del problema, Church y su estudiante Stephen Kleene introdujeron la noción de funciones λ-definibles y pudieron demostrar que varias clases amplias de funciones que se encuentran frecuentemente en la teoría de números eran λ-definibles. [ 27 ] El debate comenzó cuando Church propuso a Gödel que se definieran las funciones "efectivamente computables" como funciones λ-definibles. Sin embargo, Gödel no estaba convencido y calificó la propuesta de "completamente insatisfactoria". [ 28 ] En cambio, en correspondencia con Church (c. 1934–1935), Gödel propuso axiomatizar la noción de "calculabilidad efectiva"; de hecho, en una carta de 1935 a Kleene, Church informó que:

Su [la de Gödel] única idea en ese momento era que podría ser posible, en términos de calculabilidad efectiva como una noción indefinida, enunciar un conjunto de axiomas que incorporaran las propiedades generalmente aceptadas de esta noción, y hacer algo sobre esa base. [ 29 ]

Pero Gödel no ofreció más indicaciones. Finalmente, sugeriría su recursión, modificada por la sugerencia de Herbrand, que Gödel había detallado en sus conferencias de 1934 en Princeton, Nueva Jersey (Kleene y Rosser transcribieron las notas). Pero no creía que las dos ideas pudieran identificarse satisfactoriamente "excepto heurísticamente". [ 30 ]

A continuación, fue necesario identificar y demostrar la equivalencia de dos nociones de calculabilidad efectiva. Equipado con el cálculo λ y la recursión "general", Kleene, con la ayuda de Church y J. Barkley Rosser, elaboró ​​demostraciones (1933, 1935) para mostrar que ambos cálculos son equivalentes. Posteriormente, Church modificó sus métodos para incluir el uso de la recursión de Herbrand-Gödel y luego demostró (1936) que el problema de decisión es irresoluble: no existe ningún algoritmo que pueda determinar si una fórmula bien formada tiene una forma normal beta . [ 31 ]

Muchos años después, en una carta a Davis (c. 1965), Gödel dijo que «en el momento de esas conferencias [de 1934], no estaba en absoluto convencido de que su concepto de recursión comprendiera todas las recursiones posibles». [ 32 ] Hacia 1963-1964, Gödel repudiaría la recursión de Herbrand-Gödel y el cálculo lambda en favor de la máquina de Turing como definición de «algoritmo», «procedimiento mecánico» o «sistema formal». [ 33 ]

¿Una hipótesis que conduce a una ley natural?: A finales de 1936, el artículo de Alan Turing (que también demostraba que el problema de decisión es irresoluble) se presentó oralmente, pero aún no se había publicado. [ 34 ] Por otro lado, el artículo de Emil Post de 1936 ya se había publicado y se había certificado como independiente del trabajo de Turing. [ 35 ] Post discrepó profundamente de la "identificación" que hizo Church de la computabilidad efectiva con el cálculo lambda y la recursión, afirmando:

En realidad, el trabajo ya realizado por Church y otros lleva esta identificación considerablemente más allá de la etapa de hipótesis de trabajo. Pero enmascarar esta identificación bajo una definición  ... nos ciega ante la necesidad de su verificación continua. [ 36 ]

Más bien, consideraba la noción de "calculabilidad efectiva" como una mera "hipótesis de trabajo" que podría conducir, mediante razonamiento inductivo, a una " ley natural " en lugar de a "una definición o un axioma". [ 37 ] Esta idea fue duramente criticada por Church. [ 38 ]

Así, Post, en su artículo de 1936, también descartaba la sugerencia de Gödel a Church en 1934-1935 de que la tesis podría expresarse como un axioma o un conjunto de axiomas. [ 29 ]

Turing añade otra definición, Rosser equipara las tres : En poco tiempo, apareció el artículo de Turing de 1936-1937 «Sobre los números computables, con una aplicación al problema de decisión » [ 34 ] . En él, enunció otra noción de «computabilidad efectiva» con la introducción de sus máquinas a (ahora conocidas como el modelo computacional abstracto de la máquina de Turing ). En un esbozo de demostración añadido como apéndice a su artículo de 1936-1937, Turing demostró que las clases de funciones definidas por el cálculo λ y las máquinas de Turing coincidían. [ 39 ] Church reconoció rápidamente lo convincente que era el análisis de Turing. En su reseña del artículo de Turing, dejó claro que la noción de Turing hacía «evidente de inmediato la identificación con la efectividad en el sentido ordinario (no definido explícitamente)». [ 40 ]

In a few years (1939) Turing would propose, like Church and Kleene before him, that his formal definition of mechanical computing agent was the correct one.[41] Thus, by 1939, both Church (1934) and Turing (1939) had individually proposed that their "formal systems" should be definitions of "effective calculability";[42] neither framed their statements as theses.

Rosser (1939) formally identified the three notions-as-definitions:

All three definitions are equivalent, so it does not matter which one is used.[43]

Kleene proposes Thesis I: This left the overt expression of a "thesis" to Kleene. In 1943 Kleene proposed his "Thesis I":[44]

This heuristic fact [general recursive functions are effectively calculable] ... led Church to state the following thesis. The same thesis is implicit in Turing's description of computing machines.

Thesis I. Every effectively calculable function (effectively decidable predicate) is general recursive [Kleene's italics]

Since a precise mathematical definition of the term effectively calculable (effectively decidable) has been wanting, we can take this thesis ... as a definition of it. ...

... the thesis has the character of an hypothesis—a point emphasized by Post and by Church. If we consider the thesis and its converse as definition, then the hypothesis is an hypothesis about the application of the mathematical theory developed from the definition. For the acceptance of the hypothesis, there are, as we have suggested, quite compelling grounds.

The Church–Turing Thesis: Stephen Kleene, in Introduction to Metamathematics, finally goes on to formally name "Church's Thesis" and "Turing's Thesis", using his theory of recursive realizability, having switched from presenting his work in the terminology of Church–Kleene lambda definability to that of Gödel–Kleene recursiveness (partial recursive functions). In this transition, Kleene modified Gödel's general recursive functions to allow for proofs of the unsolvability of problems in the intuitionism of E. J. Brouwer. In his graduate textbook on logic, "Church's thesis" is introduced and basic mathematical results are demonstrated to be unrealizable. Next, Kleene proceeds to present "Turing's thesis", where results are shown to be uncomputable, using his simplified derivation of a Turing machine based on the work of Emil Post. Both theses are proven equivalent by use of "Theorem XXX".

Tesis I. Toda función efectivamente calculable (predicado efectivamente decidible) es recursiva general . [ 45 ]

Teorema XXX: Las siguientes clases de funciones parciales son coextensivas, es decir, tienen los mismos miembros: (a) las funciones recursivas parciales, (b) las funciones computables  ... [ 46 ]

Tesis de Turing: La tesis de Turing de que toda función que se consideraría naturalmente computable es computable bajo su definición, es decir, por una de sus máquinas, es equivalente a la tesis de Church por el Teorema XXX. [ 46 ]

Finalmente, Kleene utiliza por primera vez el término «tesis Church-Turing» en una sección en la que ayuda a aclarar conceptos del artículo de Alan Turing «El problema de la palabra en semigrupos con cancelación», tal como lo exigió William Boone en una crítica. [ 47 ]

Desarrollos posteriores

Un intento por comprender mejor la noción de "computabilidad efectiva" llevó a Robin Gandy (alumno y amigo de Turing) en 1980 a analizar la computación de las máquinas (a diferencia de la computación humana realizada por una máquina de Turing). La curiosidad de Gandy por los autómatas celulares (incluido el juego de la vida de Conway ), el paralelismo y los autómatas cristalinos, y su análisis de estos, lo llevaron a proponer cuatro "principios (o restricciones)  ... que, según se argumenta, toda máquina debe satisfacer". [ 48 ] Su cuarto principio, el más importante, "el principio de causalidad", se basa en la "velocidad finita de propagación de efectos y señales; la física contemporánea rechaza la posibilidad de una acción instantánea a distancia". [ 49 ] A partir de estos principios y algunas restricciones adicionales —(1a) un límite inferior en las dimensiones lineales de cualquiera de las partes, (1b) un límite superior en la velocidad de propagación (la velocidad de la luz), (2) progreso discreto de la máquina y (3) comportamiento determinista— produce un teorema que dice: «Lo que puede ser calculado por un dispositivo que satisface los principios I-IV es computable». [ 50 ]

A finales de la década de 1990, Wilfried Sieg analizó las nociones de "calculabilidad efectiva" de Turing y Gandy con la intención de "precisar la noción informal, formular sus características generales axiomáticamente e investigar el marco axiomático". [ 51 ] En sus trabajos de 1997 y 2002, Sieg presenta una serie de restricciones sobre el comportamiento de una computadora —"un agente de computación humana que procede mecánicamente". Estas restricciones se reducen a:

  • "(B.1) (Acotación) Existe un límite fijo en el número de configuraciones simbólicas que una computadora puede reconocer inmediatamente.
  • "(B.2) (Acotación) Existe un límite fijo en el número de estados internos en los que puede estar una computadora.
  • "(L.1) (Localidad) Un ordenador solo puede cambiar elementos de una configuración simbólica observada.
  • "(L.2) (Localidad) Un ordenador puede cambiar la atención de una configuración simbólica a otra, pero las nuevas configuraciones observadas deben estar dentro de una distancia limitada de la configuración observada inmediatamente antes.
  • "(D) (Determinación) La (sub)configuración inmediatamente reconocible determina de forma única el siguiente paso de cálculo (y la id [descripción instantánea])"; expresado de otra manera: "El estado interno de un computador junto con la configuración observada fija de forma única el siguiente paso de cálculo y el siguiente estado interno." [ 52 ]

El asunto sigue siendo objeto de debate activo dentro de la comunidad académica. [ 53 ] [ 54 ]

La tesis como definición

La tesis puede considerarse simplemente una definición matemática ordinaria. Los comentarios de Gödel sobre el tema sugieren esta visión, por ejemplo: «la definición correcta de computabilidad mecánica fue establecida sin lugar a dudas por Turing». [ 55 ] Robert I. Soare argumenta explícitamente que la tesis no es más que una definición , [ 11 ] donde también sostiene que la definición de computabilidad de Turing tiene la misma probabilidad de ser correcta que la definición épsilon-delta de una función continua .

Éxito de la tesis

Se han propuesto otros formalismos (además de la recursión, el cálculo λ y la máquina de Turing) para describir la calculabilidad/computabilidad efectiva. Kleene (1952) añade a la lista las funciones " calculables en el sistema S 1 " de Kurt Gödel 1936, y los " sistemas canónicos [también llamados normales ] " de Emil Post (1943, 1946) . [ 56 ] En la década de 1950, Hao Wang y Martin Davis simplificaron enormemente el modelo de máquina de Turing de una cinta (véase máquina de Post-Turing ). Marvin Minsky amplió el modelo a dos o más cintas y simplificó enormemente las cintas en "contadores ascendentes y descendentes", que Melzak y Lambek desarrollaron aún más en lo que ahora se conoce como el modelo de máquina de contadores . A finales de la década de 1960 y principios de la de 1970, los investigadores ampliaron el modelo de máquina de contadores en la máquina de registros , un pariente cercano de la noción moderna de computadora . Otros modelos incluyen la lógica combinatoria y los algoritmos de Markov . Gurevich añade el modelo de máquina de punteros de Kolmogorov y Uspensky (1953, 1958): "... simplemente querían ... convencerse de que no hay manera de extender la noción de función computable." [ 57 ]  

Todas estas contribuciones implican pruebas de que los modelos son computacionalmente equivalentes a la máquina de Turing; se dice que tales modelos son Turing completos . Debido a que todos estos diferentes intentos de formalizar el concepto de "calculabilidad/computabilidad efectiva" han producido resultados equivalentes, ahora se asume generalmente que la tesis de Church-Turing es correcta. De hecho, Gödel (1936) propuso algo más fuerte que esto; observó que había algo "absoluto" en el concepto de "calculable en S 1 ":

También se puede demostrar que una función que es computable ['calculable'] en uno de los sistemas S i , o incluso en un sistema de tipo transfinito, ya es computable [calculable] en S 1 . Por lo tanto, el concepto 'computable' ['calculable'] es en cierto sentido definido 'absoluto', mientras que prácticamente todos los demás conceptos metamatemáticos familiares (por ejemplo, demostrable, definible, etc.) dependen esencialmente del sistema al que se definen  ... [ 58 ]

Uso informal en pruebas

Las demostraciones en la teoría de la computabilidad a menudo recurren a la tesis de Church-Turing de manera informal para establecer la computabilidad de las funciones, evitando los detalles (a menudo muy extensos) que implicaría una demostración formal y rigurosa. [ 59 ] Para establecer que una función es computable por una máquina de Turing, generalmente se considera suficiente dar una descripción informal en inglés de cómo se puede computar la función de manera efectiva, y luego concluir "por la tesis de Church-Turing" que la función es computable por una máquina de Turing (o, equivalentemente, parcialmente recursiva).

Dirk van Dalen da el siguiente ejemplo para ilustrar este uso informal de la tesis Church-Turing: [ 60 ]

Ejemplo: Cada conjunto recursivamente enumerable (RE) infinito contiene un conjunto recursivo infinito .

Demostración: Sea A una RE infinita. Enumeramos los elementos de A de la siguiente manera: n 0 , n 1 , n 2 , n 3 , ...

De esta lista extraemos una sublista creciente: ponemos m 0  = n 0 , después de un número finito de pasos encontramos un n k tal que n k > m 0 , ponemos m 1  = n k . Repetimos este procedimiento para encontrar m 2 > m 1 , etc. Esto produce una lista efectiva del subconjunto B={m 0 , m 1 , m 2 ,...} de A, con la propiedad m i < m i+1 .

Afirmación : B es decidible. Para comprobar si k pertenece a B, debemos verificar si k  = m i para algún i. Dado que la secuencia de m i es creciente, debemos generar como máximo k+1 elementos de la lista y compararlos con k. Si ninguno de ellos es igual a k, entonces k no pertenece a B. Como esta prueba es efectiva, B es decidible y, según la tesis de Church , recursivo.

Para que el ejemplo anterior fuera completamente riguroso, habría que construir cuidadosamente una máquina de Turing, o una función λ, o invocar con precisión los axiomas de recursión, o, en el mejor de los casos, recurrir ingeniosamente a diversos teoremas de la teoría de la computabilidad. Pero como el teórico de la computabilidad cree que la computabilidad de Turing describe correctamente lo que se puede computar de forma efectiva, y dado que se describe un procedimiento efectivo en inglés para determinar el conjunto B, el teórico de la computabilidad acepta esto como prueba de que el conjunto es, en efecto, recursivo.

Variaciones

El éxito de la tesis de Church-Turing impulsó la propuesta de variaciones de la misma. Por ejemplo, la tesis física de Church-Turing afirma: "Todas las funciones físicamente computables son Turing-computables". [ 61 ] : 101

La tesis de Church-Turing no dice nada sobre la eficiencia con la que un modelo de computación puede simular otro. Se ha demostrado, por ejemplo, que una máquina de Turing universal (de múltiples cintas) solo sufre un factor de ralentización logarítmico al simular cualquier máquina de Turing. [ 62 ]

Una variación de la tesis de Church-Turing aborda si un modelo de computación arbitrario pero "razonable" puede simularse eficientemente. Esto se denomina tesis de factibilidad , [ 63 ] también conocida como tesis de Church-Turing ( clásica ) de la teoría de la complejidad o tesis de Church-Turing extendida , que no se debe a Church ni a Turing, sino que se desarrolló gradualmente en el marco de la teoría de la complejidad . Esta tesis afirma: [ 64 ] "Una máquina de Turing probabilística puede simular eficientemente cualquier modelo de computación realista". La palabra "eficientemente" aquí significa hasta reducciones en tiempo polinomial . Esta tesis fue originalmente denominada tesis de Church-Turing de la teoría de la complejidad computacional por Ethan Bernstein y Umesh Vazirani (1997). La tesis de Church-Turing de la teoría de la complejidad postula, entonces, que todos los modelos de computación "razonables" generan la misma clase de problemas que pueden calcularse en tiempo polinomial. Suponiendo la conjetura de que el tiempo polinomial probabilístico ( BPP ) es igual al tiempo polinomial determinista ( P ), la palabra «probabilístico» es opcional en la tesis de Church-Turing de la teoría de la complejidad. Una tesis similar, llamada tesis de la invariancia , fue introducida por Cees F. Slot y Peter van Emde Boas. Esta afirma: « Las máquinas “ razonables” pueden simularse entre sí con una sobrecarga de tiempo acotada polinomialmente y una sobrecarga de espacio de factor constante». [ 65 ] La tesis apareció originalmente en un artículo en STOC '84, que fue el primer artículo en demostrar que se podía lograr simultáneamente una sobrecarga de tiempo polinomial y una sobrecarga de espacio constante para una simulación de una máquina de acceso aleatorio en una máquina de Turing. [ 66 ]

Si se demuestra que BQP es un superconjunto estricto de BPP , se invalidaría la tesis de Church-Turing en la teoría de la complejidad. En otras palabras, existirían algoritmos cuánticos eficientes que realizarían tareas para las que no existen algoritmos probabilísticos eficientes . Sin embargo, esto no invalidaría la tesis original de Church-Turing, ya que una computadora cuántica siempre puede ser simulada por una máquina de Turing, pero sí invalidaría la tesis clásica de Church-Turing en la teoría de la complejidad por razones de eficiencia. En consecuencia, la tesis de Church-Turing en la teoría de la complejidad cuántica afirma: [ 64 ] "Una máquina de Turing cuántica puede simular eficientemente cualquier modelo de computación realista".

Eugene Eberbach y Peter Wegner afirman que la tesis de Church-Turing a veces se interpreta de forma demasiado amplia, declarando: «Aunque [...] las máquinas de Turing expresan el comportamiento de los algoritmos, la afirmación más amplia de que los algoritmos capturan con precisión lo que se puede computar es inválida». [ 67 ] Afirman que las formas de computación no capturadas por la tesis son relevantes hoy en día, términos que denominan computación super-Turing .

Implicaciones filosóficas

Los filósofos han interpretado la tesis de Church-Turing como algo con implicaciones para la filosofía de la mente . [ 68 ] [ 69 ] [ 70 ] B. Jack Copeland afirma que es una cuestión empírica abierta si existen procesos físicos deterministas reales que, a largo plazo, escapan a la simulación por una máquina de Turing; además, afirma que es una cuestión empírica abierta si alguno de estos procesos está involucrado en el funcionamiento del cerebro humano. [ 71 ] También hay algunas cuestiones abiertas importantes que abarcan la relación entre la tesis de Church-Turing y la física, y la posibilidad de la hipercomputación . Cuando se aplica a la física, la tesis tiene varios significados posibles:

  1. El universo es equivalente a una máquina de Turing; por lo tanto, calcular funciones no recursivas es físicamente imposible. Esto se conoce como la tesis fuerte de Church-Turing o principio de Church-Turing-Deutsch , y constituye un fundamento de la física digital .
  2. El universo no es equivalente a una máquina de Turing (es decir, las leyes de la física no son computables por una máquina de Turing), pero los eventos físicos incomputables no son aprovechables para la construcción de una hipercomputadora . Por ejemplo, un universo en el que la física involucra números reales aleatorios , en contraposición a los números reales computables , entraría en esta categoría.
  3. El universo es una hipercomputadora , y es posible construir dispositivos físicos para aprovechar esta propiedad y calcular funciones no recursivas. Por ejemplo, es una cuestión abierta si todos los eventos de la mecánica cuántica son computables por una máquina de Turing, aunque se sabe que los modelos rigurosos, como las máquinas de Turing cuánticas, son equivalentes a las máquinas de Turing deterministas. (No son necesariamente equivalentes en eficiencia; véase más arriba). John Lucas y Roger Penrose han sugerido que la mente humana podría ser el resultado de algún tipo de computación "no algorítmica" mejorada mediante la mecánica cuántica. [ 72 ] [ 73 ]

Existen muchas otras posibilidades técnicas que quedan fuera o entre estas tres categorías, pero estas sirven para ilustrar el alcance del concepto.

Los aspectos filosóficos de la tesis, tanto en lo que respecta a las computadoras físicas como biológicas, también se discuten en el libro de texto de Odifreddi de 1989 sobre la teoría de la recursión. [ 74 ] : 101–123

Funciones no computables

Es posible definir formalmente funciones que no son computables. Un ejemplo conocido es la función Busy Beaver . Esta función recibe una entrada n y devuelve el mayor número de símbolos que una máquina de Turing con n estados puede imprimir antes de detenerse, cuando se ejecuta sin entrada. Encontrar una cota superior para la función Busy Beaver equivale a resolver el problema de la parada , un problema que se sabe que las máquinas de Turing no pueden resolver. Dado que la función Busy Beaver no puede ser computada por máquinas de Turing, la tesis de Church-Turing afirma que esta función no puede ser computada eficazmente por ningún método.

Varios modelos computacionales permiten el cálculo de funciones no computables (de Church-Turing). Estos se conocen como hipercomputadoras .

Mark Burgin sostiene que los algoritmos superrecursivos, como las máquinas de Turing inductivas, refutan la tesis de Church-Turing. [ 75 ] Su argumento se basa en una definición de algoritmo más amplia que la ordinaria, de modo que las funciones no computables obtenidas de algunas máquinas de Turing inductivas se denominan computables. Esta interpretación de la tesis de Church-Turing difiere de la interpretación comúnmente aceptada en la teoría de la computabilidad, analizada anteriormente. El argumento de que los algoritmos superrecursivos son, en efecto, algoritmos en el sentido de la tesis de Church-Turing no ha encontrado una amplia aceptación dentro de la comunidad de investigación en computabilidad.

Véase también

Notas

  1. ↑ También conocida como tesis de computabilidad , [ 1 ] la tesis de Turing-Church , [ 2 ] la conjetura de Church-Turing , tesis de Church , conjetura de Church y tesis de Turing .

Referencias

  1. ↑ Soare, Robert I. (1 de septiembre de 2009). "Máquinas oráculo de Turing, computación en línea y tres desplazamientos en la teoría de la computabilidad" . Annals of Pure and Applied Logic . Computation and Logic in the Real World: CiE 2007. 160 (3): 368– 399. doi : 10.1016/j.apal.2009.01.008 . ISSN 0168-0072 . 
  2. ↑ Conrad, Michael (mayo de 1985). "Sobre los principios de diseño para una computadora molecular". Communications of the ACM . 28 (5): 464– 480. doi : 10.1145/3532.3533 .
  3. ↑ Steinert-Threlkeld, Shane. "Cálculos Lambda" . Enciclopedia de Filosofía en Internet . Consultado el 24 de febrero de 2026 .
  4. ↑ Church, Alonzo (mayo de 1935). "Un problema irresoluble de la teoría elemental de números. Informe preliminar" (PDF) . Boletín de la Sociedad Matemática Americana . 41 (5): 332–333 . Recuperado el 24 de febrero de 2026 .
  5. ↑ Church, Alonzo (julio de 1935). "Un problema irresoluble de la teoría elemental de números (informe preliminar)" (PDF) . Boletín de la Sociedad Matemática Americana . 41 (7): 453. Recuperado el 24 de febrero de 2026 .
  6. ↑ Church, Alonzo (abril de 1936). "Un problema irresoluble de la teoría elemental de números" . American Journal of Mathematics . 58 (2): 345–363 . doi : 10.2307/2371045 . Recuperado el 24 de febrero de 2026 .
  7. ↑ El resumen del artículo de Church fue recibido por el Boletín de la Sociedad Matemática Americana el 22 de marzo de 1935, [ 4 ] presentado a la Sociedad Matemática Americana el 19 de abril de 1935, [ 5 ] y publicado el 15 de abril de 1936. [ 6 ]
  8. ↑ Correspondencia entre Max Newman y Church en los documentos de Alonzo Church
  9. ↑ Turing, Alan (2004). The essential Turing : seminal writings in computing, logic, philosophy, artificial intelligence, and artificial life, plus the secrets of Enigma (PDF) . Oxford: Clarendon Press. p. 44. ISBN   9780198250791. Consultado el 06-12-2021 .
  10. ↑ Turing, AM (1937). "Sobre los números computables, con una aplicación al problema de decisión" . Actas de la Sociedad Matemática de Londres . s2-42 (1): 230– 265. doi : 10.1112/plms/s2-42.1.230 . Consultado el 24 de febrero de 2026 .
  11. 1 2 Soare, Robert I. (septiembre de 1996). "Computabilidad y recursión". Boletín de lógica simbólica . 2 (3): 284– 321. CiteSeerX 10.1.1.35.5803 . doi : 10.2307/420992 . JSTOR 420992. S2CID 5894394 .   
  12. ↑ Turing, quien había avanzado considerablemente en la redacción de sus propios resultados, se sintió decepcionado al enterarse del artículo de Church poco después de su publicación. [ 8 ] [ 9 ] Turing completó rápidamente su artículo y lo publicó apresuradamente; fue recibido por las Actas de la Sociedad Matemática de Londres el 28 de mayo de 1936, leído el 12 de noviembre de 1936 y publicado en la serie 2, volumen 42 (1936-1937) [ 10 ] ; apareció en dos secciones: en la Parte 3 (páginas 230-240), publicada el 30 de noviembre de 1936 y en la Parte 4 (páginas 241-265), publicada el 23 de diciembre de 1936; Turing añadió correcciones en el volumen 43 (1937), págs. 544-546. [ 11 ] : 45
  13. ↑ Iglesia 1936a
  14. ↑ Kleene 1936
  15. ↑ Turing 1937a
  16. ↑ Kleene 1936
  17. ↑ Turing 1937b . Esquema de la demostración en la página 153:λ-definible{\displaystyle \lambda {\mbox{-definible}}}⟹triv{\displaystyle {\stackrel {triv}{\implies }}}λ-K-definible{\displaystyle \lambda {\mbox{-}}K{\mbox{-definible}}}⟹160{\displaystyle {\stackrel {160}{\implies }}}Computable por Turing{\displaystyle {\mbox{Computable por Turing}}}⟹161{\displaystyle {\stackrel {161}{\implies }}}μ-recursivo{\displaystyle \mu {\mbox{-recursivo}}}⟹Klmiminortemi{\displaystyle {\stackrel {Kleene}{\implies }}}[ 16 ]λ-definible{\displaystyle \lambda {\mbox{-definible}}}
  18. ↑ Rosser 1939 en Davis 1965 :225 .
  19. ↑ "efectivo". Diccionario Colegiado Nuevo de Merriam-Webster (9.ª ed.). 
  20. ↑ Véase también "efectivo". Diccionario en línea Merriam-Webster (11.ª ed.) . Consultado el 26 de julio de 2014 . que también ofrece estas definiciones de "efectivo": la primera ["que produce un efecto decidido, decisivo o deseado"] como definición del sentido "1a" de la palabra "efectivo", y la segunda ["capaz de producir un resultado"] como parte de la "Discusión de sinónimos de EFFECTIVO" allí, (en la parte introductoria, donde resume las similitudes entre los significados de las palabras "efectivo", "eficaz", "eficiente" y "eficaz").
  21. 1 2 Turing, AM (1938). Sistemas de lógica basados ​​en ordinales (PDF) (PhD). Universidad de Princeton. pág. 8. Archivado del original (PDF) el 23-10-2012 . Recuperado el 23-06-2012 . 
  22. ↑ Gandy (1980 :123) lo expresa así: "Lo que es efectivamente calculable es computable". Él lo llama "la tesis de Church".
  23. ↑ Copeland, B. Jack (2024), "La tesis de Church-Turing" , en Zalta, Edward N.; Nodelman, Uri (eds.), La enciclopedia de filosofía de Stanford ( edición de invierno de 2024), Laboratorio de Investigación en Metafísica, Universidad de Stanford , consultado el 11 de junio de 2025. 
  24. ^ Hilbert, David; Ackermann, Wilhelm (1972) [1ª ed. 1928]. Grundzüge der theoretischen Logik [ Fundamentos de la lógica teórica ] (en alemán) (6ª ed.). Berlín, Alemania: Springer. ISBN  3-540-05843-5.Publicado en traducción al inglés como Principles of Mathematical Logic (1950). Providence, Rhode Island, EE. UU.: AMS Chelsea Publishing.
  25. ↑ Comentario de Davis antes de Church 1936 en Davis 1965 :88 . Church usa las palabras "calculabilidad efectiva" en la página 100 y siguientes.
  26. ↑ En su reseña de Church's Thesis after 70 Years editado por Adam Olszewski et al. 2006, la crítica de Peter Smith a un artículo de Muraswski y Wolenski sugiere 4 "líneas" respecto al estatus de la tesis Church-Turing: (1) hipótesis empírica, (2) axioma o teorema, (3) definición, (4) explicación. Pero Smith opina que (4) es indistinguible de (3). Smith, Peter (2007-07-11). "Church's Thesis after 70 Years" (PDF) . Logic Matters .
  27. ↑ Nota al pie 3 en Church 1936a Un problema irresoluble de la teoría elemental de números , en Davis 1965 :89 .
  28. ↑ Dawson 1997 :99 .
  29. 1 2 Sieg 1997 :160 .
  30. ↑ Sieg 1997 :160 , citando la carta de 1935 escrita por Church a Kleene, nota al pie 3 en Gödel 1965 en Davis 1965 :44 .
  31. ↑ Iglesia 1936 en Davis 1965 :105ff.
  32. ↑ Comentario de Davis antes de Gödel 1965 en Davis 1965 :40 .
  33. ↑ Para un análisis detallado de la adopción por parte de Gödel de las máquinas de Turing como modelos de computación, véase Shagrir, Oron (15 de junio de 2006). «Gödel sobre Turing y la computabilidad» (PDF) . La tesis de Church después de 70 años . De Gruyter. págs. 393–419 . doi : 10.1515/9783110325461.393 . ISBN  978-3-11-032494-5. Archivado del original (PDF) el 17-12-2015 . Consultado el 08-02-2016 .
  34. 1 2 Turing 1937a .
  35. ↑ Nota al pie del editor sobre Proceso combinatorio finito posterior a 1936. Formulación I. en Davis 1965 :289 .
  36. ↑ Publicación de 1936 en Davis 1965 :291, nota al pie 8.
  37. ↑ Publicación de 1936 en Davis 1965 :291 .
  38. ^ Sieg 1997 : 171 y 176-177 .
  39. ↑ Turing 1936–1937 en Davis 1965 :263ff.
  40. ↑ Iglesia 1937 .
  41. ↑ Turing 1939 en Davis:160.
  42. ↑ Church 1934 en Davis 1965 :100 , también Turing 1939 en Davis 1965 :160 .
  43. ↑ Rosser 1939 en Davis 1965 :226 (cursiva añadida).
  44. ↑ Kleene 1943 , pág. 60 en Davis 1965 :274 (notas a pie de página omitidas). 
  45. ↑ Kleene 1952 :300.
  46. 1 2 Kleene 1952 :376.
  47. ↑ Kleene 1952 :382, 536
  48. ↑ Gandy 1980 :123 y ss.
  49. ↑ Gandy 1980 :135
  50. ↑ Gandy 1980 :126
  51. ^ Sieg 1998–1999 en Sieg, Sommer y Talcott 2002 : 390 y siguientes. ; también Sieg 1997 : 154 y siguientes.
  52. ↑ En una nota a pie de página, Sieg divide la obra de Post de 1936 (B) en (B.1) y (B.2), y la obra de Post (L) en (L.1) y (L.2), y describe (D) de manera diferente. Con respecto a su propuesta de máquina Gandy, posteriormente añade LC.1, LC.2, GA.1 y GA.2. Estas son complejas; véase Sieg 1998–1999 en Sieg, Sommer y Talcott 2002 : 390 y ss.
  53. ↑ Una recopilación de artículos se puede encontrar en Olszewski, Woleński y Janusz (2006) . También una reseña de esta recopilación: Smith, Peter (11 de julio de 2007). "La tesis de Church después de 70 años" (PDF) .
  54. ↑ Véase también Hodges, Andrew (2005). "¿Tenían Church y Turing una tesis sobre las máquinas?" (PDF) . Archivado del original (PDF) el 4 de marzo de 2016. Consultado el 27 de julio de 2014 .
  55. ↑ Gödel, Kurt (1995) [193?]. «Proposiciones diofánticas indecidibles» . En Feferman, Solomon (ed.). Obras completas . Vol. 3. Nueva York: Oxford University Press . pág . 168. ISBN   978-0-19-507255-6OCLC 928791907​​ 
  56. ↑ Kleene 1952:320
  57. ↑ Gurevich 1988:2
  58. ↑ Traducción de Gödel (1936) por Davis en The Undecidable p. 83, que difiere en el uso de la palabra 'calculable' en la traducción de Kleene (1952) p. 321
  59. ↑ Horsten en Olszewski, Woleński y Janusz 2006 :256 .
  60. ↑ Gabbay 2001 :284
  61. ↑ Piccinini, Gualtiero (enero de 2007). "Computacionalismo, la tesis de Church-Turing y la falacia de Church-Turing" . Synthese . 154 (1): 97–120 . CiteSeerX 10.1.1.360.9796 . doi : 10.1007/s11229-005-0194-z . S2CID 494161. Archivado (PDF) del original el 24 de abril de 2008.  
  62. ↑ Arora, Sanjeev; Barak, Boaz (2009). Teoría de la complejidad: un enfoque moderno . Cambridge University Press . ISBN 978-0-521-42426-4.Secciones 1.4, "Máquinas como cadenas y la máquina de Turing universal" y 1.7, "Demostración del teorema 1.9".
  63. ↑ "Descripción oficial del problema" (PDF) . Archivado del original (PDF) el 24/11/2005.
  64. 1 2 Kaye, Phillip; Laflamme, Raymond; Mosca, Michele (2007). Introducción a la computación cuántica . Oxford University Press. págs. 5–6 . ISBN  978-0-19-857049-3.
  65. ↑ van Emde Boas, Peter (1990). "Modelos y simulaciones de máquinas". Manual de informática teórica A. Elsevier . pág. 5. 
  66. ↑ Slot, C.; van Emde Boas, P. (diciembre de 1984). Sobre cinta versus núcleo: una aplicación de funciones hash perfectas eficientes en espacio a la invariancia del espacio . STOC .
  67. ↑ Eberbach y Wegner 2003 , pág. 287 . 
  68. ↑ Abramson, Darren (2011). "La filosofía de la mente es (en parte) filosofía de la informática" . Minds and Machines . 21 (2): 203– 219. doi : 10.1007/s11023-011-9236-0 . S2CID 32116031 . 
  69. ↑ Copeland, B. Jack (10 de noviembre de 2017). "La tesis de Church-Turing" . En Zalta, Edward N. (ed.). Enciclopedia de filosofía de Stanford . ISSN 1095-5054 . OCLC 429049174 .  
  70. ↑ Para consultar artículos originales, véase Chalmers, David J. , ed. (2002). Philosophy of Mind: Classical and Contemporary Readings . Nueva York: Oxford University Press. ISBN 978-0-19-514581-6OCLC 610918145​​ 
  71. ↑ Copeland, B. Jack (2004). «Computación». En Floridi, Luciano (ed.). La guía Blackwell de la filosofía de la computación y la información . Wiley-Blackwell. pág. 15. ISBN  978-0-631-22919-3.
  72. ↑ cf. Penrose, Roger (1990). «Algoritmos y máquinas de Turing». La nueva mente del emperador: Sobre ordenadores, mentes y las leyes de la física . Oxford: Oxford University Press. pp. 47–49 . ISBN  978-0-19-851973-7OCLC 456785846​​ 
  73. ↑ Véase también la descripción de «la naturaleza no algorítmica de la intuición matemática», Penrose, Roger (1990). «¿Dónde reside la física de la mente?». La nueva mente del emperador: sobre ordenadores, mentes y las leyes de la física . Oxford: Oxford University Press. págs. 416-418 . ISBN  978-0-19-851973-7OCLC 456785846​​ 
  74. ↑ Piergiorgio Odifreddi (1989). Teoría clásica de la recursión . Estudios de lógica y fundamentos de las matemáticas. Vol. 125. Ámsterdam, Países Bajos: North Holland. 
  75. ↑ Burgin, Mark (2005). Algoritmos superrecursivos . Monografías en Ciencias de la Computación. Nueva York: Springer. ISBN 978-0-387-95569-8OCLC 990755791​​ 

Fuentes

  • Barwise, Jon ; Keisler, HJ ; Kunen, Kenneth , eds. (1980). El Simposio Kleene . Ámsterdam: North-Holland Publishing Company. ISBN 978-0-444-85345-5.
  • Ben-Amram, AM (2005). "La tesis de Church-Turing y sus similares" . SIGACT News . 36 (3): 113– 116. CiteSeerX 10.1.1.74.7308 . doi : 10.1145/1086649.1086651 . S2CID 13566703. Archivado del original (PS) el 6 de julio de 2017. Recuperado el 24 de octubre de 2017 .  
  • Bernstein, E.; Vazirani, U. (1997). "Teoría de la complejidad cuántica". Revista SIAM de Computación . 26 (5): 1411–1473 . CiteSeerX 10.1.1.655.1186 . doi : 10.1137/S0097539796300921 . 
  • Blass, Andreas ; Gurevich, Yuri (octubre de 2003). «Algoritmos: En busca de definiciones absolutas» (PDF) . Boletín de la Asociación Europea de Ciencias de la Computación Teórica (81). Archivado (PDF) del original el 27 de julio de 2004.
  • Burgin, Mark (2005). «Algoritmos superrecursivos». Monografías en informática . Springer. ISBN 978-0-387-95569-8.
  • Church, Alonzo (1932). "Un conjunto de postulados para la fundación de la lógica". Anales de Matemáticas . 33 (2): 346– 366. doi : 10.2307/1968337 . JSTOR 1968337 . 
  • Church, Alonzo (abril de 1936a). «Un problema irresoluble de la teoría elemental de números» (PDF) . American Journal of Mathematics . 58 (2): 345–363 . doi : 10.2307/2371045 . JSTOR 2371045. S2CID 14181275. Archivado del original (PDF) el 27 de febrero de 2020.  
  • Church, Alonzo (junio de 1936b). " Una nota sobre el problema de la decisión". Journal of Symbolic Logic . 1 (1): 40– 41. doi : 10.2307/2269326 . JSTOR 2269326. S2CID 42323521 .  
  • Church, Alonzo (marzo de 1937). "Reseña: AM Turing, Sobre los números computables, con una aplicación al problema de decisión". Journal of Symbolic Logic . 2 (1): 42– 43. doi : 10.2307/2268810 . JSTOR 2268810 . 
  • Church, Alonzo (1941). Los cálculos de la conversión lambda . Princeton: Princeton University Press.
  • Cooper, SB; Odifreddi, P. (2003). "Incomputabilidad en la naturaleza". En SB Cooper; SS Goncharov (eds.). Computabilidad y modelos: perspectivas de Oriente y Occidente . Kluwer Academic/Plenum Publishers. pp. 137–160 . 
  • Davis, Martin , ed. (1965). Lo indecidible, trabajos básicos sobre proposiciones indecidibles, problemas irresolubles y funciones computables . Nueva York: Raven Press.Incluye artículos originales de Gödel, Church, Turing, Rosser, Kleene y Post mencionados en esta sección.
    • Gödel, Kurt. "Sobre proposiciones indecidibles de sistemas matemáticos formales". En Davis (1965) .
  • Dawson, John W. Jr. (1997). Logical Dilemmas: The Life and Work of Kurt Gödel. Wellesley, Massachusetts, US: A. K. Peters.
  • Eberbach, E.; Wegner, P. (October 2003). "Beyond Turing Machines"(PDF). Bulletin of the European Association for Theoretical Computer Science (81): 279–304. CiteSeerX 10.1.1.61.9759. Archived(PDF) from the original on 2016-03-15.
  • Gabbay, D. M. (2001). Handbook of Philosophical Logic. Vol. 1 (2nd ed.).
  • Gandy, Robin (1980). "Church's Thesis and the Principles for Mechanisms". In H. J. Barwise; H. J. Keisler; K. Kunen (eds.). The Kleene Symposium. North-Holland Publishing Company. pp. 123–148.
  • Gandy, Robin (1994). Herken, Rolf (ed.). The universal Turing Machine: A Half-Century Survey. New York: Wien Springer–Verlag. pp. 51ff. ISBN 978-3-211-82637-9.
  • Gödel, Kurt (1936). "Über die Lāange von Beweisen" [On The Length of Proofs]. Ergenbnisse Eines Mathematishen Kolloquiums (in German) (7). Heft: 23–24. Cited by Kleene (1952).
  • Gurevich, Yuri (June 1988). "On Kolmogorov Machines and Related Issues". Bulletin of European Association for Theoretical Computer Science (35): 71–82.
  • Gurevich, Yuri (July 2000). "Sequential Abstract State Machines Capture Sequential Algorithms"(PDF). ACM Transactions on Computational Logic. 1 (1): 77–111. CiteSeerX 10.1.1.146.3017. doi:10.1145/343369.343384. S2CID 2031696. Archived(PDF) from the original on 2003-10-16.
  • Herbrand, Jacques (1932). "Sur la non-contradiction de l'arithmétique". Journal für die Reine und Angewandte Mathematik (in French). 166: 1–8. doi:10.1515/crll.1932.166.1. S2CID 116636410.
  • Hofstadter, Douglas R. (1999-02-05). "Chapter XVII: Church, Turing, Tarski, and Others". Gödel, Escher, Bach: an Eternal Golden Braid (Twentieth-anniversary ed.). Basic Books. pp. 559–585. ISBN 0-465-02656-7.
  • Kleene, Stephen Cole (January 1935). "A Theory of Positive Integers in Formal Logic". American Journal of Mathematics. 57 (1): 153–173 & 219–244. doi:10.2307/2372027. JSTOR 2372027.
  • Kleene, Stephen Cole (1936). "Lambda-Definability and Recursiveness". Duke Mathematical Journal. 2 (2): 340–353. doi:10.1215/s0012-7094-36-00227-2.
  • Kleene, Stephen Cole (1943). "Recursive Predicates and Quantifiers". Transactions of the American Mathematical Society. 53 (1): 41–73. doi:10.2307/1990131. JSTOR 1990131. Reprinted in The Undecidable, p. 255ff. Kleene refined his definition of "general recursion" and proceeded in his chapter "12. Algorithmic theories" to posit "Thesis I" (p. 274); he would later repeat this thesis (in Kleene 1952:300) and name it "Church's Thesis" (Kleene 1952:317) (i.e., the Church thesis).
  • Kleene, Stephen Cole (1952). Introduction to Metamathematics. North-Holland. OCLC 523942.
  • Knuth, Donald (1973). The Art of Computer Programming. Vol. 1/Fundamental Algorithms (2nd ed.). Addison–Wesley.
  • Kugel, Peter (November 2005). "It's time to think outside the computational box". Communications of the ACM. 48 (11): 32–37. CiteSeerX 10.1.1.137.6939. doi:10.1145/1096000.1096001. S2CID 29843806.
  • Lewis, H.R.; Papadimitriou, C.H. (1998). Elements of the Theory of Computation. Upper Saddle River, New Jersey, US: Prentice-Hall.
  • Manna, Zohar (2003) [1974]. Mathematical Theory of Computation. Dover. ISBN 978-0-486-43238-0.{{cite book}}: CS1 maint: location missing publisher (link)
  • Markov, A. A. (1960) [1954]. "The Theory of Algorithms". American Mathematical Society Translations. 2 (15): 1–14.
  • Olszewski, Adam; Woleński, Jan; Janusz, Robert, eds. (2006). La tesis de Church después de 70 años . Frankfurt: Ontos. ISBN 978-3-938793-09-1OCLC 909679288​​ 
  • Pour-El, MB ; Richards, JI (1989). Computabilidad en análisis y física . Springer Verlag .
  • Rosser, JB (1939). " Una exposición informal de las demostraciones del teorema de Gödel y del teorema de Church". The Journal of Symbolic Logic . 4 (2): 53– 60. doi : 10.2307/2269059 . JSTOR 2269059. S2CID 39499392 .  
  • Sieg, Wilfried (junio de 1997). "Paso a paso recursivo: el análisis de Church sobre la calculabilidad efectiva". Boletín de lógica simbólica . 3 (2): 154– 180. doi : 10.2307/421012 . JSTOR 421012 . 
  • Sieg, Wilfried; Sommer, Richard; Talcott, Carolyn, eds. (2002). Reflexiones sobre los fundamentos de las matemáticas: ensayos en honor de Solomon Feferman . Lecture Notes in Logic. Vol.  15. AK Peters, Ltd. ISBN 978-1-56881-169-7.
  • Syropoulos, Apostolos (2008). Hipercomputación: Computación más allá de la barrera Church-Turing . Springer. ISBN 978-0-387-30886-9.
  • Turing, AM (1937a) [Presentado a la Sociedad en noviembre de 1936], "Sobre los números computables, con una aplicación al problema de decisión" (PDF) , Actas de la Sociedad Matemática de Londres , 2, vol.  42, págs. 230–265 , Bibcode : 1937PLMS...42..230T , doi : 10.1112/plms/s2-42.1.230 , S2CID 73712  y Turing, AM (1938). "Sobre los números computables, con una aplicación al problema de decisión: una corrección". Actas de la Sociedad Matemática de Londres . 2. Vol. 43 (publicado en 1937). pp. 544– 546. doi : 10.1112/plms/s2-43.6.544 .  (Véase también: Davis 1965 : 115 y ss.)
  • Turing, Alan Mathison (diciembre de 1937b). «Computabilidad y λ-definibilidad» (PDF) . Journal of Symbolic Logic . 2 (4): 153– 163. doi : 10.2307/2268280 . JSTOR 2268280. S2CID 2317046. Archivado del original (PDF) el 9 de agosto de 2020.