Tesis de Church-Turing

En la teoría de la computabilidad, la tesis de Church-Turing (también conocida como tesis de computabilidad, la tesis de Turing-Church, la 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 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 el matemático británico Alan Turing. Antes de la definición precisa de función computable, los matemáticos a menudo usaban el término informal efectivamente calculable para describir funciones que son computables por métodos de papel y lápiz. En la década de 1930, se realizaron varios intentos independientes para formalizar la noción de computabilidad:

• En 1933, Kurt Gödel, con Jacques Herbrand, formalizó la definición de la clase de funciones recursivas generales: la clase más pequeña de funciones (con arbitrariedad muchos argumentos) que se cierra bajo composición, recursión y minimización, e incluye cero, sucesor, y todas las proyecciones.
• En 1936, la Iglesia de Alonzo creó un método para definir funciones llamadas el λ-calculus. Dentro de λ-calculus, definió una codificación de los números naturales llamados los numerales de la Iglesia. Una función sobre los números naturales se llama λ-computable si la función correspondiente en los numerales de la Iglesia puede ser representada por un término del λ-calculus.
• También en 1936, antes de aprender de la obra de la Iglesia, Alan Turing creó un modelo teórico para máquinas, ahora llamadas máquinas Turing, que podrían llevar a cabo cálculos 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 en los números naturales se llama Turing computable si alguna máquina Turing calcula la función correspondiente en los números naturales codificados.

Church, Kleene y Turing demostraron que estas tres clases formalmente definidas de funciones computables coinciden: una función es computable en λ si y solo si es computable por Turing, 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 por estos tres procesos equivalentes. Otros intentos formales de caracterizar la computabilidad han fortalecido posteriormente esta creencia (ver más abajo).

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

Desde sus inicios, han surgido variaciones de la tesis original, incluidas afirmaciones sobre lo que una computadora puede realizar físicamente en nuestro universo (tesis física de Church-Turing) y lo que se puede calcular de manera eficiente (tesis de Church-Turing (teoría de la complejidad)). Estas variaciones no se deben a Church ni a Turing, sino que surgen de trabajos posteriores en teoría de la complejidad y física digital. La tesis también tiene implicaciones para la filosofía de la mente (ver más abajo).

Declaración en palabras de Church y Turing

J. B. Rosser (1939) aborda la noción de "computabilidad efectiva" como sigue: "Claramente, la existencia de CC y RC (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 con seguridad producirá la respuesta en un número finito de pasos. Así, el adverbio-adjetivo "efectivo" se usa en el sentido de "1a: producir un efecto decidido, decisivo o deseado" y "capaz de producir un resultado".

A continuación, las palabras "efectivamente calculable" significará "producido por cualquier intuitivamente 'efectivo' significa cualquier cosa" y "efectivamente computable" significará "producido por una máquina de Turing o dispositivo mecánico equivalente". Las 'definiciones' de Turing dado en una nota a pie de página en su Ph.D. de 1938. La tesis Sistemas de lógica basada en ordinales, supervisada por Church, son prácticamente iguales:

^† Usaremos la expresión "función computarable" para significar una función calculable por una máquina, y dejemos "eficazmente calculable" referirse a la idea intuitiva sin identificación particular con cualquiera de estas definiciones.

La tesis puede enunciarse como: Toda función efectivamente calculable es una función computable. Church también afirmó que "Ningún procedimiento computacional será considerado como un algoritmo a menos que pueda representarse como una máquina de Turing". Turing lo expresó así:

Se dijo... que "una función es efectivamente calculable si sus valores pueden ser encontrados por algún proceso puramente mecánico". Podemos tomar esto literalmente, entendiendo que por un proceso puramente mecánico 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 de pie de página citada anteriormente.]

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, que preguntaba 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" ser inmovilizado, al menos lo suficientemente bien como para que comience la búsqueda. Pero desde el principio, los intentos de Alonzo Church comenzaron con un debate que continúa hasta el día de hoy. Era la noción de &# 34;calculabilidad efectiva" ser (i) un "axioma o axiomas" en un sistema axiomático, (ii) simplemente una definición que "identifica" dos o más proposiciones, (iii) una hipótesis empírica para ser verificada mediante la observación de eventos naturales, o (iv) simplemente una propuesta por el bien del argumento (es decir, un & #34;tesis").

Alrededor de 1930–1952

En el transcurso del estudio del problema, Church y su alumno Stephen Kleene introdujeron la noción de funciones definibles por λ y pudieron demostrar que varias clases grandes de funciones que se encuentran con frecuencia en la teoría de números eran definibles por λ. El debate comenzó cuando Church le propuso a Gödel que se definiera lo "efectivamente computable" funciones como las funciones definibles en λ. Gödel, sin embargo, no estaba convencido y calificó la propuesta de 'totalmente insatisfactoria'. 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:

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

Pero Gödel no ofreció más orientación. Eventualmente, sugeriría su recursividad, modificada por la sugerencia de Herbrand, que Gödel había detallado en sus conferencias de 1934 en Princeton NJ (Kleene y Rosser transcribieron las notas). Pero no creía que las dos ideas pudieran identificarse satisfactoriamente 'excepto heurísticamente'.

A continuación, era necesario identificar y probar la equivalencia de dos nociones de calculabilidad efectiva. Equipado con cálculo λ y "general" recursividad, Kleene con la ayuda de Church y J. Barkley Rosser produjeron pruebas (1933, 1935) para mostrar que los dos cálculos son equivalentes. Posteriormente, Church modificó sus métodos para incluir el uso de la recursividad de Herbrand-Gödel y luego demostró (1936) que el Entscheidungsproblem no tiene solución: no existe ningún algoritmo que pueda determinar si una fórmula bien formada tiene una forma beta normal.

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

¿Una hipótesis que conduzca a una ley natural?: A fines de 1936, el artículo de Alan Turing (que también prueba que el Entscheidungsproblem no tiene solución) se entregó oralmente, pero aún no había aparecido impreso. Por otro lado, el artículo de 1936 de Emil Post había aparecido y fue certificado como independiente del trabajo de Turing. Post no estuvo de acuerdo con la 'identificación' de Church. de computabilidad efectiva con el cálculo de λ y la recursividad, planteando:

En realidad el trabajo ya realizado por la Iglesia y otros lleva esta identificación considerablemente más allá de la etapa de hipótesis de trabajo. Pero para ocultar esta identificación bajo una definición... nos ciega a la necesidad de su continua verificación.

Más bien, consideró la noción de "calculabilidad efectiva" como meramente una "hipótesis de trabajo" que podría conducir por razonamiento inductivo a una "ley natural" en lugar de por "una definición o un axioma". Esta idea fue "agudamente" criticado por la Iglesia.

Así, en su artículo de 1936, Post 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.

Turing añade otra definición, Rosser equipara las tres: en poco tiempo, el artículo de Turing de 1936-1937 "Sobre números computables, con una aplicación al problema Entscheidungs' 34; apareció. 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). Y en un boceto de prueba agregado como "Apéndice" En su artículo de 1936-1937, Turing mostró que las clases de funciones definidas por el cálculo λ y las máquinas de Turing coincidían. Church reconoció rápidamente lo convincente que era el análisis de Turing. En su revisión del artículo de Turing, dejó claro que la noción de Turing hacía evidente de inmediato "la identificación con la eficacia en el sentido ordinario (no definido explícitamente)".

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

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

Los tres definiciones son equivalentes, por lo que no importa cuál es usado.

Kleene propone Tesis I: Esto dejó la expresión abierta de una "tesis" a Kleene. En 1943, Kleene propuso su "Tesis I":

Este hecho heurístico [las funciones recursivas generales son efectivamente calculables]... llevó a la Iglesia a declarar la tesis siguiente. La misma tesis es implícita en la descripción de Turing de máquinas informáticas.

Tesis I. Cada función eficientemente calculable (predeterminado eficazmente decidable) es recurrente general [Kleene's italics]

Puesto que una definición matemática precisa del término efectivamente calculable (eficazmente decidable) ha estado deseando, podemos tomar esta tesis... como una definición de ella...

...la tesis tiene el carácter de una hipótesis—un punto enfatizado por Post y por la Iglesia. Si consideramos la tesis y su contrario como 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, hay, como hemos sugerido, motivos 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 'La tesis de Turing', utilizando su teoría de la realizabilidad recursiva. Kleene pasó de presentar su trabajo en la terminología de la definibilidad lambda de Church-Kleene, a la de la 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 E. J. Brouwer. En su libro de texto de posgrado sobre lógica, "Tesis de Church" se introduce 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 no son computables, utilizando su derivación simplificada de una máquina de Turing basada en el trabajo de Emil Post. Se demuestra que ambas tesis son equivalentes mediante el uso del "Teorema XXX".

Tesis I. Cada función eficientemente calculable (predeterminado eficazmente decidable) es recurrente general.

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

Tesis de Turing: La tesis de Turing de que cada 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 la Iglesia por Teorema XXX.

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 los conceptos del artículo de Alan Turing "The Word Problem in Semi-Groups with Cancellation", tal y como exige una crítica de William Boone.

Desarrollos posteriores

Un intento de comprender la noción de "computabilidad efectiva" llevó mejor a Robin Gandy (estudiante y amigo de Turing) en 1980 a analizar la computación máquina (en contraposición a la computación humana representada por una máquina de Turing). La curiosidad y el análisis de Gandy sobre los autómatas celulares (incluido el juego de la vida de Conway), el paralelismo y los autómatas cristalinos lo llevaron a proponer cuatro "principios (o restricciones)... que se argumenta, cualquier máquina debe satisfacer". Su cuarto 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". 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) el progreso discreto de la máquina, y (3) comportamiento determinista: produce un teorema de que "lo que puede calcularse mediante un dispositivo que satisface los principios I-IV es computable".

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

• "(B.1) (Boundedness) Hay un límite fijo en el número de configuraciones simbólicas que un compositor puede reconocer inmediatamente.
• "(B.2) (Boundedness) Hay un límite fijo en el número de estados internos en los que un compositor puede estar.
• "(L.1) (Localidad) Un compositor puede cambiar sólo elementos de una configuración simbólica observada.
• "(L.2) (Localidad) Un compositor puede cambiar la atención de una configuración simbólica a otra, pero las nuevas configuraciones observadas deben estar a una distancia limitada de la configuración inmediatamente observada.
• "(D) (Determinacy) La inmediatamente reconocible (sub-)configuración determina singularmente el siguiente paso de cálculo (y id [descripción instantánea])"; declaró otra manera: "El estado interno de un computor junto con la configuración observada fija singularmente el próximo paso de cálculo y el siguiente estado interno".

El asunto permanece en discusión activa dentro de la comunidad académica.

La tesis como definición

La tesis puede verse como nada más que una definición matemática ordinaria. Los comentarios de Gödel sobre el tema sugieren este punto de vista, p. "la definición correcta de computabilidad mecánica fue establecida más allá de toda duda por Turing". El caso para ver la tesis como nada más que una definición lo hace explícitamente Robert I. Soare, donde también se argumenta que la definición de computabilidad de Turing no es menos probable que sea correcta que la definición épsilon-delta de un función continua.

Éxito de la tesis

Se han propuesto otros formalismos (además de la recursividad, el cálculo λ y la máquina de Turing) para describir la calculabilidad/computabilidad efectiva. Kleene (1952) añade a la lista las funciones "recontables en el sistema S₁" de Kurt Gödel 1936, y Emil Post's (1943, 1946) "canonical [también llamado normal] sistemas& #34;. En la década de 1950, Hao Wang y Martin Davis simplificaron enormemente el modelo de máquina de Turing de una cinta (ver máquina 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 evolucionaron aún más hasta convertirse en lo que ahora se conoce como el modelo de máquina contadora. A fines de la década de 1960 y principios de la de 1970, los investigadores expandieron el modelo de la máquina contadora a la máquina registradora, un primo cercano de la noción moderna de computadora. Otros modelos incluyen lógica combinatoria y algoritmos de Markov. Gurevich añade el modelo de máquina apuntadora de Kolmogorov y Uspensky (1953, 1958): "... solo querían... convencerse a sí mismos de que no hay manera de extender la noción de función computable."

Todas estas contribuciones involucran 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 arrojado resultados equivalentes, ahora se supone 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" sobre el concepto de "recontable en S₁":

También se puede demostrar que una función computable ['reckonable'] en uno de los sistemas S_i, o incluso en un sistema de tipo transfinito, ya es computable [reckonable] en S₁. Así el concepto 'computable' ['reckonable'] está en cierto sentido definido 'absoluto', mientras que prácticamente todos los demás conceptos metamatemáticos conocidos (por ejemplo, provable, definable, etc.) dependen esencialmente del sistema al que se definen...

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 las funciones y evitar los detalles (a menudo muy extensos) que estarían involucrados en una prueba formal y rigurosa. 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 "por la tesis de Church-Turing" que la función es computable por Turing (equivalentemente, recursiva parcial).

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

Ejemplo: Cada conjunto RE infinito contiene un conjunto recursivo infinito.

Prueba: Deja que una RE infinita. Listamos los elementos de A efectivamente, n₀, n₁, n₂, n₃,...

De esta lista extraemos una sublista creciente: poner m₀= n₀, después de finitamente muchos pasos que encontramos_k tal que n_k Ø m₀, poner m₁= n_k. Repetimos este procedimiento para encontrar m₂ Ø m₁, etc. esto produce una lista efectiva del subconjunto B={m₀, m₁, m₂Con la propiedad m_i *_i+1.

Reclamación. B es decidable. Para, para probar k en B debemos comprobar si k = m_i para algunos. Desde la secuencia de m_i's está aumentando tenemos que producir a la mayoría de los elementos k+1 de la lista y compararlos con k. Si ninguno de ellos es igual a k, entonces k no en B. Puesto que esta prueba es eficaz, B es decidable y, por la tesis de la Iglesia, recursivo.

Para hacer que el ejemplo anterior sea completamente riguroso, habría que construir cuidadosamente una máquina de Turing, o una función λ, o invocar cuidadosamente los axiomas de recurrencia o, en el mejor de los casos, invocar inteligentemente varios teoremas de la teoría de la computabilidad. Pero debido a que el teórico de la computabilidad cree que la computabilidad de Turing captura correctamente lo que se puede calcular de manera efectiva, y debido a que en inglés se explica un procedimiento efectivo para decidir el conjunto B, el teórico de la computabilidad acepta esto como prueba de que el conjunto es recursivo.

Variaciones

El éxito de la tesis de Church-Turing provocó que se propusieran variaciones de la tesis. Por ejemplo, la tesis física de Church-Turing establece: "Todas las funciones computables físicamente son computables por Turing."

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 ralentización logarítmica al simular cualquier máquina de Turing.

Una variación de la tesis de Church-Turing aborda si una decisión arbitraria pero "razonable" modelo de computación se puede simular de manera eficiente. Esto se llama la tesis de factibilidad, también conocida como la (clásica) tesis de Turing de la teoría de la complejidad o la Iglesia extendida– Tesis de Turing, que no se debe a Church ni a Turing, sino que se fue realizando gradualmente en el desarrollo de la teoría de la complejidad. Afirma: "Una máquina de Turing probabilística puede simular de manera eficiente cualquier modelo realista de computación". La palabra 'eficientemente' aquí significa hasta reducciones de tiempo polinomial. Esta tesis fue originalmente llamada tesis de Church-Turing teórica de la complejidad computacional por Ethan Bernstein y Umesh Vazirani (1997). La tesis de la teoría de la complejidad de Church-Turing, entonces, postula que todo lo 'razonable' los modelos de computación producen la misma clase de problemas que pueden calcularse en tiempo polinomial. Asumiendo la conjetura de que el tiempo polinomial probabilístico (BPP) es igual al tiempo polinomial determinista (P), la palabra 'probabilista' es opcional en la tesis de Church-Turing teórica de la complejidad. Cees F. Slot y Peter van Emde Boas introdujeron una tesis similar, denominada tesis de la invariancia. Dice: "'Razonable' las máquinas pueden simularse entre sí dentro de una sobrecarga acotada polinómicamente en el tiempo y una sobrecarga de factor constante en el espacio." La tesis apareció originalmente en un artículo en STOC'84, que fue el primer artículo en mostrar que la sobrecarga de tiempo polinomial y la sobrecarga de espacio constante podrían lograrse simultáneamente para una simulación de una máquina de acceso aleatorio en una máquina de Turing.

Si se demuestra que BQP es un superconjunto estricto de BPP, invalidaría la tesis de Church-Turing de la 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 máquina de Turing siempre puede simular una computadora cuántica, pero invalidaría la tesis clásica de teoría de la complejidad de Church-Turing por razones de eficiencia. En consecuencia, la tesis de Church-Turing teórica de la complejidad cuántica establece: "Una máquina cuántica de Turing puede simular de manera eficiente cualquier modelo realista de computación."

Eugene Eberbach y Peter Wegner afirman que la tesis de Church-Turing a veces se interpreta de manera demasiado amplia, afirmando "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". Afirman que las formas de computación no capturadas por la tesis son relevantes hoy, términos que ellos llaman computación de super-Turing.

Implicaciones filosóficas

Los filósofos han interpretado que la tesis de Church-Turing tiene implicaciones para la filosofía de la mente. B. Jack Copeland afirma que es una pregunta empírica abierta si existen procesos físicos deterministas reales que, a la larga, 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. También hay algunas preguntas abiertas importantes que cubren 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, computar funciones no recursivas es físicamente imposible. Esto ha sido denominado la fuerte Iglesia –Tesis de la prueba, o principio de la Iglesia–Turing–Deutsch, y es una fundación 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 compatibles con Turing), pero los eventos físicos incomputables no son "harnessable" para la construcción de un hipercomputador. Por ejemplo, un universo en el que la física involucra números reales aleatorios, a diferencia de los reales computables, caería en esta categoría.
3. El universo es un hipercomputador, 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 compatibles con Turing, aunque se sabe que modelos rigurosos como máquinas de Turing cuánticos son equivalentes a máquinas de Turing deterministas. (No son necesariamente equivalentes eficientemente; véase arriba). John Lucas y Roger Penrose han sugerido que la mente humana podría ser el resultado de algún tipo de computación cuántica-mecánicamente mejorada, "no-algorítmica".

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

Los aspectos filosóficos de la tesis, relacionados con las computadoras físicas y biológicas, también se analizan en el libro de texto de 1989 de Odifreddi sobre la teoría de la recursión.

Funciones no computables

Se pueden definir formalmente funciones que no son computables. Un ejemplo bien conocido de una función de este tipo es la función Busy Beaver. Esta función toma una entrada n y devuelve la mayor cantidad de símbolos que una máquina de Turing con estados n puede imprimir antes de detenerse, cuando se ejecuta sin entrada. Encontrar un límite superior en la función del castor ocupado es equivalente a resolver el problema de la detención, un problema que las máquinas de Turing saben que no tiene solución. Dado que las máquinas de Turing no pueden calcular la función del castor ocupado, la tesis de Church-Turing establece que esta función no se puede calcular de manera efectiva mediante ningún método.

Varios modelos computacionales permiten el cálculo de funciones no computables (Church-Turing). Estos son conocidos como hipercomputadoras. Mark Burgin argumenta que los algoritmos súper recursivos, como las máquinas inductivas de Turing, refutan la tesis de Church-Turing. Su argumento se basa en una definición de algoritmo más amplia que la ordinaria, por lo 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 súper recursivos 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 computabilidad.