De Wikipedia, la enciclopedia libre
Ir a navegaciónSaltar a buscar

En la teoría de la computabilidad , la tesis de Church-Turing (también conocida como tesis de computabilidad , [1] la tesis de Turing-Church , [2] la conjetura de Church-Turing , la tesis de Church , la conjetura de Church y la tesis de Turing ) es una hipótesis sobre la naturaleza de funciones computables . Establece que una función sobre los números naturales puede calcularse mediante un método eficaz si y solo si es calculable 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 a menudo usaban 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 hicieron 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 arbitrariamente muchos argumentos) que está cerrada bajo composición , recursividad 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 llamados los números de la Iglesia . Una función en los números naturales se llama λ-computable si la función correspondiente en los números de la Iglesia se puede representar mediante un término del cálculo λ.
  • También en 1936, antes de conocer el trabajo de Church, [ cita requerida ] Alan Turing creó un modelo teórico para máquinas, ahora llamado 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 de Turing si alguna máquina de Turing calcula la función correspondiente sobre los números naturales codificados.

Church, [3] Kleene, [4] y Turing [5] [7] demostraron que estas tres clases formalmente definidas de funciones computables coinciden: una función es λ-computable si y solo si es Turing computable, y si y solo si es recursivo general . Esto ha llevado a matemáticos e informáticos a creer que el concepto de computabilidad se caracteriza con precisión por estos tres procesos equivalentes. Otros intentos formales 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 de funciones computables definidas formalmente anteriormente coinciden con la noción informal de una función efectivamente calculable. Dado que, como noción informal, el concepto de calculabilidad efectiva no tiene una definición formal, la tesis, aunque tiene una aceptación casi universal, no puede ser probada formalmente.

