Lambda račun: opis teorema, lastnosti, primeri

Lambda-kalkulus je formalni sistem v matematični logiki za izražanje izračunov, ki temelji na abstrakciji in uporabi funkcij z uporabo vezave in zamenjave spremenljivk. To je univerzalni model, ki ga je mogoče uporabiti za načrtovanje katerega koli Turingovega stroja. Lambda račun je v tridesetih letih prejšnjega stoletja prvič predstavil slavni matematik Church.

Sistem je sestavljen iz konstrukcije lambda izrazov in izvajanja redukcijskih operacij na njih.

Razlage in uporaba

Grška črka lambda (λ) se uporablja v lambda-izrazih in lambda-terminah za označevanje vezave spremenljivke v funkciji.

Lambda račun je lahko brez tipizacije ali s tipizacijo. V prvi različici se lahko funkcije uporabljajo le, če lahko sprejemajo podatke te vrste. Tipizirani lambda-račun je šibkejši, izrazi lahko manjšo vrednost. Po drugi strani pa lahko z njimi dokažete več stvari.

Eden od razlogov za obstoj številnih različnih vrst je želja znanstvenikov, da bi naredili več, ne da bi se odpovedali možnosti dokazovanja močnih trditev lambda računa.

Sistem se uporablja na različnih področjih matematike, filozofije, jezikoslovja in računalništva. Predvsem je lambda-kalkulus izračun, ki je imel pomembno vlogo pri razvoju teorije programskih jezikov. Funkcionalni slogi ustvarjanja so tisti, ki izvajajo sisteme. Prav tako so vroča tema raziskav v teoriji teh kategorij.

Za bebce

Lambda-kalkulus je uvedel matematik Alonzo Church v tridesetih letih 20. stoletja kot del študije o temeljih znanosti. Prvotni sistem je bil logično nekonsistenten leta 1935, ko sta Stephen Kline in J. J. Kline prvič dokazala, da sta nezdružljiva. Б. Rosser je razvil paradoks Kliney-Rosser.

Nato je Church leta 1936 izločil in objavil le tisti del, ki je bil pomemben za računanje, kar se zdaj imenuje neotipljeni lambda račun. Leta 1940 je predstavil tudi šibkejšo, vendar logično dosledno teorijo, znano kot enostavni sistem tipov. V svojem delu razlaga celotno teorijo v preprostem jeziku, zato bi lahko rekli, da je Church objavil lambda račun za malčke.

Do šestdesetih let 20. stoletja, ko je postala jasna njegova povezava s programskimi jeziki, je bil λ le formalizem. Zahvaljujoč aplikacijam Richarda Montaguea in drugih jezikoslovcev na področju semantike naravnega jezika je kalkulacija dobila častno mesto tako v jezikoslovju kot v računalništvu.

Izvor simbola

Lambda ne označuje besede ali okrajšave, ampak je nastala s sklicevanjem na Russellovo Matematično načelo, čemur sta sledili dve tipografski spremembi. Primer zapisa: Za funkcijo f s f (y) = 2y + 1 je 2ŷ + 1. Tudi v tem primeru se za označevanje vhodne spremenljivke uporablja simbol za prevoz ("klobuk") nad y.

Cerkev je prvotno nameravala uporabiti podobne simbole, vendar tiskarji niso mogli postaviti simbola "klobuka" nad črke. Namesto tega so ga prvotno natisnili kot /y.2y+1". V naslednji epizodi urejanja so pisci nadomestili znak "/ " z vizualno podobnim znakom.

Uvod v lambda račun

Sistem je sestavljen iz jezika izrazov, ki so izbrani po določeni formalni sintaksi, in niza pravil transformacije, ki omogočajo manipulacijo z njimi. To zadnjo točko si lahko predstavljamo kot teorijo enačb ali kot operativno opredelitev.

Vse funkcije v lambda-kalkulu so anonimne, tj. brez imen. Sprejemajo samo eno vhodno spremenljivko, pri čemer se currying uporablja za implementacijo grafov z več nepremenljivkami.

Izrazi Lambda

Sintaksa računa opredeljuje nekatere izraze kot veljavne in druge kot neveljavne. Tako kot so različni nizi znakov veljavni programi C, nekateri pa ne. Veljavni izraz lambda-kalkulatorja se imenuje ""lambda-terminus"".

Naslednja tri pravila zagotavljajo induktivno definicijo, ki jo je mogoče uporabiti za konstruiranje vseh skladenjsko veljavnih pojmov:

Spremenljivka x je veljavni izraz lambda:

• če je T LT in je x nekonstanten, potem se (lambda xt) imenuje abstrakcija.
• če sta tako T kot s koncepta, potem se (TS) imenuje aplikacija.

Nič drugega ni izraz lambda. Koncept je torej veljaven, če in samo če ga je mogoče dobiti z večkratno uporabo teh treh pravil. Vendar se lahko nekateri oklepaji izpustijo v skladu z drugimi merili.

Opredelitev

Izrazi lambda so sestavljeni iz:

• spremenljivk v 1, v 2,..., v n,...
• simbola za abstrakcijo ""λ"" in točka.`
• oklepaji ().

Množico Λ lahko definiramo induktivno:

• Če je x spremenljivka, potem je x ∈ Λ