¿Relación entre la máquina de Turing y el cálculo de Lambda?

49

¿Existe una relación entre la Máquina de Turing y el cálculo Lambda, o simplemente surgieron al mismo tiempo?

computability lambda-calculus turing-machines ojo de halcón
fuente

77

¿Puedes elaborar tu pregunta? Ambos modelos tienen el mismo poder computacional (ambos pueden expresar la familia de funciones recursivas), es decir, están completos. Ver: en.wikipedia.org/wiki/Turing_completeness

Joel Rybicki

relacionado: Teoría de la posibilidad de realización: diferencia de poder entre el cálculo Lambda y las máquinas de Turing

Kaveh

Esta es una buena pregunta!

Tayfun paga el

31

El cálculo lambda es más antiguo que el modelo de máquina de Turing, aparentemente data del período 1928-1929 (Seldin 2006), y fue inventado para encapsular la noción de una función esquemática que Church necesitaba para una lógica fundamental que él ideó. No se inventó para capturar la noción general de función computable y, de hecho, una versión tipada más débil habría servido mejor a sus propósitos.

Parece ser incidental el propósito de que el cálculo que inventó la Iglesia resultó ser Turing completo, aunque más tarde Church utilizó el cálculo lambda como base para lo que llamó las funciones efectivamente computables (1936), a lo que Turing recurrió en su artículo .

La teoría simple de los tipos de Church (1940) proporciona una teoría de funciones más moderada y tipificada que es suficiente para expresar la sintaxis de la lógica de orden superior, pero no expresa todas las funciones recursivas. Puede considerarse que esta teoría está más en sintonía con la motivación original de Church.

Referencias

Iglesia (1936). Un problema sin solución en la teoría de los números elementales. American Journal of Mathematics 58: 345—363.
Iglesia (1940). Una formulación de la teoría simple de los tipos . Journal of Symbolic Logic 5 (2): 56-68.
Seldin (2006). La lógica del curry y la iglesia . En Handbook of the History of Logic, vol.5: Logic from Russell to Church , p. 819-874. Holanda Septentrional: Amsterdam.

Nota Esta respuesta se revisó sustancialmente debido a las objeciones de Kaveh y Sasho. Recomiendo la línea de tiempo de Wikipedia que sugirió Kaveh, Historia de la tesis de la Iglesia-Turing , que tiene algunas citas de artículos seminales.

Charles Stewart
fuente

2

Church afirmó que el cálculo lambda captura la notación intuitiva de la función computable antes del artículo de Turing, por eso se llama Tesis de Church. La idea de capturar la noción general de funciones computables se remonta más atrás (por ejemplo, las funciones recursivas generales de Godel), y Church estaba tratando de capturarla.

Kaveh

55

Creo que es engañoso decir que la equivalencia de los modelos es un accidente completo. Me parece que Church y Turing se propusieron capturar nociones relacionadas, incluso si no era inmediatamente obvio que las nociones estaban realmente relacionadas. ¿Diría que es un "accidente completo" que la integración y la anti-diferenciación de Riemann estén estrechamente relacionadas?

Sasho Nikolov

@Kaveh: Según Seldin (2006) La lógica de Church and Curry , los objetivos y la sintaxis del cálculo lambda se desarrollaron en el período de 1928 a 1929, mucho antes de que Church conociera la noción general de función recursiva. Mi respuesta se beneficiaría de una línea de tiempo, pero no tengo tiempo para armar eso ahora.

Charles Stewart el

1

@Charles: La iglesia estuvo en Gotinga 1927-1928. Seguramente estaba al tanto de lo que estaba sucediendo sobre la teoría de la función recursiva y el programa de Hilbert. El resultado de Ackermann sobre una función recursiva no primitiva es del mismo año. Church estaba tratando de construir una base para las matemáticas. Todo esto sucedió antes del papel de Turing. Mira esto . Kleene demostró la equivalencia de las funciones recursivas generales y la función definible

antes del trabajo de Turing. Su último párrafo es engañoso, ya que da la sensación de que lo fueron

λ

$\lambda$

Kaveh

1

