Tesis de Church-Turing

Tesis sobre la naturaleza de la computabilidad

En teoría de la computabilidad , la tesis de Church-Turing (también conocida como tesis de computabilidad , ^[1] tesis de Turing-Church , ^[2] conjetura de Church -Turing , tesis de Church , conjetura de Church y tesis de Turing ) es una tesis sobre la naturaleza de las 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 por una máquina de Turing . La tesis recibe su 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 utilizar el término informal efectivamente calculable para describir funciones que son computables mediante 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 :

• 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 está cerrada bajo composición , recursión y minimización , e incluye cero , sucesor y todas las proyecciones .
• En 1936, 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 de los números naturales se denomina λ-computable si la función correspondiente de los numerales de Church puede representarse mediante un término del cálculo λ.
• También en 1936, antes de conocer el trabajo de Church, ^[6] Alan Turing creó un modelo teórico para máquinas, hoy llamadas máquinas de Turing, que podían realizar cálculos a partir de datos de entrada 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 de Turing si alguna máquina de Turing calcula la función correspondiente sobre números naturales codificados.

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 computable según el método de Turing, y si y solo si es recursiva general . Esto ha llevado a los matemáticos y científicos 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 otra parte, la tesis de Church-Turing afirma que las tres clases formalmente definidas de funciones computables mencionadas anteriormente coinciden con la noción informal de función efectivamente calculable. Aunque la tesis tiene una aceptación casi universal, no se puede demostrar formalmente, ya que el concepto de calculabilidad efectiva solo se define informalmente.

Desde su inicio, han surgido variaciones sobre la tesis original, incluyendo afirmaciones sobre lo que puede ser realizado físicamente por una computadora en nuestro universo ( tesis física de Church-Turing ) y lo que puede ser computado eficientemente (tesis de Church-Turing (teoría de la complejidad)). Estas variaciones no se deben a Church o 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).

Declaración en palabras de Church y Turing

JB Rosser  (1939) aborda la noción de "computabilidad efectiva" de la siguiente manera: "Es claro que la existencia de CC y RC (las pruebas de Church y Rosser) presupone una definición precisa de 'efectivo'. 'Método efectivo' se utiliza aquí en el sentido bastante especial de un método cada paso del cual está predeterminado con precisión y que es seguro que producirá la respuesta en un número finito de pasos". ^[12] Así, el adjetivo-adverbio "efectivo" se utiliza en un sentido de "1a: producir un efecto decidido, decisivo o deseado", y "capaz de producir un resultado". ^{[13] [14]}

En lo sucesivo, las palabras "efectivamente calculable" significarán "producido por cualquier medio intuitivamente 'efectivo'" y "efectivamente computable" significará "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 en su tesis doctoral de 1938, Systems of Logic Based on Ordinals (Sistemas de lógica basados ​​en ordinales) , supervisada por Church, son prácticamente las mismas:

^† Utilizaremos la expresión "función computable" para significar una función calculable por una máquina, y haremos referencia a "efectivamente calculable" a la idea intuitiva sin identificación particular con ninguna de estas definiciones. ^[15]

La tesis puede enunciarse así: Toda función efectivamente calculable es una función computable . ^[16] Church también afirmó que «Ningún procedimiento computacional será considerado un algoritmo a menos que pueda representarse como una máquina de Turing». ^{[ cita requerida ]} 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 entiende uno que podría ser llevado a cabo por una máquina. El desarrollo... conduce a... una identificación de computabilidad ^† con calculabilidad efectiva. [ ^† es la nota al pie citada anteriormente.] ^[15]

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 , ^[17] que preguntaba si habí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" estuviera precisada, al menos lo suficientemente bien como para que la búsqueda comenzara. ^[18] Pero desde el principio los intentos de Alonzo Church comenzaron con un debate que continúa hasta el día de hoy. ^{[19] ¿} Debía ^{[ aclarar ]} que la noción de "calculabilidad efectiva" era (i) un "axioma o axiomas" en un sistema axiomático, (ii) meramente 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) solo una propuesta por el bien del argumento (es decir, una "tesis")?

Alrededor de 1930-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 grandes de funciones que se encuentran frecuentemente en la teoría de números eran λ-definibles. ^[20] El debate comenzó cuando Church propuso a Gödel que se definieran las funciones "efectivamente computables" como funciones λ-definibles. Gödel, sin embargo, no estaba convencido y calificó la propuesta de "totalmente insatisfactoria". ^[21] Más bien, 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:

La única idea que tenía [Gödel] 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 incorporarían las propiedades generalmente aceptadas de esta noción, y hacer algo sobre esa base. ^[22]

