Cálculo lambda

El cálculo lambda es un sistema formal diseñado para investigar la definición de función, la noción de aplicación de funciones y la recursión. Fue introducido por Alonzo Church y Stephen Kleene en la década de 1930; Church usó el cálculo lambda en 1936 para resolver el Entscheidungsproblem. Puede ser usado para definir de manera limpia y precisa qué es una " función computable". El interrogante de si dos expresiones del cálculo lambda son equivalentes no puede ser resuelto por un algoritmo general. Esta fue la primera pregunta, incluso antes que el problema de la parada, cuya indecidibilidad fue probada. El cálculo lambda tiene una gran influencia sobre los lenguajes funcionales, como Lisp, ML y Haskell.

Se puede considerar al cálculo lambda como el lenguaje universal de programación más pequeño. Consiste en una regla de transformación simple (sustitución de variables) y un esquema simple para definir funciones.

El cálculo lambda es universal porque cualquier función computable puede ser expresada y evaluada a través de él. Por lo tanto, es equivalente a las máquinas de Turing. Sin embargo, el cálculo lambda no hace énfasis en el uso de reglas de transformación y no considera las máquinas reales que pueden implementarlo. Se trata de una propuesta más cercana al software que al hardware.

Este artículo se enfocará sobre el cálculo lambda sin tipos, como fue diseñado originalmente por Church. Desde entonces, algunos cálculo lambda tipados fueron creados.

Other Languages
bosanski: Lambda račun
čeština: Lambda kalkul
Ελληνικά: Λογισμός λάμδα
Esperanto: Lambda-kalkulo
français: Lambda-calcul
hrvatski: Lambda račun
italiano: Lambda calcolo
日本語: ラムダ計算
한국어: 람다 대수
Nederlands: Lambdacalculus
norsk bokmål: Lambdakalkyle
português: Cálculo lambda
srpskohrvatski / српскохрватски: Lambda račun
Simple English: Lambda calculus
slovenčina: Lambda kalkul
српски / srpski: Ламбда рачун
svenska: Lambdakalkyl
українська: Лямбда-числення
Tiếng Việt: Phép tính lambda
中文: Λ演算