@Charles, mientras escribía, estoy de acuerdo en que la motivación original de Church era construir una base (algo así como el sistema de Frege) (AFAIK), pero también lo consideró como un modelo de cálculo antes del trabajo de Turing. No creo que sea necesario eliminar la respuesta, revisar el segundo párrafo debería hacerlo bien. (La razón por la que comenté es que siento que en los últimos tiempos la gente subestima la computabilidad del trabajo de la Iglesia.)

Kaveh

26

Solo me gustaría señalar que, si bien el cálculo lambda y las máquinas de Turing calculan la misma clase de funciones teóricas de números, no son exactamente equivalentes en todos los sentidos imaginables. Por ejemplo, en la teoría de la realización hay afirmaciones que pueden realizarse con una máquina de Turing pero no con el cálculo lambda. Una de esas declaraciones es la tesis formal de la Iglesia, que establece:

\forall f : n a t \to n a t \exists e \forall n \exists k (T (e, n, k) \land U (k, f (n)))

$\forall f : \mathbf{nat} \to \mathbf{nat} \ \exists e \ \forall n \ \exists k \ \big( \mathbf{T}(e, n, k) \land \mathbf{U}(k,f(n)) \big)$

$\mathbf{T}$ $c$ $f$ $e$ $f$ $f$ $c$ $c$ $f$ . Esto no se puede hacer (puedo explicar por qué, si lo hace como una pregunta por separado).

Andrej Bauer
fuente

44

T_{E} X

$T_EX$

Andrej, el artículo de Wikipedia usa un orden diferente de los parámetros que estás utilizando, el segundo argumento es la entrada y el tercero es el código para detener la computación, el primer argumento es el código de la máquina. Supongo que estás diciendo CT, lo edité basado en vDT88.

Kaveh

f

$f$

λ

$\lambda$

f

$f$

λ

$\lambda$

@Kaveh: Creo que fue al revés, pero también me pregunto por qué no es natural tener una salida del mismo tipo que la entrada en el caso del cálculo lambda.

Abel Molina

1

f : R \to R

$f : \mathbb{R} \to \mathbb{R}$

2^{N}

$2^\mathbb{N}$

N^{N}

$\mathbb{N}^\mathbb{N}$

11

Están relacionados tanto matemática como históricamente.

El cálculo lambda fue desarrollado en 1928-1929 por Alonzo Church (publicado en 1932).

La máquina de Turing fue desarrollada en 1935-1937 por Alan Turing (publicado en 1937).

Alan Turing fue el Ph.D. de Alonzo Church Estudiante en Princeton desde 1936-1938.

Las máquinas de Turing y el cálculo lambda son equivalentes en potencia computacional: cada uno puede simular eficientemente al otro.

Matt podría
fuente

6

Entscheidungsproblem es uno de los 23 problemas famosos propuestos por el matemático David Hilbert.

En 1936 y 1937, Alonzo Church y Alan Turing, respectivamente, publicaron artículos independientes que muestran que es imposible decidir algorítmicamente si las declaraciones en aritmética son verdaderas o falsas, y por lo tanto, una solución general al problema de Entscheidungs es imposible.

Esto fue hecho por Alonzo Church en 1936 con el concepto de "cálculo efectivo" basado en su cálculo λ y por Alan Turing en el mismo año con su concepto de máquinas Turing. Más tarde se reconoció que estos son modelos equivalentes de computación. - Wikipedia

Por lo tanto, el cálculo lambda y las máquinas de Turing no solo están estrechamente relacionadas, sino que son modelos equivalentes de cálculo .

También te puede gustar leer The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine de Charles Petzold . Este libro captura información interesante sobre el tema.

Pratik Deoghare
fuente

4

Las máquinas de Turing y el cálculo Lambda son dos modelos que capturan la noción de algoritmo (cálculo mecánico). El cálculo de Lambda fue inventado por Church para realizar cálculos con funciones. Es la base de los lenguajes de programación funcionales. Básicamente, cada problema que es computable (decidible) por las máquinas de Turing también es computable usando el cálculo Lambda. Por lo tanto, son dos modelos equivalentes de cálculo (hasta factores polinómicos) y ambos intentan capturar el poder de cualquier cálculo mecánico.

Mohammad Al-Turkistany
fuente

¿Relación entre la máquina de Turing y el cálculo de Lambda?

Respuestas:

Referencias