Pero Gödel no ofreció más indicaciones. Finalmente, sugirió 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". ^[23]

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, produjo pruebas (1933, 1935) para demostrar que los dos cálculos son equivalentes. Church posteriormente modificó sus métodos para incluir el uso de la recursión de Herbrand-Gödel y luego demostró (1936) que el Entscheidungsproblem es irresoluble: no existe ningún algoritmo que pueda determinar si una fórmula bien formada tiene una forma normal beta . ^[24]

Muchos años después, en una carta a Davis (c. 1965), Gödel dijo que "en el momento de estas conferencias [1934], no estaba del todo convencido de que su concepto de recursión comprendiera todas las recursiones posibles". ^[25] Entre 1963 y 1964, Gödel rechazaría la recursión de Herbrand-Gödel y el cálculo λ en favor de la máquina de Turing como definición de "algoritmo", "procedimiento mecánico" o "sistema formal". ^[26]

¿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 Entscheidungsproblem era irresoluble) fue presentado oralmente, pero aún no había aparecido impreso. ^[27] Por otro lado, el artículo de Emil Post de 1936 había aparecido y fue certificado como independiente del trabajo de Turing. ^[28] Post estaba en total desacuerdo con la "identificación" de Church de la computabilidad efectiva con el cálculo λ y la recursión, afirmando:

En realidad, el trabajo ya realizado por Church y otros lleva esta identificación mucho más allá de la etapa de hipótesis de trabajo. Pero ocultar esta identificación bajo una definición… nos ciega a la necesidad de su verificación continua. ^[29]

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

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

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 la endoscopia" ^[27] . En él, Turing enunciaba 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 ). Y en un esbozo de prueba añadido como "apéndice" a su artículo de 1936-1937, Turing demostraba que las clases de funciones definidas por el cálculo λ y las máquinas de Turing coincidían. ^[32] 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)". ^[33]

En pocos años (1939) Turing propondría, como Church y Kleene antes que él, que su definición formal de agente computacional mecánico era la correcta. ^[34] Así, en 1939, tanto Church (1934) como Turing (1939) habían propuesto individualmente que sus "sistemas formales" deberían ser definiciones de "calculabilidad efectiva"; ^[35] ninguno de ellos formuló sus afirmaciones como tesis .

Rosser (1939) identificó formalmente las tres nociones como definiciones:

Las tres definiciones son equivalentes, por lo que no importa cuál se utilice. ^[36]

Kleene propone la Tesis I : Esto dejó en manos de Kleene la expresión explícita de una "tesis". En 1943, Kleene propuso su "Tesis I": ^[37]

Este hecho heurístico [las funciones recursivas generales son efectivamente calculables]... llevó a Church a enunciar la siguiente tesis. La misma tesis está implícita en la descripción que hace Turing de las máquinas de computación.

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

Como no existe una definición matemática precisa del término efectivamente calculable (efectivamente decidible), podemos tomar esta tesis... como una definición del mismo...

...la tesis tiene el carácter de una hipótesis, un punto que Post y Church enfatizaron. Si consideramos la tesis y su recíproca como una definición, entonces la hipótesis es una hipótesis sobre la aplicación de la teoría matemática desarrollada a partir de la definición. Para la aceptación de la hipótesis, existen, como hemos sugerido, razones bastante convincentes.

La tesis de Church-Turing : Stephen Kleene, en Introducción a las metamatemáticas , finalmente pasa a nombrar formalmente "Tesis de Church" y "Tesis de Turing", utilizando su teoría de realizabilidad recursiva. Kleene pasó de presentar su trabajo en la terminología de definibilidad lambda de Church-Kleene a la de recursividad de Gödel-Kleene (funciones recursivas parciales). En esta transición, Kleene modificó las funciones recursivas generales de Gödel para permitir pruebas de la insolubilidad de los problemas en el intuicionismo de EJ Brouwer. En su libro de texto de posgrado sobre lógica, se introduce la "tesis de Church" y se demuestra que los resultados matemáticos básicos son irrealizables. A continuación, Kleene procede a presentar la "tesis de Turing", donde se demuestra que los resultados son incomputables, utilizando su derivación simplificada de una máquina de Turing basada en el trabajo de Emil Post. Ambas tesis se demuestran equivalentes mediante el uso del "Teorema XXX".

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

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

Tesis de Turing: La tesis de Turing de que toda función que naturalmente sería considerada como computable es computable según su definición, es decir, por una de sus máquinas, es equivalente a la tesis de Church por el Teorema XXX. ^[39]

Kleene, finalmente, utiliza por primera vez el término "tesis de Church-Turing" en una sección en la que ayuda a dar aclaraciones a conceptos del trabajo de Alan Turing "El problema de las palabras en semigrupos con cancelación", como lo exigía una crítica de William Boone. ^[40]

Desarrollos posteriores