Desde sus inicios, han surgido variaciones de la tesis original, incluidas declaraciones sobre lo que puede realizar físicamente una computadora en nuestro universo ( tesis física de Church-Turing ) y lo que puede calcularse de manera eficiente ( 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: "Claramente, la existencia de CC y RC (pruebas de Church y Rosser) presupone una definición precisa de" efectivo ". sentido de un método, cada paso del cual está predeterminado con precisión y que seguramente producirá la respuesta en un número finito de pasos ". [8] Así, el adverbio-adjetivo "eficaz" se utiliza en el sentido de "1a: producir un efecto decidido, decisivo o deseado", y "capaz de producir un resultado". [9] [10]

En lo que sigue, las palabras "efectivamente calculable" significarán "producido por cualquier medio intuitivo" efectivo "y" efectivamente computable "significará" producido por una máquina de Turing o dispositivo mecánico equivalente ". Las "definiciones" de Turing dadas en una nota a pie de página en su Ph.D. de 1938. Los sistemas de tesis de lógica basados ​​en ordinales , supervisados ​​por Church, son prácticamente los mismos:

† 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 identificación particular con ninguna de estas definiciones. [11]

La tesis puede enunciarse como: Toda función efectivamente calculable es una función computable . [12] Church también declaró que "Ningún procedimiento computacional será considerado como un algoritmo a menos que pueda ser representado como una Máquina de Turing". [ cita requerida ] Turing lo dijo de esta manera:

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

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 , [13] 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" se definiera, al menos lo suficientemente bien como para que la búsqueda comenzara. [14] Pero desde el principio , los intentos de Alonzo Church comenzaron con un debate que continúa hasta el día de hoy. [15] Fue [ aclarar ]la noción de "calculabilidad efectiva" es (i) un "axioma o axiomas" en un sistema axiomático, (ii) meramente una definición que "identifica" dos o más proposiciones, (iii) una hipótesis empírica que debe ser verificada mediante la observación de eventos naturales, o (iv) simplemente una propuesta por el bien de la argumentación (es decir, una "tesis").

Alrededor de 1930-1952

En el curso 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 λ. [16] El debate comenzó cuando Church propuso a Gödel que se deberían definir las funciones "efectivamente computables" como las funciones definibles por λ. Gödel, sin embargo, no estaba convencido y calificó la propuesta como "completamente insatisfactoria". [17] 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 indefinida, establecer un conjunto de axiomas que encarnarían las propiedades generalmente aceptadas de esta noción, y hacer algo sobre esa base. . [18]

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, Nueva Jersey (Kleene y Rosser transcribieron las notas). Pero no creía que las dos ideas pudieran identificarse satisfactoriamente "excepto de forma heurística". [19]

A continuación, fue necesario identificar y probar la equivalencia de dos nociones de calculabilidad efectiva. Equipado con el cálculo λ y la recursividad "general", Stephen Kleene con la ayuda de Church y J. Barkley Rosser produjo pruebas (1933, 1935) para mostrar que los dos cálculos son equivalentes. Church posteriormente modificó sus métodos para incluir el uso de la recursividad de Herbrand-Gödel y luego demostró (1936) que el problema de Entscheidungs es irresoluble: no existe un algoritmo que pueda determinar si una fórmula bien formada tiene una "forma normal". [ aclarar ] [20]

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

¿Una hipótesis que conduce a una ley natural? : A finales de 1936, el artículo de Alan Turing (que también demuestra que el problema de Entscheidungs es irresoluble) se presentó oralmente, pero aún no había aparecido impreso. [23] Por otro lado, el artículo de 1936 de Emil Post había aparecido y estaba certificado como independiente del trabajo de Turing. [24] Post estuvo en total desacuerdo con la "identificación" de Church de la computabilidad efectiva con el cálculo λ y la recursividad, 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 a la necesidad de su verificación continua. [25]

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

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. [18]

Turing añade otra definición, Rosser equipara las tres : En poco tiempo, apareció el artículo de Turing de 1936-1937 "Sobre números computables, con una aplicación al problema de Entscheidung" [23] . En él, afirmó 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 bosquejo de prueba agregado como "Apéndice" a 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. [28]Church se apresuró a reconocer lo convincente que era el análisis de Turing. En su revisión del artículo de Turing, dejó en claro que la noción de Turing hizo que "la identificación con la eficacia en el sentido ordinario (no definido explícitamente) fuera evidente de inmediato". [29]

En unos 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. [30] Así, en 1939, tanto Church (1934) como Turing (1939) habían propuesto individualmente que sus "sistemas formales" deberían ser definiciones de "calculabilidad efectiva"; [31] ninguno enmarcó sus declaraciones 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. [32]

Kleene propone la Tesis I : Esto dejó la expresión abierta de una "tesis" a Kleene. En su artículo de 1943, Predicados y cuantificadores recursivos, Kleene propuso su "TESIS I":

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 de Turing de las máquinas informáticas ( 23 ).

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

Dado que ha faltado una definición matemática precisa del término efectivamente calculable (efectivamente decidible), podemos tomar esta tesis ... como una definición de la misma ... [33]

referencias Church 1936; [ no lo suficientemente específico para verificar ] ( 23 ) hace referencia a Turing 1936-7 Kleene continúa señalando que:

la tesis tiene el carácter de una hipótesis, un punto enfatizado por Post y por Church ( 24 ). Si consideramos la tesis y su inverso 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, existen, como hemos sugerido, motivos bastante convincentes. [33]

(24) hace referencia a Post 1936 de Post y las definiciones formales de Church en la teoría de los números ordinales , Fund. Matemáticas . vol 28 (1936) págs. 11-21 (ver ref. # 2, Davis 1965 : 286).

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 la realizabilidad recursiva. Kleene pasó de presentar su trabajo en la terminología de 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 imposibilidad de resolver los problemas en el intuicionismo de EJ Brouwer. En su libro de texto de posgrado sobre lógica, se presenta 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 muestra que los resultados son incuestionables, utilizando su derivación simplificada de una máquina de Turing basada en el trabajo de Emil Post.Ambas tesis han demostrado ser equivalentes mediante el uso del "Teorema XXX".

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

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 ... [35]

Tesis de Turing: La tesis de Turing de que toda función que naturalmente se consideraría 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. [35]

Kleene, finalmente, utiliza por primera vez el término "tesis de Church-Turing" en una sección en la que ayuda a aclarar conceptos en el artículo de Alan Turing "El problema verbal en semigrupos con cancelación", como se exige en un crítica de William Boone. [36]

Desarrollos posteriores

Un intento de comprender la noción de "computabilidad efectiva" llevó a Robin Gandy (alumno y amigo de Turing) en 1980 a analizar la computación de la 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 acerca de 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 limitaciones) ... que, según se argumenta, cualquier máquina debe satisfacer". [37] 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".[38]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 de que "lo que puede calcularse mediante un dispositivo que satisfaga los principios I-IV es computable". [39]

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 "afinar la noción informal, formular axiomáticamente sus características generales e investigar el marco axiomático". [40] En su trabajo de 1997 y 2002, Sieg presenta una serie de restricciones sobre el comportamiento de un computor : "un agente informático humano que procede mecánicamente". Estas limitaciones se reducen a:

  • "(B.1) (Delimitación) Hay un límite fijo en el número de configuraciones simbólicas que un computor puede reconocer inmediatamente.
  • "(B.2) (Delimitación) Hay un límite fijo en el número de estados internos en los que puede estar un computor.
  • "(L.1) (Localidad) Un computador puede cambiar solo 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 observada previamente.
  • "(D) (Determinación) La (sub) configuración inmediatamente reconocible determina de forma única el siguiente paso de cálculo (y la identificación [descripción instantánea])"; declaró de otra manera: "El estado interno de un computor junto con la configuración observada fija de manera única el siguiente paso de cálculo y el siguiente estado interno". [41]

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

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, por ejemplo, "la definición correcta de computabilidad mecánica fue establecida más allá de toda duda por Turing". [44] El caso para ver la tesis como nada más que una definición es hecho explícitamente por Robert I. Soare , [45] 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 una 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. Stephen Kleene (1952) añade a la lista las funciones " razonables en el sistema S 1 " de Kurt Gödel 1936, y los " sistemas canónicos [también llamados normales ] " de Emil Post (1943, 1946) . [46] En la década de 1950, Hao Wang y Martin Davis simplificaron enormemente el modelo de máquina de Turing de una sola cinta (ver Máquina de Post-Turing ). Marvin Minskyexpandió 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 contador . A finales de la década de 1960 y principios de la de 1970, los investigadores expandieron el modelo de máquina contador a la máquina de registro , un primo cercano a la noción moderna de computadora . Otros modelos incluyen lógica combinatoria y algoritmos de Markov . Gurevich agrega el modelo de máquina de puntero de Kolmogorov y Uspensky (1953, 1958): "... solo querían ... convencerse de que no hay forma de extender la noción de función computable". [47]

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 arrojado 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 "razonable en S 1 ":

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

Uso informal en pruebas

Las pruebas en la teoría de la computabilidad a menudo invocan la tesis de Church-Turing de una manera informal para establecer la computabilidad de las funciones evitando los detalles (a menudo muy largos) que estarían involucrados en una prueba formal rigurosa. [49] 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 la función puede calcularse efectivamente, y luego concluir "por la tesis de Church-Turing" que la función es de Turing computable (equivalentemente, recursivo parcial).

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

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

Prueba: Sea A RE infinito. Enumeramos los elementos de A efectivamente, n 0 , n 1 , n 2 , n 3 , ...

De esta lista extraemos una sublista creciente: pon m 0 = n 0 , después de un número finito de pasos encontramos an n k tal que n k > m 0 , pon 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 .

Reclamo . B es decidible. Porque, para probar k en B debemos verificar si k = m i para algún i. Dado 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. Dado que esta prueba es efectiva, B es decidible y, según la tesis de Church , recursiva.

Para que el ejemplo anterior sea completamente riguroso, habría que construir cuidadosamente una máquina de Turing, o función λ, o invocar cuidadosamente axiomas de recursividad, o en el mejor de los casos, invocar hábilmente 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 un procedimiento efectivo está detallado en inglés 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 motivó la propuesta de variaciones de la tesis. Por ejemplo, la tesis física de Church-Turing afirma: "Todas las funciones físicamente computables son Turing computables". [51] : 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 varias cintas) solo sufre un factor de desaceleración logarítmica al simular cualquier máquina de Turing. [52]

