Lambda kalkul

z Wikipédie, slobodnej encyklopédie

Lambda kalkul (λ-kalkul) je formálny systém a výpočtový model používaný v teoretickej informatike a matematike pre štúdium funkcií a rekurzie. Jeho autormi sú Alonzo Church a Stephen Cole Kleene. λ-kalkul je teoretickým základom funkcionálneho programovania a príslušných programovacích jazykov, najmä Lispu.

λ-kalkul analyzuje funkcie nie z hľadiska pôvodného matematického zmyslu zobrazenia z množiny do množiny, ale ako metódu výpočtu. Dá sa chápať ako najjednoduchší univerzálny programovací jazyk. Je univerzálny, pretože ľubovoľnú rekurzívne spočítateľnú funkciu je možné vyjadriť a vyčísliť pomocou tohto formalizmu, λ-kalkul je teda výpočtovou silou ekvivalentný Turingovmu stroju.