En 1980, Robin Gandy (alumno y amigo de Turing) intentó comprender mejor la noción de "computabilidad efectiva" y se dedicó a analizar la computación por máquina (en contraposición a 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 los mismos, lo llevaron a proponer cuatro "principios (o restricciones)... que, según se afirma, cualquier máquina debe satisfacer". ^[41] 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". ^[42] A partir de estos principios y algunas restricciones adicionales (1a) un límite inferior para las dimensiones lineales de cualquiera de las partes, (1b) un límite superior para 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 que "Lo que puede calcularse mediante un dispositivo que satisface los principios I a IV es computable". ^[43]

A finales de los años 1990, Wilfried Sieg analizó las nociones de "calculabilidad efectiva" de Turing y Gandy con la intención de "afinar la noción informal, formular sus características generales de manera axiomática e investigar el marco axiomático". ^[44] En su trabajo de 1997 y 2002, Sieg presenta una serie de restricciones al comportamiento de un computador -"un agente informático humano que procede mecánicamente". Estas restricciones se reducen a:

• "(B.1) (Limitación) Existe un límite fijo en la cantidad de configuraciones simbólicas que una computadora puede reconocer inmediatamente.
• "(B.2) (Limitación) Hay un límite fijo en la cantidad de estados internos en los que puede estar una computadora.
• "(L.1) (Localidad) Una computadora puede cambiar sólo elementos de una configuración simbólica observada.
• "(L.2) (Localidad) Un computador 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 inmediatamente anterior observada.
• "(D) (Determinación) La (sub)configuración inmediatamente reconocible determina de manera única el siguiente paso de cálculo (y la identificación [descripción instantánea])"; dicho de otra manera: "El estado interno de un computador junto con la configuración observada fija de manera única el siguiente paso de cálculo y el siguiente estado interno". ^[45]

El asunto sigue siendo objeto de debate activo dentro de la comunidad académica. ^{[46] [47]}

La tesis como definición

La tesis puede ser vista como nada más que 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 más allá de cualquier duda por Turing". ^[48] El caso para ver la tesis como nada más que una definición es presentado explícitamente por Robert I. Soare , ^[5] donde también se argumenta que la definición de computabilidad de Turing no tiene menos probabilidades 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 " contables en el sistema S ₁ " de Kurt Gödel 1936, y los " sistemas canónicos [también llamados normales ] " de Emil Post (1943, 1946) . ^[49] En la década de 1950, Hao Wang y Martin Davis simplificaron en gran medida el modelo de máquina de Turing de una cinta (véase máquina post-Turing ). Marvin Minsky amplió el modelo a dos o más cintas y simplificó en gran medida las cintas en "contadores arriba-abajo", 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 primo 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): "... sólo querían... convencerse de que no hay forma de ampliar la noción de función computable". ^[50]

Todas estas contribuciones implican pruebas de que los modelos son computacionalmente equivalentes a la máquina de Turing; se dice que dichos 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 ₁ ":

También se puede demostrar que una función que es computable ['contable'] en uno de los sistemas S _i , o incluso en un sistema de tipo transfinito, ya es computable [contable] en S ₁ . Así, el concepto 'computable' ['contable'] es en cierto sentido definido 'absoluto', mientras que prácticamente todos los demás conceptos metamatemáticos familiares (por ejemplo, demostrable, definible, etc.) dependen de manera bastante esencial del sistema para el que están definidos... ^[51]

Uso informal en pruebas

Las pruebas en la teoría de la computabilidad a menudo invocan la tesis de Church-Turing de manera informal para establecer la computabilidad de funciones, evitando al mismo tiempo los detalles (a menudo muy largos) que estarían involucrados en una prueba formal rigurosa. ^[52] Para establecer que una función es computable por la máquina de Turing, generalmente se considera suficiente dar una descripción informal en inglés de cómo se puede calcular efectivamente la función y luego concluir "según la tesis de Church-Turing" que la función es computable según el método de Turing (equivalentemente, parcialmente recursiva).

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

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

Demostración: Sea A un RE infinito. Enumeramos los elementos de A de manera efectiva, n ₀ , n ₁ , n ₂ , n ₃ , ...

De esta lista extraemos una sublista creciente: ponemos m ₀  = n ₀ , después de un número finito de pasos encontramos un n _k tal que n _k > m ₀ , ponemos m ₁  = n _k . Repetimos este procedimiento para encontrar m ₂ > m ₁ , etc. esto produce un listado efectivo del subconjunto B={m ₀ , m ₁ , m ₂ ,...} de A, con la propiedad m _i < m _i+1 .

Afirmación . B es decidible. Para comprobar k en B debemos comprobar si k = m _i para algún i. Puesto que la secuencia de m _i es creciente, tenemos que producir como máximo k+1 elementos de la lista y compararlos con k. Si ninguno de ellos es igual a k, entonces k no está en B. Puesto que esta prueba es eficaz, B es decidible y, según la tesis de Church , recursiva.

Para que el ejemplo anterior fuera completamente riguroso, habría que construir cuidadosamente una máquina de Turing, o una función λ, o invocar cuidadosamente axiomas de recursión, o en el mejor de los casos, invocar hábilmente varios teoremas de la teoría de la computabilidad. Pero como el teórico de la computabilidad cree que la computabilidad de Turing captura correctamente lo que se puede calcular de manera efectiva, y como se explica en inglés un procedimiento efectivo para decidir 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 dio lugar a la propuesta de variantes de la misma. Por ejemplo, la tesis física de Church-Turing afirma: "Todas las funciones físicamente computables son computables mediante el método de Turing". ^{[54] : 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 (multicinta) solo sufre un factor de desaceleración logarítmico al simular cualquier máquina de Turing. ^[55]

Una variación de la tesis de Church-Turing aborda si un modelo arbitrario pero "razonable" de computación puede ser simulado eficientemente. Esto se llama la tesis de viabilidad , ^[56] también conocida como la tesis de Church-Turing de la teoría de la complejidad ( clásica ) o la tesis de Church-Turing extendida , que no se debe a Church o Turing, sino que se realizó gradualmente en el desarrollo de la teoría de la complejidad . Afirma: ^[57] "Una máquina de Turing probabilística puede simular eficientemente cualquier modelo realista de computación". La palabra "eficientemente" aquí significa hasta reducciones de tiempo polinomial . Esta tesis fue llamada originalmente 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, entonces, postula que todos los modelos "razonables" de computación producen la misma clase de problemas que pueden ser calculados 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 teoría de la complejidad. Una tesis similar, llamada tesis de la invariancia , fue introducida por Cees F. Slot y Peter van Emde Boas. Establece: " Las máquinas 'razonables' pueden simularse entre sí dentro de una sobrecarga polinomialmente limitada en el tiempo y una sobrecarga de factor constante en el espacio". ^[58] La tesis apareció originalmente en un artículo en STOC '84, que fue el primer artículo en demostrar que la sobrecarga de tiempo polinomial y la sobrecarga de espacio constante se podían lograr simultáneamente para una simulación de una máquina de acceso aleatorio en una máquina de Turing. ^[59]

Si se demuestra que BQP es un superconjunto estricto de BPP , invalidaría la tesis de Church-Turing de teoría de la complejidad. En otras palabras, habría algoritmos cuánticos eficientes que realizan tareas que no tienen 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 invalidaría la tesis clásica de Church-Turing de teoría de la complejidad por razones de eficiencia. En consecuencia, la tesis de Church-Turing de teoría de la complejidad cuántica establece: ^[57] "Una máquina de Turing cuántica puede simular eficientemente cualquier modelo realista de computación".

Eugene Eberbach y Peter Wegner afirman que la tesis de Church-Turing a veces se interpreta de forma demasiado amplia, afirmando que "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 calcular no es válida". ^[60] Afirman que las formas de computación no capturadas por la tesis son relevantes hoy en día, términos que ellos llaman computación super-Turing .

Implicaciones filosóficas

Los filósofos han interpretado la tesis de Church-Turing como algo que tiene implicaciones para la filosofía de la mente . ^{[61] [62] [63]} B. Jack Copeland afirma que es una cuestión empírica abierta si existen procesos físicos deterministas reales que, a largo plazo, eluden la simulación por una máquina de Turing; además, afirma que es una cuestión empírica abierta si tales procesos están involucrados en el funcionamiento del cerebro humano. ^[64] También hay algunas cuestiones abiertas importantes que cubren la relación entre la tesis de Church-Turing y la física, y la posibilidad de 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 ha denominado la tesis fuerte de Church-Turing o principio de Church-Turing-Deutsch , y es uno de los fundamentos 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 mediante el método 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 oposición a 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 pregunta abierta si todos los eventos mecánicos cuánticos son computables por el método 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 términos de 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 por la mecánica cuántica. ^{[65] [66]}

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

Los aspectos filosóficos de la tesis, tanto en relación con las computadoras físicas como biológicas, también se analizan en el libro de texto de Odifreddi de 1989 sobre la teoría de la recursión. ^{[67] : 101–123}

Funciones no computables

Se pueden definir formalmente funciones que no sean computables. Un ejemplo bien conocido de este tipo de función es la función Busy Beaver . Esta función toma 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 un límite superior para la función Busy Beaver es equivalente a resolver el problema de la detención , un problema que se sabe que no puede resolverse con máquinas de Turing. Dado que la función Busy Beaver no puede ser calculada por máquinas de Turing, la tesis de Church-Turing afirma que esta función no puede ser calculada de manera efectiva por ningún método.

Varios modelos computacionales permiten el cálculo de funciones no computables (de Church-Turing). Estas se conocen como hipercomputadoras . Mark Burgin sostiene que los algoritmos superrecursivos, como las máquinas de Turing inductivas, refutan la tesis de Church-Turing. ^{[68] [ página requerida ]} 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, discutida anteriormente. El argumento de que los algoritmos superrecursivos son de hecho algoritmos en el sentido de la tesis de Church-Turing no ha encontrado una amplia aceptación dentro de la comunidad de investigación de la computabilidad. ^{[ cita requerida ]}

Véase también

• Máquina abstracta
• La tesis de Church sobre las matemáticas constructivas
• Principio de Church-Turing-Deutsch , que establece que todo proceso físico puede ser simulado por un dispositivo informático universal.
• Lógica de computabilidad
• Teoría de la computabilidad
• Decidibilidad
• Hipercomputación
• Modelo de cálculo
• Oracle (informática)
• Algoritmo superrecursivo
• Completitud de Turing

Notas al pie

1. Robert Soare , "Máquinas Oracle de Turing, computación en línea y tres desplazamientos en la teoría de la computabilidad"
2. Rabin, Michael O. (junio de 2012). Turing, Church, Gödel, computabilidad, complejidad y aleatorización: una visión personal. El evento ocurre a las 9:36 . Consultado el 5 de diciembre de 2021 .
3. Correspondencia entre Max Newman y Church en los documentos de Alonzo Church
4. Turing, Alan (2004). El Turing esencial: escritos fundamentales sobre informática, lógica, filosofía, inteligencia artificial y vida artificial, además de los secretos de Enigma (PDF) . Oxford: Clarendon Press. pág. 44. ISBN. 9780198250791. Recuperado el 6 de diciembre de 2021 .
5. 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. 
6. El artículo de Church fue presentado a la American Mathematical Society el 19 de abril de 1935 y publicado el 15 de abril de 1936. Turing, que había hecho un progreso sustancial en la redacción de sus propios resultados, se sintió decepcionado al enterarse de la prueba de Church tras su publicación. ^{[3] [4]} Turing completó rápidamente su artículo y se apresuró a publicarlo; fue recibido por las Actas de la London Mathematical Society el 28 de mayo de 1936, leído el 12 de noviembre de 1936 y publicado en la serie 2, volumen 42 (1936-1937); 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), pp. 544-546. ^{[5] : 45}
7. Iglesia 1936a
8. Kleene 1936
9. Turing 1937a
10. Kleene 1936
11. Turing 1937b. Esquema de la prueba en la pág. 153: ^[10] ${\displaystyle \lambda {\mbox{-definable}}}$ ${\displaystyle {\stackrel {triv}{\implies }}}$ ${\displaystyle \lambda {\mbox{-}}K{\mbox{-definable}}}$ ${\displaystyle {\stackrel {160}{\implies }}}$ ${\displaystyle {\mbox{Turing computable}}}$ ${\displaystyle {\stackrel {161}{\implies }}}$ ${\displaystyle \mu {\mbox{-recursive}}}$ ${\displaystyle {\stackrel {Kleene}{\implies }}}$ ${\displaystyle \lambda {\mbox{-definable}}}$
12. Rosser 1939 en Davis 1965:225.
13. "eficaz". Diccionario colegial de Merriam Webster (novena edición).
14. Véase también "efectivo". Diccionario en línea Merriam-Webster (11.ª ed.) . Consultado el 26 de julio de 2014 .que también da estas definiciones para "eficaz" – la primera ["que produce un efecto decidido, decisivo o deseado"] como la definición para el sentido "1a" de la palabra "eficaz", y la segunda ["capaz de producir un resultado"] como parte de la "Discusión de sinónimos de EFECTIVO" allí, (en la parte introductoria, donde resume las similitudes entre los significados de las palabras "eficaz", "eficaz", "eficiente" y "eficaz").
15. Turing, AM (1938). Sistemas de lógica basados ​​en ordinales (PDF) (PhD). Universidad de Princeton. p. 8. Archivado desde el original (PDF) el 23 de octubre de 2012. Consultado el 23 de junio de 2012 .
16. (1980:123) lo expresa de esta manera: Lo que es efectivamente calculable es computable. A esto lo llama "la tesis de Church".
17. David Hilbert y Wilhelm Ackermann: Grundzüge der theoretischen Logik, Berlín, Alemania, Springer, 1ª ed. 1928. (6.a ed. 1972, ISBN 3-540-05843-5 ) Traducción al inglés: David Hilbert y Wilhelm Ackermann: Principios de lógica matemática, AMS Chelsea Publishing, Providence, Rhode Island, EE. UU., 1950. 
18. Comentario de Davis antes de Church 1936 Un problema insoluble de la teoría elemental de números en Davis 1965:88. Church utiliza las palabras "calculabilidad efectiva" en la página 100 y siguientes.
19. En su reseña de Church's Thesis after 70 Years editada por Adam Olszewski et al. 2006, la crítica de Peter Smith a un artículo de Muraswski y Wolenski sugiere cuatro "líneas" con respecto al estatus de la tesis de 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), cf. Smith (11 de julio de 2007) Church's Thesis after 70 Years en http://www.logicmatters.net/resources/pdfs/CTT.pdf
20. cf. nota al pie 3 en Church 1936a Un problema irresoluble de la teoría de números elemental en Davis 1965:89.
21. Dawson 1997:99.
22. Sieg 1997:160.
23. Sieg 1997:160 citando la carta de 1935 escrita por Church a Kleene, cf. Nota al pie 3 en Gödel 1934 en Davis 1965:44.
24. cf. Iglesia 1936 en Davis 1965:105ff..
25. Comentario de Davis antes de Gödel 1934 en Davis 1965:40.
26. Para una discusión detallada 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) . Church's Thesis After 70 Years . De Gruyter. doi :10.1515/9783110325461.393. ISBN . 978-3-11-032494-5Archivado desde el original (PDF) el 17 de diciembre de 2015. Consultado el 8 de febrero de 2016 .
27. Turing 1937a.
28. cf. Nota al pie del editor de Post 1936 Finite Combinatory Process. Formulation I. en Davis 1965:289.
29. Después de 1936 en Davis 1965:291, nota al pie 8.
30. Después de 1936 en Davis 1952:291.
31. Sieg 1997:171 y 176-177.
32. Turing 1936–1937 en Davis 1965:263ff.
33. Iglesia 1937.
34. Turing 1939 en Davis:160.
35. cf. Church 1934 en Davis 1965:100, también Turing 1939 en Davis 1965:160.
36. cursiva añadida, Rosser 1939 en Davis 1965:226.
37. Kleene 1943, p. 60 en Davis 1965:274. Se omiten las notas a pie de página.
38. Kleene 1952:300.
39. Kleene 1952:376.
40. Kleene 1952:382, 536
41. Gandy 1980:123 y siguientes.
42. Gandy 1980:135
43. Gandy 1980:126
44. Sieg 1998-1999 en Sieg, Sommer y Talcott 2002: 390 y siguientes; también Sieg 1997:154 y siguientes.
45. En una nota a pie de página, Sieg divide la (B) de Post de 1936 en (B.1) y (B.2) y (L) en (L.1) y (L.2) y describe (D) de forma diferente. Con respecto a su propuesta de máquina de Gandy, más tarde añade LC.1, LC.2, GA.1 y GA.2. Estas son complicadas; véase Sieg 1998–1999 en Sieg, Sommer & Talcott 2002:390ff..
46. Se puede encontrar una colección de artículos en Olszewski, Woleński & Janusz (2006). También una reseña de esta colección: Smith, Peter (2007-07-11). "La tesis de Church después de 70 años" (PDF) .
47. Véase también Hodges, Andrew (2005). «¿Tenían Church y Turing una tesis sobre las máquinas?» (PDF) . Archivado desde el original (PDF) el 4 de marzo de 2016. Consultado el 27 de julio de 2014 .
48. Gödel, Kurt (1995) [193?]. "Proposiciones diofánticas indecidibles". En Feferman, Solomon (ed.). Obras completas. Vol. 3. Nueva York: Oxford University Press . p. 168. ISBN 978-0-19-507255-6. OCLC  928791907.
49. Kleene 1952:320
50. Gurevich 1988:2
51. Traducción de Gödel (1936) por Davis en The Undecidable p. 83, que difiere en el uso de la palabra 'contable' en la traducción en Kleene (1952) p. 321
52. Horsten en Olszewski, Woleński y Janusz 2006:256.
53. Gabbay 2001:284
54. Piccinini, Gualtiero (enero de 2007). "Computacionalismo, la tesis de Church-Turing y la falacia de Church-Turing" (PDF) . Synthese . 154 (1): 97–120. CiteSeerX 10.1.1.360.9796 . doi :10.1007/s11229-005-0194-z. S2CID  494161. Archivado (PDF) desde el original el 24 de abril de 2008. 
55. 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 cuerdas y la máquina universal de Turing" y 1.7, "Demostración del teorema 1.9".
56. "Descripción oficial del problema" (PDF) . Archivado desde el original (PDF) el 24 de noviembre de 2005.
57. 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.
58. van Emde Boas, Peter (1990). "Modelos de máquinas y simulaciones". Manual de informática teórica A . Elsevier . pág. 5.
59. Slot, C.; van Emde Boas, P. (diciembre de 1984). Sobre cinta versus núcleo: una aplicación de funciones hash perfectas y eficientes en el uso del espacio a la invariancia del espacio . STOC .
60. Eberbach y Wegner 2003, pág. 287.
61. Abramson, Darren (2011). "La filosofía de la mente es (en parte) filosofía de la informática". Mentes y máquinas . 21 (2): 203–219. doi :10.1007/s11023-011-9236-0. S2CID  32116031.
62. Copeland, B. Jack (10 de noviembre de 2017). "La tesis de Church-Turing". En Zalta, Edward N. (ed.). Stanford Encyclopedia of Philosophy .
63. Para encontrar un buen lugar donde encontrar 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-6.OCLC 610918145  .
64. Copeland, B. Jack (2004). "Computación". En Floridi, Luciano (ed.). La guía Blackwell para la filosofía de la computación y la información . Wiley-Blackwell. pág. 15. ISBN 978-0-631-22919-3.
65. cf. Penrose, Roger (1990). "Algoritmos y máquinas de Turing". La nueva mente del emperador: sobre ordenadores, mentes y leyes de la física . Oxford: Oxford University Press. pp. 47–49. ISBN 978-0-19-851973-7.OCLC 456785846  .
66. También la descripción de "la naturaleza no algorítmica de la percepción matemática", Penrose, Roger (1990). "¿Dónde se encuentra 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. pp. 416–418. ISBN. 978-0-19-851973-7.OCLC 456785846  .
67. Piergiorgio Odifreddi (1989). Teoría de la recursión clásica . Estudios de lógica y fundamentos de las matemáticas. Vol. 125. Ámsterdam, Países Bajos: Holanda Septentrional.
68. Burgin, Mark (2005). Algoritmos superrecursivos . Monografías en informática. Nueva York: Springer. ISBN 978-0-387-95569-8.OCLC 990755791  .