Una variación de la tesis de Church-Turing aborda si se puede simular eficientemente un modelo de cálculo arbitrario pero "razonable". Esto se llama tesis de viabilidad , [53] también conocida como la tesis ( clásica ) de teoría de la complejidad de Church-Turing o la tesis extendida de Church-Turing , que no se debe a Church o Turing, sino que se realizó gradualmente en el desarrollo de teoría de la complejidad . Dice: [54] "Una máquina de Turing probabilística puede simular eficientemente cualquier modelo de cálculo realista". La palabra 'eficientemente' aquí significa hasta reducciones de tiempo polinomial. Esta tesis fue originalmente llamada tesis de Church-Turing de teoría 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 todos los modelos de cálculo "razonables" producen 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 la teoría de la complejidad de Church-Turing. Una tesis similar, llamada tesis de invariancia , fue presentada por Cees F. Slot y Peter van Emde Boas. Dice: "Las máquinas 'razonables' pueden simularse entre sí dentro de una sobrecarga delimitada polinomialmente en el tiempo y una sobrecarga de factor constante en el espacio ". [55] La tesis apareció originalmente en un artículo en STOC '84, que fue el primer artículo que mostró que polinomio- la sobrecarga de tiempo 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. [56]

Si se demuestra que BQP es un superconjunto estricto de BPP , invalidaría la tesis de la teoría de la complejidad de Church-Turing. 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 la teoría de la complejidad de Church-Turing por razones de eficiencia. En consecuencia, la tesis de Church-Turing de la teoría de la complejidad cuántica establece: [54] "Una máquina cuántica de Turing puede simular de manera eficiente cualquier modelo de cálculo realista".

