Lambdakalkyle
From Wikipedia, the free encyclopedia
Lambdakalkulus eller lambdakalkylen[trenger referanse] (også kjent som -kalkylen) er et formelt system innenfor informatikk, logikk og matematikk utviklet av Alonzo Church i 1930-årene. Formålet var å undersøke fundamentet for matematikk, men Stephen Kleene og J.B. Rosser viste i 1935 at systemet er, logisk sett, inkonsistent. I 1940 presenterte Alonzo Church et typesystem for lambdakalkylen som gir opphav til et konsistent system, men som begrenser beregnbarhetsstryket betraktelig.
Senere ble systemet forsket med som et fundament for beregninger, og Alan Turing viste i 1937 at lambdakalkylen er turingkomplett. I dag er det i denne forbindelse den utypete lambdakalkylen er mest kjent. Se typeteori for typede varianter av lambdakalkylen.