Referencias

• Barwise, Jon ; Keisler, HJ ; Kunen, Kenneth , eds. (1980). El simposio de 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 desde el original (PS) el 2017-07-06 . Consultado el 2017-10-24 .
• 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: una búsqueda de definiciones absolutas" (PDF) . Boletín de la Asociación Europea de Ciencias Informáticas Teóricas (81). Archivado (PDF) desde el original el 27 de julio de 2004.^{[ página necesaria ]}
• 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 insoluble 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 desde el original (PDF) el 27 de febrero de 2020.
• Church, Alonzo (junio de 1936b). "Una nota sobre el problema de la entscheidung". 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, On Computable Numbers, con una aplicación al problema de Entscheidung". Revista de lógica simbólica . 2 (1): 42–43. doi :10.2307/2268810. JSTOR  2268810.
• Church, Alonzo (1941). Los cálculos de 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 desde Oriente y Occidente . Kluwer Academic/Plenum Publishers. págs. 137–160.
• Davis, Martin , ed. (1965). Lo indecidible, Documentos 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.
• Dawson, John W. Jr. (1997). Dilemas lógicos: La vida y obra de Kurt Gödel . Wellesley, Massachusetts, EE. UU.: AK Peters .
• Eberbach, E.; Wegner, P. (octubre de 2003). "Más allá de las máquinas de Turing" (PDF) . Boletín de la Asociación Europea de Ciencias Informáticas Teóricas (81): 279–304. CiteSeerX  10.1.1.61.9759 . Archivado (PDF) desde el original el 15 de marzo de 2016.
• Gabbay, DM (2001). Manual de lógica filosófica . Vol. 1 (2.ª ed.).
• Gandy, Robin (1980). "La tesis de Church y los principios de los mecanismos". En H. J. Barwise; H. J. Keisler; K. Kunen (eds.). El simposio de Kleene . North-Holland Publishing Company. págs. 123–148.
• Gandy, Robin (1994). Herken, Rolf (ed.). La máquina de Turing universal: una encuesta de medio siglo . Nueva York: Wien Springer–Verlag. págs. 51 y siguientes. ISBN 978-3-211-82637-9.
• Gödel, Kurt (1965) [1934]. "Sobre proposiciones indecidibles de sistemas matemáticos formales". En Davis, Martin (ed.). The Undecidable . Kleene y Rosser (tomadores de notas de la conferencia); Institute for Advanced Study (patrocinador de la conferencia). Nueva York: Raven Press.
• Gödel, Kurt (1936). "Über die Lāange von Beweisen" [Sobre la duración de las pruebas]. Ergenbnisse Eines Mathematishen Kolloquiums (en alemán) (7). Peso: 23-24.Citado por Kleene (1952).
• Gurevich, Yuri (junio de 1988). "Sobre las máquinas de Kolmogorov y cuestiones relacionadas". Boletín de la Asociación Europea de Ciencias Informáticas Teóricas (35): 71–82.
• Gurevich, Yuri (julio de 2000). "Máquinas de estados abstractos secuenciales capturan algoritmos secuenciales" (PDF) . ACM Transactions on Computational Logic . 1 (1): 77–111. CiteSeerX  10.1.1.146.3017 . doi :10.1145/343369.343384. S2CID  2031696. Archivado (PDF) desde el original el 16 de octubre de 2003.
• Herbrand, Jacques (1932). "Sobre la no contradicción de la aritmética". Journal für die Reine und Angewandte Mathematik (en francés). 166 : 1–8. doi :10.1515/crll.1932.166.1. S2CID  116636410.
• Hofstadter, Douglas R. "Capítulo XVII: Church, Turing, Tarski y otros". Gödel, Escher, Bach: una eterna trenza dorada (edición del vigésimo aniversario). Basic Books . págs. 559–585. ISBN 0-465-02656-7.
• Kleene, Stephen Cole (enero de 1935). "Una teoría de los números enteros positivos en la lógica formal". American Journal of Mathematics . 57 (1): 153–173 y 219–244. doi :10.2307/2372027. JSTOR  2372027.
• Kleene, Stephen Cole (1936). "Definibilidad Lambda y recursividad". Duke Mathematical Journal . 2 (2): 340–353. doi :10.1215/s0012-7094-36-00227-2.
• Kleene, Stephen Cole (1943). "Predicados recursivos y cuantificadores". Transacciones de la American Mathematical Society . 53 (1): 41–73. doi : 10.2307/1990131 . JSTOR  1990131.Reimpreso en The Undecidable, pág. 255ff. Kleene refinó su definición de "recursión general" y procedió en su capítulo "12. Teorías algorítmicas" a postular la "Tesis I" (pág. 274); más tarde repetiría esta tesis (en Kleene 1952:300) y la llamaría "Tesis de Church" (Kleene 1952:317) (es decir, la tesis de Church ).
• Kleene, Stephen Cole (1952). Introducción a las metamatemáticas . Holanda Septentrional. OCLC  523942.
• Knuth, Donald (1973). El arte de la programación informática . Vol. 1/Algoritmos fundamentales (2.ª ed.). Addison–Wesley.
• Kugel, Peter (noviembre de 2005). "Es hora de pensar más allá de la caja computacional". Comunicaciones de la ACM . 48 (11): 32–37. CiteSeerX  10.1.1.137.6939 . doi :10.1145/1096000.1096001. S2CID  29843806.
• Lewis, HR ; Papadimitriou, CH (1998). Elementos de la teoría de la computación . Upper Saddle River, Nueva Jersey, EE. UU.: Prentice-Hall.
• Manna, Zohar (2003) [1974]. Teoría matemática de la computación . Dover. ISBN 978-0-486-43238-0.{{cite book}}: CS1 maint: location missing publisher (link)
• Markov, AA (1960) [1954]. "La teoría de los algoritmos". Traducciones de la American Mathematical Society . 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-1.OCLC 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 pruebas del teorema de Gödel y del teorema de Church". Revista de lógica simbólica . 4 (2): 53–60. doi :10.2307/2269059. JSTOR  2269059. S2CID  39499392.
• Sieg, Wilfried; Sommer, Richard; Talcott, Carolyn, eds. (2002). Reflexiones sobre los fundamentos de las matemáticas: ensayos en honor a Solomon Feferman . Apuntes de clase sobre lógica. Vol. 15. AK Peters, Ltd. ISBN 978-1-56881-169-7.
• Syropoulos, Apostolos (2008). Hipercomputación: computación más allá de la barrera de Church-Turing . Springer. ISBN 978-0-387-30886-9.
• Turing, AM (1937a) [Entregado a la Sociedad en noviembre de 1936], "Sobre números computables, con una aplicación al problema de Entscheidung" (PDF) , Actas de la London Mathematical Society , 2, vol. 42, págs. 230–265, doi :10.1112/plms/s2-42.1.230, S2CID  73712y Turing, AM (1938). "Sobre números computables, con una aplicación al problema de Entscheidung: una corrección". Actas de la London Mathematical Society . 2. Vol. 43 (publicado en 1937). págs. 544–546. doi :10.1112/plms/s2-43.6.544.(Véase también: Davis 1965:115ff.)
• Turing, Alan Mathison (diciembre de 1937b). "Computabilidad y λ-definabilidad" (PDF) . Journal of Symbolic Logic . 2 (4): 153–163. doi :10.2307/2268280. JSTOR  2268280. S2CID  2317046. Archivado desde el original (PDF) el 2020-08-09.

Enlaces externos

• Entrada de B. Jack Copeland sobre "La tesis de Church-Turing" en la Enciclopedia de Filosofía de Stanford .
• Entrada de Gualtiero Piccinini sobre "Computación en sistemas físicos" en la Enciclopedia de Filosofía de Stanford : un tratamiento filosófico exhaustivo de cuestiones relevantes.
• Kaznatcheev, Artem (11 de septiembre de 2014). "Idealismo trascendental y la variante de Post de la tesis de Church-Turing". Revista de lógica simbólica . 1 (3): 103–105.
• Un número especial (Vol. 28, No. 4, 1987) del Notre Dame Journal of Formal Logic estuvo dedicado a la tesis de Church-Turing.