Eugene Eberbach y Peter Wegner afirman que la tesis de Church-Turing a veces se interpreta de manera demasiado amplia, afirmando que "la afirmación más amplia de que los algoritmos capturan con precisión lo que se puede calcular no es válida". [57] [ página necesaria ] Afirman que las formas de cálculo no capturadas por la tesis son relevantes hoy en día, términos que ellos denominan cálculo 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 . [58] [59] [60] B. Jack Copeland afirma que es una cuestión 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. [61] 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 tanto, calcular funciones no recursivas es físicamente imposible. Esto se ha denominado la tesis fuerte de Church-Turing, o el principio Church-Turing-Deutsch , y es una de las bases 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 Turing), pero los eventos físicos incomputables no son "adaptables" para la construcción de una hipercomputadora . Por ejemplo, un universo en el que la física implica 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 cuestión abierta si todos los eventos de la mecánica cuántica son computables de Turing, aunque se sabe que los modelos rigurosos como las máquinas cuánticas de Turing son equivalentes a las máquinas deterministas de Turing. (No son necesariamente equivalentes de manera eficiente; ver 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 mecánicamente cuántica. [62] [63]

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

Los aspectos filosóficos de la tesis, con respecto a las computadoras físicas y biológicas, también se discuten en el libro de texto de 1989 de Odifreddi sobre teoría de la recursividad. [64] : 101–123

Funciones no computables

Se pueden definir formalmente funciones que no son computables. Un ejemplo bien conocido de tal función 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 n estados 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 puede resolver . Dado que la función de castor ocupado no puede ser calculada por máquinas de Turing, la tesis de Church-Turing establece que esta función no puede calcularse eficazmente por ningún método.

Varios modelos computacionales permiten el cálculo de funciones no computables (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. [65] [ página necesaria ]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 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 sobre computabilidad. [ cita requerida ]

Ver también

  • Máquina abstracta
  • Tesis de Church en matemáticas constructivas
  • Principio de Church-Turing-Deutsch , que establece que cada 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 computación
  • Oracle (ciencias de la computación)
  • Algoritmo superrecursivo
  • Completitud de Turing

Notas al pie

  1. ^ Robert Soare , "Turing Oracle Machines, 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 . Archivado desde el original el 5 de junio de 2019 . Consultado el 14 de julio de 2012 .
  3. ^ Iglesia 1936
  4. ↑ Kleene, 1936
  5. ^ Turing 1937a
  6. ↑ Kleene, 1936
  7. ^ Turing 1937b . Esquema de prueba en la p.153: [6]
  8. ^ Rosser 1939 en Davis 1965 : 225.
  9. ^ "efectivo". Nuevo diccionario colegiado de Merriam Webster (9ª ed.).
  10. ^ Consulte también "eficaz". Diccionario en línea de Merriam-Webster (11ª ed.) . Consultado el 26 de julio de 2014 , que también da estas definiciones de "efectivo" - el primero ["producir un efecto decidido, decisivo o deseado"] como la definición del sentido "1a" de la palabra "efectivo", y el segundo ["capaz de producir un resultado "] como parte de la" Discusión de sinónimos de EFECTIVO "allí, (en la parte introductoria, donde se resumen las similitudes entre los significados de las palabras" eficaz "," eficaz "," eficiente "y" eficaz ").
  11. ↑ a b Turing, AM (1938). Sistemas de lógica basados ​​en ordinales (PDF) (PhD). Universidad de Princeton. pag. 8. Archivado desde el original (PDF) el 23 de octubre de 2012 . Consultado el 23 de junio de 2012 .
  12. ↑ Gandy (1980 : 123) lo expresa de esta manera: Lo que es efectivamente calculable es computable. A esto lo llama "Tesis de la Iglesia".
  13. ^ David Hilbert y Wilhelm Ackermann: Grundzüge der teoretischen Logik, Berlín, Alemania, Springer, 1ª ed. 1928. (6a ed. 1972, ISBN 3-540-05843-5 ) Traducción al inglés: David Hilbert y Wilhelm Ackermann: Principles of Mathematical Logic, AMS Chelsea Publishing, Providence, Rhode Island, EE. UU., 1950 
  14. ^ Comentario de Davis antes de Church 1936 Un problema irresoluble de la teoría de números elementales en Davis 1965: 88. Church usa las palabras "calculabilidad efectiva" en la página 100 y siguientes.
  15. ↑ En su revisión de la Tesis de Church después de 70 años editada por Adam Olszewski et al. En 2006, la crítica de Peter Smith a un artículo de Muraswski y Wolenski sugiere 4 "líneas" sobre el 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
  16. ^ cf nota a pie de página 3 en Church 1936a An Unsolvable Problem of Elementary Number Theory en Davis 1965 : 89.
  17. ^ Dawson 1997 : 99.
  18. ↑ a b Sieg, 1997: 160.
  19. ↑ Sieg 1997: 160 citando la carta de 1935 escrita por Church a Kleene, cf Footnote 3 en Gödel 1934 en Davis 1965 : 44.
  20. ^ cf. Church 1936 en Davis 1965 : 105ff.
  21. ^ Comentario de Davis antes de Gödel 1934 en Davis 1965 : 40.
  22. ^ Para una discusión detallada de la adopción de Gödel de las máquinas de Turing como modelos de computación, vea Shagrir. "Goedel sobre Turing sobre computabilidad" (PDF) . Archivado desde el original (PDF) el 17 de diciembre de 2015 . Consultado el 8 de febrero de 2016 . [ falta la fecha ]
  23. ^ a b Turing, 1937 .
  24. ^ cf. Nota a pie de página del editor para el proceso combinatorio finito posterior a 1936 . Formulación I. en Davis 1965 : 289.
  25. ^ Publicada en 1936 en Davis 1965 : 291, nota al pie 8.
  26. ^ Publicada en 1936 en Davis 1952: 291.
  27. ^ Sieg 1997: 171 y 176-177.
  28. ^ Turing 1936–37 en Davis 1965 : 263ff.
  29. ^ Iglesia 1937 .
  30. ^ Turing 1939 en Davis: 160.
  31. ^ cf. Church 1934 en Davis 1965 : 100, también Turing 1939 en Davis 1965 : 160.
  32. ↑ cursiva agregada, Rosser 1939 en Davis 1965 : 226.
  33. ↑ a b Kleene 1943 en Davis 1965 : 274.
  34. ^ Kleene, 1952 : 300.
  35. ^ a b {{harvcolnb | Kleene | 1952 | p = 376}.
  36. ^ Kleene 1952 : 382,536
  37. ^ Gandy 1980 : 123 y siguientes.
  38. ^ Gandy 1980 : 135.
  39. ↑ Gandy 1980 : 126
  40. ^ Sieg 1998–9 en Sieg, Somner y Talcott 2002 : 390ff; también Sieg 1997: 154ss.
  41. ↑ En una nota a pie de página, Sieg divide el 1936 de Post (B) en (B.1) y (B.2) y (L) en (L.1) y (L.2) y describe (D) de manera diferente. Con respecto a su máquina Gandy propuesta, luego agrega LC.1, LC.2, GA.1 y GA.2. Estos son complicados; ver Sieg 1998–99 en Sieg, Somner & Talcott 2002 : 390ff.
  42. ↑ Se puede encontrar una colección de artículos en Olszewski, Woleński & Janusz (2006) . También una revisión de esta colección: Smith, Peter (11 de julio de 2007). "Tesis de la Iglesia después de 70 años" (PDF) .
  43. ^ Véase también Hodges, Andrew (2005). "¿Church y Turing tenían 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 .
  44. ^ Gödel, Kurt (1995) [¿193?]. "Proposiciones diofánticas indecidibles" . En Feferman, Solomon (ed.). Obras completas . 3 . Nueva York: Oxford University Press. pag. 168 . ISBN 978-0-19-507255-6. OCLC  928791907 : a través de Google Books.
  45. ^ Soare, Robert I. (septiembre de 1996). "Computabilidad y recursividad". Boletín de Lógica Simbólica . 2 (3): 284–321. CiteSeerX 10.1.1.35.5803 . doi : 10.2307 / 420992 . JSTOR 420992 .  
  46. ↑ Kleene, 1952: 320.
  47. ^ Gurevich 1988: 2
  48. ^ traducción de Gödel (1936) por Davis en The Undecidable p. 83, que difiere en el uso de la palabra "razonable" en la traducción de Kleene (1952) p. 321
  49. ^ Horsten en Olszewski, 2006 : 256.
  50. ^ Gabbay 2001 : 284
  51. ^ Piccinini, Gualtiero (enero de 2007). "Computacionalismo, la tesis de la Iglesia-Turing y la falacia de la Iglesia-Turing" (PDF) . Síntesis . 154 (1): 97-120. CiteSeerX 10.1.1.360.9796 . doi : 10.1007 / s11229-005-0194-z . S2CID 494161 .   
  52. ^ Arora, Sanjeev; Barak, Boaz (2009). Teoría de la complejidad: un enfoque moderno . Prensa de la Universidad de Cambridge. ISBN 978-0-521-42426-4. Secciones 1.4, "Máquinas como cuerdas y la máquina de Turing universal" y 1.7, "Prueba del teorema 1.9".
  53. ^ "Descripción oficial del problema" (PDF) . Archivado desde el original (PDF) el 24 de noviembre de 2005.
  54. ^ a b Kaye, Phillip; Laflamme, Raymond; Mosca, Michele (2007). Introducción a la computación cuántica . Prensa de la Universidad de Oxford. págs. 5-6. ISBN 978-0-19-857049-3.
  55. ↑ van Emde Boas, Peter (1990). "Modelos y Simulaciones de Máquinas". Handbook of Theoretical Computer Science A . Elsevier. pag. 5.
  56. ^ Ranura, C .; van Emde Boas, P. (diciembre de 1984). En cinta versus núcleo: una aplicación de funciones hash perfectas eficientes en el espacio a la invariancia del espacio . STOC .
  57. ^ Eberbach y Wegner 2003 .
  58. ^ 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 . 
  59. ^ Copeland, B. Jack (10 de noviembre de 2017). "La tesis de Church-Turing" . En Zalta, Edward N. (ed.). Enciclopedia de Filosofía de Stanford .
  60. ↑ Para encontrar un buen lugar para encontrar artículos originales, consulte Chalmers, David J. , ed. (2002). Filosofía de la mente: lecturas clásicas y contemporáneas . Nueva York: Oxford University Press. ISBN 978-0-19-514581-6. OCLC  610918145 .
  61. ^ Copeland, B. Jack (2004). "Cálculo". En Floridi, Luciano (ed.). La guía de Blackwell sobre la filosofía de la informática y la información . Wiley-Blackwell. pag. 15. ISBN 978-0-631-22919-3.
  62. ^ cf Penrose, Roger (1990). "Algoritmos y máquinas de Turing". La nueva mente del emperador: con respecto a las computadoras, las mentes y las leyes de la física . Oxford: Prensa de la Universidad de Oxford. págs. 47–49. ISBN 978-0-19-851973-7. OCLC  456785846 .
  63. ^ También la descripción de "la naturaleza no algorítmica de la comprensión matemática", Penrose, Roger (1990). "¿Dónde radica la física de la mente?". La nueva mente del emperador: con respecto a las computadoras, las mentes y las leyes de la física . Oxford: Prensa de la Universidad de Oxford. págs. 416–418. ISBN 978-0-19-851973-7. OCLC  456785846 .
  64. ^ Piergiorgio Odifreddi (1989). Teoría clásica de la recursividad . Estudios de Lógica y Fundamentos de las Matemáticas. 125 . Amsterdam: Holanda Septentrional.
  65. ^ 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 . Amsterdam: Compañía editorial de Holanda Septentrional. ISBN 978-0-444-85345-5.
  • Ben-Amram, AM (2005). "La tesis de Church-Turing y sus semejanzas" (PS) . Noticias SIGACT . 36 (3): 113-116. CiteSeerX  10.1.1.74.7308 . doi : 10.1145 / 1086649.1086651 . S2CID  13566703 .
  • 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 de la Computación Teórica (81).[ página necesaria ]
  • Burgin, Mark (2005). "Algoritmos superrecursivos". Monografías en informática . Saltador. ISBN 978-0-387-95569-8.
  • Iglesia, Alonzo (1932). "Un conjunto de postulados para la fundación de la lógica". Annals of Mathematics . 33 (2): 346–366. doi : 10.2307 / 1968337 . JSTOR  1968337 .
  • Church, Alonzo (abril de 1936a). "Un problema irresoluble de la teoría de números elemental" (PDF) . Revista Estadounidense de Matemáticas . 58 (2): 345–363. doi : 10.2307 / 2371045 . JSTOR  2371045 . Archivado desde el original (PDF) el 27 de febrero de 2020.
  • Church, Alonzo (junio de 1936b). "Una nota sobre el Entscheidungsproblem". Revista de lógica simbólica . 1 (1): 40–41. doi : 10.2307 / 2269326 . JSTOR  2269326 .
  • Church, Alonzo (marzo de 1937). "Revisión: AM Turing, en números computables, con una aplicación al Entscheidungsproblem". Revista de lógica simbólica . 2 (1): 42–43. doi : 10.2307 / 2268810 . JSTOR  2268810 .
  • Iglesia, Alonzo (1941). Los cálculos de conversión lambda . Princeton: Prensa de la Universidad de Princeton.
  • 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. págs. 137-160.
  • Davis, Martin , ed. (1965). Los artículos básicos e indecidibles 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, MA: AK Peters.
  • Eberbach, E .; Wegner, P. (octubre de 2003). "Más allá de las máquinas de Turing". Boletín de la Asociación Europea de Ciencias de la Computación Teórica (81): 279–304.
  • Gabbay, DM (2001). Manual de lógica filosófica . 1 (2ª ed.).
  • Gandy, Robin (1980). "Tesis de la Iglesia y los principios de los mecanismos". En HJ Barwise; HJ Keisler; K. Kunen (eds.). El Simposio de Kleene . Compañía editorial de Holanda Septentrional. 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. 51ss. ISBN 978-3-211-82637-9.
  • Gödel, Kurt (1965) [1934]. "Sobre proposiciones indecidibles de sistemas matemáticos formales". En Davis, Martin (ed.). Lo indecidible . Kleene y Rosser (tomadores de notas de conferencias); Instituto de Estudios Avanzados (patrocinador de la conferencia). Nueva York: Raven Press.
  • Gödel, Kurt (1936). "Über die Lāange von Beweisen" [Sobre la longitud de las pruebas]. Ergenbnisse Eines Mathematishen Kolloquiums (en alemán). Heft (7): 23-24.Citado por Kleene (1952) .
  • Gurevich, Yuri (junio de 1988). "Sobre máquinas Kolmogorov y problemas relacionados". Boletín de la Asociación Europea de Ciencias de la Computación Teórica (35): 71–82.
  • Gurevich, Yuri (julio de 2000). "Máquinas de estado abstracto secuencial capturan algoritmos secuenciales" (PDF) . Transacciones ACM en lógica computacional . 1 (1): 77-111. CiteSeerX  10.1.1.146.3017 . doi : 10.1145 / 343369.343384 . S2CID  2031696 .
  • Herbrand, Jacques (1932). "Sur la non-contradiction de l'arithmétique". Journal für die Reine und Angewandte Mathematik (en francés). 166 : 1–8.
  • Hofstadter, Douglas R. "Capítulo XVII: Iglesia, Turing, Tarski y otros". Gödel, Escher, Bach: una eterna trenza dorada .[ páginas necesarias ]
  • Kleene, Stephen Cole (enero de 1935). "Una teoría de los enteros positivos en lógica formal". Revista Estadounidense de Matemáticas . 57 (1): 153–173 y 219–244. doi : 10.2307 / 2372027 . JSTOR  2372027 .
  • Kleene, Stephen Cole (1936). "Lambda-Definibilidad y recursividad". Diario de matemáticas de Duke . 2 (2): 340–353. doi : 10.1215 / s0012-7094-36-00227-2 .
  • Kleene, Stephen Cole (1943). "Predicados y cuantificadores recursivos" . Transacciones de la Sociedad Americana de Matemáticas . 54 (1): 41–73. doi : 10.2307 / 1990131 . JSTOR  1990131 .Reimpreso en The Undecidable , p. 255ff. Kleene refinó su definición de "recursividad general" y procedió en su capítulo "12. Teorías algorítmicas" a postular "Tesis I" (p. 274); más tarde repetiría esta tesis (en Kleene 1952 : 300) y la denominaría "Tesis de la Iglesia" ( Kleene 1952 : 317) (es decir, la tesis de la Iglesia ).
  • 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 . 1 / Algoritmos fundamentales (2ª ed.). Addison – Wesley.
  • Kugel, Peter (noviembre de 2005). "Es hora de pensar fuera 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.
  • Markov, AA (1960) [1954]. "La teoría de los algoritmos". Traducciones de la Sociedad Americana de Matemáticas . 2 (15): 1-14.
  • Olszewski, Adam; Woleński, Jan; Janusz, Robert, eds. (2006). 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 el teorema de la Iglesia". El diario de la lógica simbólica . 4 (2): 53–60. doi : 10.2307 / 2269059 . JSTOR  2269059 .
  • Sieg, Wilfried; Sommer, Richard; Talcott, Carolyn, eds. (2002). Reflexiones sobre los fundamentos de las matemáticas: ensayos en honor a Solomon Feferman . Notas de clase en lógica. 15 . AK Peters, Ltd. ISBN 978-1-56881-169-7.
  • Syropoulos, Apostolos (2008). Hipercomputación: Computación más allá de la barrera de Turing de la Iglesia . Saltador. ISBN 978-0-387-30886-9.
  • Turing, AM (1937) [Entregado a la Sociedad en noviembre de 1936], "On Computable Numbers, with an Application to the Entscheidungsproblem" (PDF) , Proceedings of the London Mathematical Society , 2, 42 , págs. 230–65, doi : 10.1112 / plms / s2-42.1.230y Turing, AM (1938). "En números computables, con una aplicación al Entscheidungsproblem: una corrección". Actas de la London Mathematical Society . 2. 43 (publicado en 1937). págs. 544–6. doi : 10.1112 / plms / s2-43.6.544 .(Ver también: Davis 1965 : 115ff)
  • Alan Mathison Turing (diciembre de 1937). "Computabilidad y λ-definibilidad" (PDF) . Revista de lógica simbólica . 2 (4): 153-163. doi : 10.2307 / 2268280 . JSTOR  2268280 . S2CID  2317046 . Archivado desde el original (PDF) el 2020-08-09.

Enlaces externos

  • Entrada "The Church-Turing Thesis" de B. Jack Copeland en la Enciclopedia de Filosofía de Stanford .
  • Entrada de "Computación en sistemas físicos" de Gualtiero Piccinini en la Enciclopedia de Filosofía de Stanford , un tratamiento filosófico integral de temas relevantes.
  • Kaznatcheev, Artem (11 de septiembre de 2014). "Idealismo trascendental y 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 se dedicó a la tesis de Church-Turing.