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í
- De la pregunta de Hilbert a la máquina universal (paso 5 de 7)
Bibliografía
Fuente original
Estudios y contexto
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.