La historia de la IA

Cálculo lambda y problema irresoluble

Etapa 1 · Los fundamentos (1763–1942) › Computabilidad

Linaje
Símbolos y lógica
Tipo
Publicación

Quién

Universidad de Princeton

Qué ocurrió

Alonzo Church publica en abril de 1936, en el American Journal of Mathematics, «An Unsolvable Problem of Elementary Number Theory», presentado ante la American Mathematical Society un año antes.

Qué aportó

Propone que lo calculable de forma efectiva es lo que se puede expresar en su cálculo lambda, y con esa definición demuestra que hay problemas sin solución mecánica. Poco después lo aplica al Entscheidungsproblem, con respuesta negativa.

Desarrollo

Alonzo Church, profesor en Princeton, llevaba desde principios de los años treinta desarrollando con sus alumnos Stephen Kleene y J. Barkley Rosser un sistema formal llamado cálculo lambda. En él todo se construye con funciones: definirlas y aplicarlas a argumentos. Hasta los números son funciones: el 2 es la función que aplica otra dos veces. Kleene mostró que con ese sistema tan austero se podían expresar las funciones aritméticas habituales, y Church y Kleene probaron que las funciones definibles en él coinciden con las funciones recursivas que había estudiado Gödel.

Eso llevó a Church a una propuesta audaz: una función de números es calculable de forma efectiva, es decir, mediante un procedimiento mecánico, solo si se puede definir en el cálculo lambda. Es lo que hoy se llama tesis de Church. No se puede demostrar, porque compara una idea intuitiva con una definición matemática, pero da por fin algo preciso con lo que trabajar.

Con esa definición, el artículo publicado en abril de 1936 construye un problema de teoría de números que ningún procedimiento mecánico resuelve. Poco después, en una breve nota en el primer volumen del Journal of Symbolic Logic, Church aplicó el resultado al problema de la decisión de Hilbert y Ackermann: no existe un método general para decidir si una fórmula de la lógica de primer orden es válida.

Gödel no quedó convencido por la propuesta de Church. Le convenció la de Turing, publicada unos meses después, que llegaba a la misma frontera desde otro sitio.

Nivel técnico

El cálculo lambda solo tiene tres cosas: variables, la definición de una función (λx.M, «la función que a x le asigna M») y la aplicación de una función a un argumento (M N). Calcular es sustituir: (λx.M) N se reduce a M con N en lugar de x.

Los números se representan como funciones. El 2 es λf.λx.f(f x): toma una función y la aplica dos veces. Con estas definiciones Church y Kleene expresaron la suma, la multiplicación y cualquier función recursiva. El cálculo lambda es el antecedente directo de los lenguajes funcionales, empezando por Lisp.

Viene de

  • El Entscheidungsproblem (1928)

    Influencia directa documentada

    Ambos artículos responden al Entscheidungsproblem; el de Turing lo nombra en el título

Lleva a

  • On Computable Numbers (30 de noviembre de 1936)

    Convergencia independiente

    Mismo resultado por vías independientes

  • Finite Combinatory Processes (septiembre de 1936)

    Influencia directa documentada

    El artículo se presenta desde la primera frase como un desarrollo en la línea del teorema de incompletitud de Gödel y de los problemas sin solución de Church

Hilos que pasan por aquí

Bibliografía

Cómo citar

«Cálculo lambda y problema irresoluble». En La historia de la IA, revisión del 13 de noviembre de 2026. https://thehistoryofai.com/es/hito/church-calculo-lambda

Última revisión de esta ficha: 13 de noviembre de 2026.

Abrir en la cronología interactiva