Prvýkrát uverejnené 12. decembra 2012; podstatná revízia piatok 8. februára 2013
A-počet je v podstate jednoduchým zápisom funkcií a aplikácií. Hlavnými myšlienkami sú použitie funkcie na argument a formovanie funkcií abstrakciou. Syntax základného počtu λ-kalkúl je pomerne riedka, čo z nej robí elegantný a zameraný zápis reprezentujúci funkcie. Funkcie a argumenty sú na rovnakej úrovni. Výsledkom je intencionálna teória funkcií ako pravidiel výpočtu, ktorá kontrastuje s extenzívnou teóriou funkcií ako množiny usporiadaných párov. Napriek svojej riedkej syntaxi, vďaka expresívnosti a flexibilite λ-kalkulu je hojnosť logiky a matematiky. Tento príspevok rozvíja niektoré najdôležitejšie oblasti a pripravuje čitateľa na ďalšie štúdium predmetu a jeho aplikácií vo filozofii, lingvistike, počítačovej vede a logike.
1. Úvod
1.1 Operácie s viacerými argumentmi
1.2 Náročnosť
2. Syntax
2.1 Premenné, viazané a bezplatné
2.2 Kombinátory
3. Stručná história λ-kalkulu
4. Zníženie
4.1 Iné pojmy redukcie
4.2 Stratégie znižovania
5. λ-teórie
5.1 Základná teória λ
5.2 Rozšírenie základnej teórie λ
6. Konzistentnosť počtu A
7. Sémantika A-počtu
8. Rozšírenia a variácie
8.1 Kombinovaná logika
8.2 Pridávanie typov
9. Aplikácie
9.1 Logika à la
9.2 Výpočty
9.3 Vzťahy
Bibliografia
Akademické nástroje
Ďalšie internetové zdroje
Súvisiace záznamy
1. Úvod
A-počet je elegantný zápis pre prácu s aplikáciami funkcií na argumenty. Aby sme si vzali matematický príklad, predpokladajme, že sme dostali jednoduchý polynóm, ako napríklad x 2 - 2 · x + 5. Aká je hodnota tohto výrazu, keď x = 2? Vypočítame to „zapojením“2 pre x vo výraze: dostaneme 2 2 - 2 · 2 + 5, ktoré môžeme ďalej zredukovať, aby sme dostali odpoveď 5. Ak chceme použiť λ-kalkul na znázornenie situácie, začíname s termínom λ
A x [x 2 - 2 x x 5].
Operátory λ nám umožňujú abstraktovať cez x. Intuitívne je možné čítať 'λ x [x 2 - 2 · x + 5]' ako výraz, ktorý čaká na hodnotu a pre premennú x. Ak je takáto hodnota a (napríklad číslo 2), hodnota výrazu je 2 - 2 · a + 5. „A“samo osebe nemá význam; viaže iba premennú x a chráni ju tak, ako bola, pred vonkajšími vplyvmi. Terminológia v λ-kalkulu je, že chceme tento výraz použiť na argument a získať hodnotu. Píšeme „M a“, aby sme označili použitie funkcie M na argument a. Pokračovaním príkladu dostaneme:
(A x [x 2 - 2 x x 5]) 2
⊳
⟨Nahradiť 2 za x⟩
2 2 - 2 + 2 + 5
=
⟨ Aritmetika ⟩
4 - 4 + 5
=
⟨ Aritmetika ⟩
5
Prvým krokom tohto výpočtu, vložením '2' pre výskyt x vo výraze 'x 2 - 2 · x + 5', je prechod z abstrakčného členu na iný termín pomocou operácie substitúcie. Zvyšné rovnosti sú opodstatnené výpočtom s prirodzenými číslami.
Tento príklad naznačuje ústredný princíp λ-kalkulu, ktorý sa nazýva β-redukcia:
(β) (λ x [M]) N ⊳ M [x: = N]
Rozumie sa, že dokážeme redukovať alebo sťahovať (⊳) aplikáciu (λ x M) N abstrakčného termínu (ľavá strana, λ x M) na niečo (pravá strana, N) jednoduchým zapojením N pre výskyt x vo vnútri M (to je to, čo predstavuje zápis „M [x: = N]“). Toto je princíp ß-redukcie; je to srdce kalkulu λ.
1.1 Operácie s viacerými argumentmi
A čo funkcie viacerých argumentov? Môže počet A predstavovať operácie, ako je výpočet dĺžky prepony pravouhlého trojuholníka:
Hypotéza pravouhlého trojuholníka s nohami dĺžky x a y ⇒ √ (x ² + y ²),
Operácia dĺžka hypotéky mapuje dve kladné reálne čísla x a y a ďalšie kladné reálne čísla. Takéto operácie s viacerými aritami je možné predstavovať pomocou aparátu A-počtu tým, že sa na operáciu pozerá ako na jeden vstup súčasne. Operáciu je teda možné vnímať ako prijímanie jedného vstupu, x, kladného reálneho čísla, a produkujúce ako svoju hodnotu nie číslo, ale operáciu: a to operáciu, ktorá berie kladné reálne číslo y ako vstup a produkuje ako výstup kladné reálne číslo √ (x ² + y ²). Dalo by sa zhrnúť diskusiu tvrdením, že operácia, dĺžka prepony, ktorá počíta dĺžku prepony pravouhlého trojuholníka vzhľadom na dĺžky a a b jeho nôh, je:
dĺžka prepony: = λ a [λ b [√ (a² + b ²)]
Na základe zásady β-redukcie máme napríklad to, že dĺžka prepony 3, aplikácia dĺžky prepony 3, je λ b [√ (3² + b ²)], čo je funkcia tejto funkcie “čaká sa na ďalší argument. Na dĺžku mínusu 3 v dĺžke λ možno pozerať ako na funkciu, ktorá počíta dĺžku mínusu pravouhlého trojuholníka s dĺžkou jedného z jeho nôh 3. Konečne zistíme, že (dĺžka mínus 3) aplikácia dĺžky prepony na 3 a potom na 4 - je 5, ako sa očakávalo.
Ďalším spôsobom, ako pochopiť redukciu funkcií na viacerých miestach na funkcie na jednom mieste, je predstaviť si stroj M, ktorý sa na začiatku začína načítaním prvého a viacerých argumentov a, b, … do pamäte. Ak jeden potom pozastaví stroj po načítaní prvý argument do pamäti, je možné zobraziť výsledok ako ďalší stroj M A, ktorý ich čaká jeden menej vstup; prvý argument je teraz opravený.
1.2 Náročnosť
Pojem funkcie alebo operácie pri práci v λ-kalkulu je náročný. Môžeme vidieť λ x [M] ako opis operácie, ktorá pri x vytvára M; telo M abstrakčného členu je samo opis toho, čo robiť s x. Intuitívne, vzhľadom na opisy M a N, sa vo všeobecnosti nemôžeme rozhodnúť, či sa λ x [M] rovná λ x [N]. Tieto dva výrazy by sa mohli „správať“rovnako (mať rovnakú hodnotu pri rovnakých argumentoch), ale nemusí byť jasné, aké zdroje sú potrebné na preukázanie rovnosti výrazov.
Naopak, definícia funkcie v teórii množín ako množina f usporiadaných párov spĺňajúcich vlastnosť, ktorú (x, y) ∈ f a (x, z) ∈ f znamenajú y = z. Pojem rovnosť funkcií predstavuje množinu funkcií qua sets, ktorá podľa štandardného princípu rozšírenosti množín znamená, že dve funkcie sú si rovné, keď obsahujú rovnaké usporiadané dvojice.
K λ-kalkulu je možné pridať istý druh princípu rozšíriteľnosti; pozri časť 5.2.
2. Syntax
Oficiálna syntax λ-kalkulu je pomerne jednoduchá; je obsiahnutá v nasledujúcej definícii.
Definícia Pre abecedu jazyka λ-kalkulu berieme ľavé a pravé zátvorky, ľavé a pravé hranaté zátvorky, symbol „λ“a nekonečnú množinu premenných. Trieda λ-výrazov je definovaná induktívne takto:
Každá premenná je λ-term.
Ak M a N sú termíny λ, potom je to aj (MN).
Ak M je λ-člen a x je premenná, potom (λ x [M]) je λ-člen.
Pod pojmom „termín“sa vždy myslí „termín X“. Pojmy vytvorené podľa pravidla (2) sa nazývajú aplikačné podmienky. Termíny vytvorené podľa pravidla (3) sa nazývajú abstrakčné termíny.
Ako je bežné pri zaobchádzaní s formálnymi jazykmi, ktoré majú zoskupovacie symboly (v našom prípade ľavá a pravá zátvorka), niektoré zátvorky sa vynechajú, keď je to bezpečné (to znamená, keď ich možno znova zaviesť iba jedným rozumným spôsobom).). Spojenie viac ako dvoch termínov λ je prísne vzaté nezákonné. Aby sme sa vyhli tediu, že vždy budeme písať všetky potrebné zátvorky, prijímame nasledujúcu konvenciu:
Konvencia (priradenie vľavo): Ak sú vedľa seba viac ako dva termíny M 1 M 2 M 3 … M n, môžeme získať chýbajúce zátvorky priradením zľava: čítanie zľava doprava, skupina M 1 a M 2 spolu, získa sa (M 1 M 2) M 3 … M n; potom skupina (M 1 M 2) s M 3: ((M 1 M 2) M 3) … M n, a tak ďalej.
Konvencia tak poskytuje jedinečné čítanie ľubovoľnej postupnosti X-výrazov, ktorých dĺžka je väčšia ako 2.
2.1 Premenné, viazané a bezplatné
Funkcia A v abstrakčnom termíne (A x [M]) je taká, že viaže premennú, ktorá sa objavuje bezprostredne za ňou v termíne M. A je teda analogické s univerzálnymi a existenciálnymi kvantifikátormi ∀ a ∃ logiky prvého poriadku. Analogicky je možné definovať pojmy voľná a viazaná premenná očakávaným spôsobom nasledovne.
Definícia Syntaktické funkcie FV a BV (pre „voľnú premennú“a „viazanú premennú“) sú definované na množine λ-výrazov štruktúrnou indukciou, takže:
zadarmo
Bound
Pre každú premennú x, FV (x) = {x}.
Pre každý termín M a každý termín N, FV (MN) = FV (M) ∪ FV (N).
Pre každú premennú x a každý člen M, FV (A x [M]) = FV (M) - {x}.
Pre každú premennú x, BV (x) = ∅.
Pre každý termín M a každý termín N, BV (MN) = BV (M) ∪ BV (N).
Pre každú premennú x a každý člen M, BV (A x [M]) = BV (M) ∪ {x}.
Ak FV (M) = ∅, potom sa M nazýva kombinator.
Doložka (3) v týchto dvoch definíciách podporuje zámer, že λ viaže premenné (zabezpečuje, že nie sú zadarmo). Všimnite si rozdiel medzi BV a FV pre premenné.
Ako je to typické v iných predmetoch, v ktorých sa objavujú koncepty, ako napríklad logika prvého poriadku, treba si dať pozor na túto otázku; príležitostný prístup k substitúcii môže viesť k syntaktickým ťažkostiam. [1] Môžeme obhajovať príležitostný prístup prijatím dohovoru, že nás nezaujímajú samy o sebe, ale určité triedy ekvivalencie. Teraz definujeme substitúciu a potom stanovíme konvenciu, ktorá nám umožní vyhnúť sa takým problémom.
Definícia (substitúcia) Píšeme 'M [x: = N]', aby sme označili substitúciu N za výskyty voľných x v M. Presná definícia [2] pomocou rekurzie na množine λ-výrazov je nasledovná: pre všetky pojmy A, B a M a pre všetky premenné x a y definujeme
x [x: = M] ≡ M
y [x: = M] ≡ y (y odlišné od x)
(AB) [x: = M] ≡ A [x: = M] B [x: = M]
(λ x [A]) [x: = M] ≡ λ x [A]
(λ y [A]) [x: = M] ≡ yλ [A [x: = M] (y odlišné od x)
Doložka 1 definície jednoducho hovorí, že ak máme nahradiť M za x a jednáme jednoducho s x, potom je výsledkom iba M. Doložka (2) hovorí, že sa nič nestane, keď pracujeme (iba) s premennou odlišnou od x, ale namiesto x musíme niečo nahradiť. Doložka (3) hovorí, že substitúcia sa bezpodmienečne distribuuje do aplikácií. Ustanovenia 4 a 5 sa týkajú podmienok abstrakcie a paralelných ustanovení 1 a 2 (alebo skôr ustanovení 2 a 1 v opačnom poradí): Ak je viazaná premenná z abstrakčného termínu λ z [A] je identická s premennou x, pre ktorú máme vykonať substitúciu, potom nevykonávame žiadnu substitúciu (tj substitúciu „zastávky“). Toto je v súlade s úmyslom, že M [x: = N] má označovať substitúciu N za výskyty voľných x v M. Ak M je abstrakčný člen λ x [A], ktorého viazaná premenná je x, potom sa v M nevyskytuje voľne, takže nie je čo robiť. Toto vysvetľuje článok 4. Klauzula (5) nakoniec hovorí, že ak sa viazaná premenná abstrakčného členu líši od x, potom aspoň x má „šancu“, že sa v abstrakčnom termíne vyskytne voľne a substitúcia pokračuje do tela termín abstrakcie.
Definícia (zmena viazaných premenných, a-konvertibilita, konvencia nezachytávania o p-konverzii) Výraz N sa získa z termínu M zmenou viazaných premenných, ak zhruba akýkoľvek abstrakčný člen λ x [A] vo vnútri M má boli nahradené λ y [A [x: = y].
Povedzme, že výrazy M a N sú konvertibilné na a, ak existuje sekvencia zmien viazaných premenných počnúc M a končiac N.
Nakoniec súhlasíme, že keď píšeme
'(λ x [M]) N sa redukuje na M [x: = N]',
požadujeme, aby sa žiadna premenná vyskytujúca sa voľne v N neviazala po jej nahradení do M.
Zhruba musíme dodržiavať zásadu, že voľné premenné by mali zostať voľné; ak hrozí, že výskyt premennej bude viazaný substitúciou, jednoducho vykonajte dostatok a-konverzií, aby ste sa vyhli problému. Ak to nezabúdame, môžeme pracovať s A-kalkulmi bez obáv z týchto nepríjemných syntaktických ťažkostí.
Syntax A-počtu je pomerne flexibilná. Dá sa vytvoriť najrôznejšie pojmy, dokonca aj samoaplikácie ako xx. Takéto výrazy sa na prvý pohľad javia ako podozrivé; jeden by mohol mať podozrenie, že používanie takýchto výrazov by mohlo viesť k nekonzistentnosti, av každom prípade by sa dalo nájsť nástroj, ktorým by sa takéto podmienky mohli zakazovať. Keby sme videli funkcie a množiny usporiadaných párov určitého druhu, znamenalo by x v xx funkciu (množinu usporiadaných párov), ktorá obsahuje ako prvok pár (x, y), ktorého prvý prvok by bol x sám, Žiadny súbor sa však nemôže takto izolovať, aby nedošlo k porušeniu axiómu nadácie (alebo pravidelnosti). Z teoretického hľadiska sú tieto pojmy jednoznačne pochybné. Nižšie nájdete krátky náčrt jedného takého nástroja, teórie typov. V skutočnosti však tieto výrazy nevedú k nekonzistentnosti a slúžia užitočnému účelu v kontexte počtu A. Okrem toho zakazovanie takýchto výrazov, ako je to v teórii typov, neprichádza zadarmo (napr. Stratí sa časť expresie netypovaného λ-kalkulu).
2.2 Kombinátory
Ako je definované vyššie, kombinátor je λ-člen bez voľných premenných. Kombinátory možno intuitívne chápať ako „úplne špecifikované“operácie, pretože nemajú žiadne voľné premenné. Existuje niekoľko kombinátorov, ktoré sa osvedčili v histórii A-počtu; ďalšia tabuľka zdôrazňuje niektoré z týchto špeciálnych kombinátorov. Mohlo by sa uviesť oveľa viac (a samozrejme existuje nekonečne veľa kombinátorov), ale nasledujúce majú stručné definície a preukázali svoju užitočnosť.
Niektoré štandardné termíny λ a kombinátory
názov
Definícia a komentáre
S
λ x [λ y [λ z [xz (yz)]
Nezabúdajte, že „xz (yz)“sa má chápať ako aplikácia (xz) (yz) z xz na yz. S možno teda chápať ako substitučný a aplikovateľný operátor: z 'zasahuje' medzi xay: namiesto použitia x na y aplikujeme xz na yz.
K
λ x [λ y [x]
Hodnota K M je konštantná funkcia, ktorej hodnota pre ľubovoľný argument je jednoducho M.
ja
λ x [x]
Funkcia identity.
B
λ x [λ y [λ z [x (yz)]
Pripomíname, že „xyz“sa má chápať ako (xy) z, takže tento kombinátor nie je funkciou triviálnej identity.
C
λ x [λ y [λ z [xzy] Zamení
argument.
T
λ x [λ y [x]
Pravda je pravdivá. Zhodné s K. Neskôr uvidíme, ako tieto reprezentácie hodnôt pravdy zohrávajú úlohu pri spájaní logiky a λ-kalkulu.
F
λ x [λ y [y]
Pravdivá hodnota nepravdivá.
ω
λ x [xx]
Kombinátor samo-aplikácie
Ω
ωω Samoaplikácia kombinátora samoaplikácie
. Znižuje sa na seba.
Y
λ f [(λ x [f (xx)]) (λ x [f (xx)])]
Curryho paradoxný kombinátor. Pre každý λ-termín X máme:
Y X
⊳
(A x [X (xx)]) (A x [X (xx)])
⊳
X ((A x [X (xx)]) (A x [X (xx)]))
Prvý krok redukcie ukazuje, že Y X sa redukuje na aplikačný termín (Xx [X (xx)]) (Xx [X (xx)]), ktorý sa opakuje v treťom kroku. Tak, Y má kuriózne vlastnosť, že Y X a X (Y X) previesť na spoločného termíne.
Θ
(λ x [λ f [f (xxf)]) (λ x [λ f [f (xxf)])
Turingov kombinátor s pevným bodom. Pre každý λ-termín X sa Θ X zníži na X (Θ X), čo je možné ručne potvrdiť. (Curryho paradoxný kombinátor Y nemá túto vlastnosť.)
Notárske konvencie použité v tejto položke
symboly
Čítanie a komentáre
MN
O uplatnení funkcie M na argument N.
Zvyčajne sa zátvorky používajú na oddelenie funkcie od argumentu, napríklad: „M (N)“. V prípade počtu A a príbuzných sú však zátvorky použité ako zoskupovacie symboly. Preto je bezpečné napísať funkciu a argument vedľa seba.
PQR
Aplikácia funkcie PQ, ktorá je sama o sebe aplikáciou funkcie P na argument Q-to R.
Ak nepoužívame zátvorky na oddelenie funkcií a argumentov, ako rozlišovať výrazy, ktoré zahŕňajú tri alebo viac výrazov, napríklad „PQR“? Pripomeňme náš dohovor, že takýmto úradne nezákonným výrazom rozumieme tak, že pracujeme zľava doprava a vždy uvádzame zátvorky okolo susedných výrazov. „PQR“je teda potrebné chápať ako (PQ) R. 'PQRS' je ((PQ) R) S. Výraz „(PQ) R“nie je jednoznačný; podľa nášho dohovoru je totožný s PQR. Výraz „P (QR)“je tiež výslovne nesporný; líši sa od PQR, pretože ide o aplikáciu P na argument QR (ktorý je sám o sebe funkciou Q na argument R).
(λ x [M])
Termín X, ktorý viaže premennú x v tele výraz M.
Úradný slovník λ-kalkulu sa skladá zo zátvoriek „λ“, ľavého “(„ a pravého “) a zo súboru premenných (predpokladá sa, že sa líši od troch symbolov„ λ “,„ (“a ') „aby sme nemali syntaktický chaos).
Alternatívny zápis. Nie je potrebné do syntaxe zahrňovať dva druhy zoskupovacích symbolov (zátvorky a hranaté zátvorky). Zvyčajne by stačili zátvorky alebo hranaté zátvorky. V tejto položke sa používajú dva druhy zátvoriek kvôli čitateľnosti. Vzhľadom na dva druhy zoskupovacích symbolov by sme mohli ďalej šetriť a vynechať zátvorky z abstrakčných výrazov, takže „(λ x [M])“by sa napísalo ako „λ x [M]“.
Niektorí autori píšu 'λ x. M 'alebo' λ x · M 's bodkou alebo stredovou bodkou oddeľujúcou viazanú premennú od tela abstrakčného členu. Rovnako ako v hranatých zátvorkách sú tieto zariadenia určené na pomoc pri čítaní výrazov λ; zvyčajne nie sú súčasťou oficiálnej syntaxe. (Jeden vidí toto zariadenie používané v predchádzajúcich logických dielach, ako napríklad Principia Mathematica, kde funkcia symbolu. Vo výrazoch ako „∀ x. Φ“znamená, aby sme si prečítali celý vzorec φ ako v rámci rozsahu z ∀ x.)
Niektorí autori píšu abstrakčné termíny bez zariadenia, ktoré by oddeľovalo viazanú premennú od tela: takéto termíny sú zreteľne napísané napríklad „λ xx“, „λ yx“. Cvičenie nie je bez jeho podstaty: je to také stručné, ako si človek môže vyžiadať, a umožňuje ešte jednoduchšiu úradnú syntax λ-kalkulu. Tento postup však nie je bezchybný. Je v λ xyz viazaná premenná x alebo je xy? Názvy premenných sú zvyčajne jednoduché písmená a teoreticky to postačuje. Zdá sa však neprimerane reštriktívne zakazovať prax prideľovania premenných dlhším menám; v skutočnosti také konštrukcie vznikajú prirodzene v počítačových programovacích jazykoch.
V záujme jednotnosti prevezmeme v tejto položke zápis v hranatých zátvorkách. (Mimochodom, tento zápis sa používa v (Turing, 1937).)
M [x: = A]
A-člen, ktorý sa získa nahradením A-termínu A za všetky výskyty x vo vnútri M.
V literatúre o λ-kalkuloch a príbuzných predmetoch nájdete ohromujúcu škálu notácií reprezentujúcich substitúciu:
M [x / A], M [A / x], M xA, M Ax, [x / A] M,…
Ktorý zápis, ktorý sa má použiť ako náhrada, sa zdá byť osobnou záležitosťou. V tejto položke používame lineárny zápis, vyhýbanie horných a dolných indexov. Prax reprezentácie substitúcie ': =' vychádza z počítačovej vedy, kde ': =' sa v niektorých programovacích jazykoch číta ako priradenie hodnoty premennej.
Rovnako ako v hranatých zátvorkách používaných na písanie abstrakčných výrazov, hranaté zátvorky používané na písanie substitúcie nie sú oficiálne súčasťou syntaxe λ-kalkulu. M a A sú termíny, x je premenná; M [x: = A] je ďalší výraz.
M ≡ N
A-termíny M a N sú rovnaké: chápané ako sekvencie symbolov, M a N majú rovnakú dĺžku a zodpovedajúce symboly sekvencií sú identické.
Syntaktický vzťah identity ≡ nie je súčasťou oficiálnej syntaxe λ-kalkulu; tento vzťah medzi λ-výrazmi patrí do metatória λ-počtu. Je zrejmé, že ide o pomerne prísny pojem rovnosti medzi podmienkami λ. Nie je to tak (ak xay sú odlišné premenné), že λ x [x] ≡ λ y [y], aj keď sa tieto dva pojmy jasne „správajú“rovnakým spôsobom v tom zmysle, že obidva sú výrazmi operácia identifikácie x ⇒ x. Neskôr vyvinieme formálne teórie rovnosti λ-termov s cieľom zachytiť túto intuitívnu rovnosť λ x [x] a λ y [y].
3. Stručná história λ-kalkulu
λ-počet vznikol zo štúdia funkcií ako pravidiel. Už základné zložky tohto subjektu sa dajú nájsť v priekopníckej práci Frege (Frege, 1893). Frege, ako sme to už uviedli vyššie, Frege poznamenal, že pri štúdiu funkcií postačuje zamerať sa na unárne funkcie (tj funkcie, ktoré majú presne jeden argument). (Postup prezerania operácie s viacerými aritami ako sledu abstrakcií, ktoré vedú k ekvivalentnej unárnej operácii, sa nazýva currying operácie. Možno by bolo historicky presnejšie nazvať operáciu fregeing., ale v označení matematických myšlienok často dochádza k justičným omylom.) V dvadsiatych rokoch matematik Moses Schönfinkel túto tému ďalej študoval v tzv. kombinátoroch. Ako bolo zvykom v prvých dňoch predmetu, Schönfinkel sa zaujímal o druhy transformácií, ktoré človek vidí vo formálnej logike, a jeho kombinátory boli zamýšľané ako príspevok k základom formálnej logiky. Analogicky so znížením, ktoré je možné vidieť v klasickej výrokovej logike pomocou Shefferovej mŕtvice, Schöfinkel preukázal úžasný výsledok, že všetky funkcie (v zmysle všetkých transformácií) by mohli byť dané ako kombinátory K a S; neskôr uvidíme definíciu týchto kombinátorov.
Veta Pre každý člen M tvorený K a S a premennou x existuje pojem F (zostavený iba z K a S), takže môžeme odvodiť F x = M.
(Dôkaz, že tieto dve stačia na reprezentáciu všetkých funkcií, je nad rámec tohto záznamu. Pre ďalšiu diskusiu pozri záznam o kombinovanej logike.) Jeden môže dokázať konštruktívne teóriu: existuje algoritmus, ktorý vzhľadom na M vytvára požadované F. Cirkev to nazvala F 'λ x [M]' (Church, 1932). [3] Z tohto hľadiska môže byť β-pravidlo odôvodnené: ak „λ x [M]“má byť funkciou F, ktorá spĺňa F x = M, potom λ x [M] x by sa malo transformovať na M. Toto je len zvláštny prípad všeobecnejšieho princípu, že pre všetky N (λ x [M]) N by sa mal transformovať na M [x: = N].
Aj keď dnes máme jasnejšie vymedzené systémy abstrakcie a prepisovania, v počiatkoch boli λ-kalkul a kombinačná logika (à la Schönfinkel) viazané na skúmanie základov matematiky. V rukách spoločnosti Curry, Church, Kleene a Rosser (niektorí z priekopníkov v predmete) sa pozornosť sústredila na definovanie matematických objektov a vykonávanie logického zdôvodnenia v rámci týchto nových systémov. Ukázalo sa, že tieto prvotné pokusy o tzv. Illatívny A-počet a kombinatickú logiku boli nekonzistentné. Curry izoloval a vyleštil nesúlad; výsledok je teraz známy ako Curryho paradox. Pozri záznam o Curryho paradoxe a dodatok B z (Barendregt, 1985).
A-kalkul si získava osobitné miesto v histórii logiky, pretože bol zdrojom prvého nerozhodnuteľného problému. Problém je: vzhľadom na λ-výrazy M a N určte, či M = N. (Teória rovnačného zdôvodnenia λ-výrazov ešte nebola definovaná; definícia príde neskôr.) Tento problém sa ukázal byť nerozhodnuteľný.
Ďalším počiatočným problémom v prípade počtu A bolo to, či je vôbec konzistentný. V tejto súvislosti nekonzistentnosť znamená, že všetky termíny sú rovnaké: jeden je možné zredukovať na ľubovoľný λ-termín M na ktorýkoľvek λ-termín N. To, že tomu tak nie je, je skorým výsledkom λ-kalkulu. Spočiatku mali výsledky výsledky preukazujúce, že určité pojmy neboli vzájomne zameniteľné (napr. K a S); neskôr, oveľa silnejší výsledok, takzvaná Church-Rosserova veta, pomohol objasniť β-konverziu a mohol byť použitý na poskytnutie rýchlych dôkazov o neprekonateľnosti celých tried λ-výrazov. Podrobnejšia diskusia o konzistentnosti je uvedená nižšie.
A-počet bol trochu nejasný formalizmus až do šesťdesiatych rokov, kedy sa nakoniec našla „matematická“sémantika. Objasnil sa aj jeho vzťah k programovacím jazykom. Dovtedy boli iba modely λ-kalkulu „syntaktické“, to znamená, že boli vytvorené v štýle Henkinovej a pozostávali z tried ekvivalencie λ-výrazov (pre vhodné pojmy ekvivalencie). Aplikácie v sémantike prirodzeného jazyka vďaka vývoju Montagueho a ďalších lingvistov pomohli „šíriť slovo“o tejto téme. Odvtedy má A-kalkul uznávané miesto v matematickej logike, informatike, lingvistike (pozri napr. Heim a Kratzer 1998) a príbuzných odboroch.
4. Zníženie
K dispozícii sú rôzne pojmy redukcie pre λ-termíny, ale hlavnou je redukcia β-redukcie, ktorú sme už videli predtým. Skôr sme používali zápis „⊳“; môžeme byť presnejší. V tejto časti sa zaoberáme β-redukciou a niektorými rozšíreniami.
Definícia (jednostupňová β-redukcia ⊳ β, 1) Pre λ-termíny A a B hovoríme, že Ap β-redukuje v jednom kroku na B, napísané A ⊳ β, 1 B, len v prípade, že existuje (výskyt) a) podtrieda C A, premennej xa a X- termíny M a N tak, že C ≡ (Xx [M]) N a B je A s výnimkou toho, že výskyt C v A je nahradený M [x: = N].
Tu je niekoľko príkladov β-redukcie:
Premenná x sa n-redukuje na nič. (Nemá správny tvar: je to jednoducho premenná, nie aplikačný termín, ktorého ľavá strana je abstrakčným termínom.)
(lax [x]) a p, la.
Ak x a y sú odlišné premenné, potom (λ x [y]) a ⊳ β, 1 y.
Termín λ ([x x [(λ y [xy]) a]) bp-redukuje v jednom kroku na dva rôzne termíny λ:
(λ x [(λ y [xy]) a]) b ⊳ β, 1 (λ y [by]) a
a
(λ x [(λ y [xy]) a]) b ⊳ β, 1 (λ x [xa]) b
Ďalej je možné skontrolovať, či sa tieto dva výrazy p-redukujú v jednom kroku na bežný výraz: ba. Máme teda:
(λ y [by]) a
↗
↘
(λ x [(λ y [xy]) a]) b
ba
↘
↗
(A x x [xa]) b
Ako pri každom binárnom vzťahu, aj tu možno klásť veľa otázok o vzťahu ⊳ β, 1, ktorý sa drží medzi λ-členmi, a jeden môže definovať rôzne odvodené pojmy ako terms β, 1.
Definícia A - redukčná sekvencia od A-termínu A do X-termínu B je konečná sekvencia s 1, … s n z X-termínov začínajúcich A, končiacich B, a ktorej susedné pojmy (s k, s k +1) spĺňajú vlastnosti, ktoré s k ⊳ β, 1 s k +1.
Všeobecnejšie povedané, akákoľvek sekvencia s -finit alebo nekonečná začínajúca A-termom A je označovaná ako p-redukčná sekvencia začínajúca na A za predpokladu, že susediace výrazy (s k, s k +1) z spĺňajú vlastnosti, ktoré s k ⊳ β, 1 s k +1.
Pokračujúc s p-redukciou z príkladu 1 neexistujú vôbec žiadne p-redukčné sekvencie začínajúce premennou x.
Pokračovanie s p-redukciou z príkladu 2, dvojdobej sekvencie
(λ x [x]) a, a
je p-redukčná sekvencia od (A x [x]) a do a. Ak je a premenná, potom táto p-redukčná sekvencia nemôže byť predĺžená a neexistujú žiadne ďalšie p-redukčné sekvencie začínajúce (A x [x]) a; tak je sada ß-redukčných sekvencií začínajúcich (Xx [x]) a konečná a neobsahuje žiadne nekonečné sekvencie.
Kombinátor Ω má podivnú vlastnosť, že omega ⊳ beta, 1 w. Každý člen každej ß-redukčnej sekvencie začínajúci na Ω (konečný alebo nekonečný) sa rovná Ω.
Zvážiť termín K Ohmov. Týmto termínom je nekonečne veľa redukčných sekvencií:
K W ⊳ beta, 1
K W ⊳ beta, 1K W ⊳ beta, 1
K W ⊳ beta, 1K W ⊳ beta, 1K W ⊳ beta, 1
K Ω ⊳ beta, 1K Ω ⊳ beta, 1K Ω …
Ak je premenná, je vidieť, že všetky konečné sekvencie zníženie počnúc K si Ohm koniec na a, a tam je presne jeden nekonečný sekvencie redukcie.
Definícia P-redex A -termínu M je (výskyt) subterm M formy (A x [P]) Q. ('redex' pochádza z 'redukovateľnej expresie.) p-redex je jednoducho kandidátom na aplikáciu p-redukcie. Ak tak urobíte, kontraktuje β-redex. Termín je označený ako p-normálna forma, ak nemá p-redexy.
(Môže mať výraz viac ß-normálnych foriem? Odpoveď je doslovne „áno“, ale v podstate je odpoveďou „nie“: Ak M a M 'sú β-normálnymi formami nejakého pojmu, potom M je α-konvertibilné na M ', takže p-normálne formy sú jedinečné až do zmeny viazaných premenných.)
Doteraz sme sa zamerali iba na jeden krok ß-redukcie. Je možné kombinovať viac krokov redukcie p do jedného tak, že sa uskutoční prechodné uzavretie vzťahu ß, 1.
Definícia Pokiaľ ide o A-B, jeden hovorí, že Ap - redukuje na B, napísaný AB - B, ak buď ABB, alebo ak existuje konečná sekvencia beta-redukcie od A po B.
Definícia Termín M má p-normálne formy, ak existuje termín N tak, že N je v beta-normálnej zaznamenanie M ⊳ beta N.
Redukovateľnosť, ako je definovaná, je jednosmerný vzťah: vo všeobecnosti nie je pravda, že ak A ⊳ β B, potom B ⊳ β A. V závislosti od účelu človeka však možno budete chcieť považovať A a B za rovnocenné, ak sa A zníži na B alebo B zníži na A. V opačnom prípade činí s ohľadom na reflexívne, symetrická a tranzitívne uzáver vzťahu ⊳ p, 1,.
Definícia Pre λ-termíny A a B hovoríme, že A = β B, ak buď A ≡ B alebo ak existuje sekvencia s 1,… s n začínajúca A, končiaca B, a ktorej susedné pojmy (s k, s k +1) sú také, že buď s k ⊳ β, 1 s k +1 alebo s k +1 ⊳ β, 1 s k.
4.1 Iné pojmy redukcie
Doteraz sme vyvinuli teóriu p-redukcie. Toto nie je v žiadnom prípade jediný pojem redukcie, ktorý je k dispozícii v prípade počtu A. Okrem β-redukcie je štandardným vzťahom medzi λ-výrazmi η-redukcia:
Definícia (jednostupňová η-redukcia) Pokiaľ ide o λ-termíny A a B, hovoríme, že App sa v jednom kroku zmenší na B, napísané A ⊳ βη , 1 B, len v prípade, že existuje (výskyt a) subterm C z A, premenná xa a X-pojmy M a N také, že buď
C ≡ (λ x [M]) N a B je A s výnimkou toho, že výskyt C v A je nahradený M [x: = N]
alebo
C ≡ (λ x [M x]) a B je A s výnimkou toho, že výskyt C v A je nahradený M.
Prvá veta definície ⊳ βη , 1 zaisťuje, že vzťah rozširuje vzťah jednostupňovej β-redukcie. Ako sme to urobili pre vzťah jednostupňovej β-redukcie, môžeme prehrať vývoj pre η-redukciu. Jeden má teda predstavu η-redex a od ⊳ η, 1 je možné definovať vzťah ⊳ η medzi λ-termínmi ako symetrické a tranzitívne uzavretie ⊳ η, 1, ktoré zachytáva nula alebo viac krokov η-redukcie. Potom jeden definuje = η ako symetrické a prechodné uzavretie ⊳ η.
Ak A ⊳ η, 1 B, potom je dĺžka B prísne menšia ako dĺžka A. Preto nemôžu existovať nekonečné η-redukcie. Toto nie je prípad p-redukcie, ako sme videli vyššie v príkladoch 3 a 4 p-redukcie.
Je možné kombinovať pojmy redukcie. Jednou užitočnou kombináciou je zmiešanie p- a η-redukcie.
Definícia (jednostupňová redukcia βη) λ x [M x] ⊳ η , 1 M a (A x [M]) N ⊳ βη , 1 M [x: = N]. A-termín Ap-redukuje sa v jednom kroku na X-termin B iba v prípade, že sa A-redukuje na B v jednom kroku alebo A-redukuje na B v jednom kroku.
Opäť je možné prehrať základné pojmy redukcie, ako sme to urobili pre β-redukciu, pre tento nový pojem redukcie βη.
4.2 Stratégie znižovania
Pripomeňme si, že výraz sa označuje ako p-normálny tvar, ak nemá p-redexy, to znamená subtermy tvaru (A x [M]) N. Pojem má p-normálnu formu, ak sa dá zredukovať na výraz v p-normálnej forme. Malo by byť intuitívne jasné, že ak má výraz p-normálnu podobu, potom ho nájdeme úplným kontrahovaním všetkých všetkých p-redexov tohto výrazu, potom vyčerpávajúcim kontraktovaním všetkých p-redexov všetkých výsledných výrazov atď. Hovoriť, že výraz má β-normálnu formu, znamená povedať, že toto slepé hľadanie jedného sa nakoniec skončí.
Slepé vyhľadávanie β-normálnych foriem nie je uspokojivé. Okrem toho, že je esteticky nepríjemný, môže byť celkom neefektívny: nemusí byť potrebné vyčerpávať všetky p-redexy. Hľadá sa stratégia - najlepšie porovnateľná - na nájdenie p-normálnej formy. Problémom je efektívne rozhodnúť sa, či existuje viac p-redexov jedného termínu, ktoré by sa mali obmedziť.
Definícia Stratégia ß-redukcie je funkcia, ktorej doménou je množina všetkých λ-výrazov a ktorej hodnota na termíne M, ktorý nie je v β-normálnej forme, je redexterterterm M, a ktorej hodnota na všetkých výrazoch M je v β-normále forma je jednoducho M.
Inými slovami, stratégia redukcie ß vyberie vždy, keď má výraz viac ß-redexov, s ktorými z nich sa má uzavrieť zmluva. (Ak je výraz v β-normálnej forme, potom sa nič neurobí, a preto v definícii ß-redukčnej stratégie požadujeme, aby nezmenil žiadny výraz v β-normálnej forme.) Jeden môže predstavovať stratégiu s ako vzťah ⊳ s na lambda-podmienok, s tým, že M ⊳ s N za predpokladu, že M je získaný z M v jednom kroku drží stratégie S. Pri pohľade ako vzťahy, stratégia predstavujú subrelation z ⊳ beta, 1, Stratégia ß-redukcie môže alebo nemusí mať vlastnosť, že dodržiavanie stratégie zabezpečí, že (prípadne) dosiahneme β-normálnu formu, ak taká existuje.
Definícia A-redukčná stratégia S je normalizovaná, ak pre všetky A-členy M, ak M má p-normálnu formu N, potom sekvencia M, S (M), S (S (M)), … končí na N.
Niektoré stratégie redukcie β sa normalizujú, iné nie.
Stratégia, ktorá sa nachádza úplne vpravo, podľa ktorej sa vždy rozhodneme redukovať najvrchnejšiu β-redex (ak existujú β-redexy), nie je normalizovaná. Zoberme si napríklad termín KIω. Tento termín má dva p-redexes: sám, a W (ktorý, stiahnutie, je termín (λx [XX]) (λx [XX])). Prácou s ľavými β-redexami môžeme β-redukciu KIω na I v dvoch krokoch. Ak budeme trvať na práci s β-redexom ω, ktorý je úplne vpravo, znížime KIω na KI (ωω), potom KI (ωωω),….
Stratégia úplne vľavo, podľa ktorej sa vždy rozhodneme znížiť ľavý β-redex (ak existujú β-redexy), je normalizovaná. Dôkaz o tejto skutočnosti presahuje rozsah tohto záznamu; pozri (Barendregt, 1985, oddiel 13.2), kde nájdete podrobnosti.
Po definovaní stratégie znižovania je prirodzené sa pýtať, či ju možno vylepšiť. Ak má výraz p-normálnu formu, stratégia objaví normálnu formu; ale mohla by existovať kratšia sekvencia p-redukcie, ktorá dosiahne rovnakú normálnu formu (alebo výraz, ktorý je a-konvertibilný na túto normálnu formu)? To je otázka optimality. Definovanie optimálnych stratégií a preukázanie, že sú optimálne, je vo všeobecnosti oveľa zložitejšie ako jednoduché definovanie stratégie. Viac informácií nájdete v (Barendregt, 1984, kapitola 10).
V záujme konkrétnosti sme diskutovali iba o stratégiách redukcie β. Ale vo vyššie uvedených definíciách je pojem redukcie p iba jednou z možností. Pre akúkoľvek predstavu o redukcii máme pridruženú teóriu stratégií redukcie R a pre R môžeme prehrať problémy normalizácie, optimality atď.
5. λ-teórie
Už sme diskutovali o tom, ako je A-počet intencionálnou teóriou funkcií. Ak v náročnom duchu chápeme λ-termíny ako opisy, ako by sme mali zaobchádzať s rovnosťou λ-termov? K dispozícii sú rôzne prístupy. V tejto časti sa zaoberajme vzťahom rovnosť = ako primitívnym, nedefinovaným vzťahom, ktorý drží dva termíny λ, a skúste axiomatizovať vlastnosti, ktoré by rovnosť mala mať. Úlohou je identifikovať axiómy identity a sformulovať vhodné pravidlá dedukcie týkajúce sa rovnosti λ-podmienok.
Niektoré zjavné vlastnosti rovnosti, ktoré nemajú nič spoločné s počtom A, sú nasledujúce:
Reflexivita, symetria a transitivita rovnosti λ-termov ako pravidiel inferencie
reflexivita
symetria
tranzitívnosti
X = Y
X = YY = Z
X = X
Y = X
X = Z
Ako je štandardné v teórii dôkazov, spôsob, ako si prečítať tieto pravidlá dedukcie, je to, že nad horizontálnym pravidlom - sú priestory pravidla (ktoré sú rovnicami) a rovnica pod horizontálnym pravidlom je uzavretím pravidla dedukcie. V prípade pravidla reflexivity nie je nič napísané nad horizontálnym pravidlom. Takýto prípad chápeme tak, že hovoríme, že pre všetky podmienky X môžeme odvodiť rovnicu X = X zo žiadnych priestorov.
5.1 Základná teória λ
Tri pravidlá dedukcie uvedené v predchádzajúcej časti upravujúce rovnosť nemajú nič spoločné s počtom λ. Nasleduje zoznam odvodzovacích pravidiel, ktoré sa týkajú nedefinovaného pojmu rovnosti a dvoch operácií budovania termínov λ-kalkulu, aplikácie a abstrakcie.
Pravidlá usudzovania týkajúce sa rovnosti pri uplatňovaní a odoberania
M = N
M = N
M = N
AM = AN
MA = NA
λ x [M] = λ x [N]
Tieto pravidlá vyvodzovania hovoria, že = je kongruenčný vzťah k množine λ-výrazov: „zachováva“tak operácie budovania termínov použitia, ako aj abstrakcie.
Posledné pravidlo odvodenia, β-konverzia, je najdôležitejšie:
β
(λ x [M]) A = M [x: = A]
Rovnako ako v prípade pravidla reflexivity pravidlo β nemá žiadne predpoklady: pre každú premennú x a akékoľvek výrazy M a A je možné odvodiť rovnicu (λ x [M]) A = M [x: = A] v ktoromkoľvek bode v formálna derivácia v teórii λ.
5.2 Rozšírenie základnej teórie λ
K dispozícii je niekoľko rozšírení na λ. Zoberme si napríklad pravidlo (η), ktoré vyjadruje pravidlo η-redukcie ako pravidlo dedukcie:
(η)
X x [M x] = M
Pravidlo η nám hovorí, že určitý druh abstrakcie je otiose: je bezpečné identifikovať M pomocou funkcie, ktorá pri argumente x platí od M do x. Týmto pravidlom tiež vidíme, že všetky pojmy sú efektívne funkčné. Človek môže intuitívne zdôvodniť toto pravidlo pomocou princípu β-redukcie.
(Ext)
M x = N x
za predpokladu, x ∉ FV (M) ∪ FV (N)
M = N
Je možné vidieť pravidlo Ext ako druh zovšeobecňovacieho princípu. Ak sme odvodili, že M x = N x, ale x čísla ani M, ani N, potom sme účinne preukázali, že M a N sú si podobné. Porovnajte tento princíp s princípom univerzálnej zovšeobecnenia v logike prvého poriadku: ak sme odvodili φ (x) z množiny Γ hypotéz, v ktorých x nie je zadarmo, potom môžeme dospieť k záveru, že Γ odvodzuje ∀ x φ.
Ďalší produktívny princíp v λ-kalkulu nám umožňuje identifikovať pojmy, ktoré „konajú“rovnako:
(co)
Pre všetky pojmy x, M x = N x
M = N
Pravidlo ω má nekonečne veľa hypotéz: za predpokladu, že M x = N x, bez ohľadu na to, čo x môže byť, potom môžeme usúdiť, že M = N. Pravidlo ω je analógom v λ-kalkulu inferenčného pravidla pod rovnakým menom v teórii formálnych čísel, podľa ktorého je možné dospieť k všeobecnému vzorcu ∀ x φ za predpokladu, že má dôkazy pre φ (x: = 0), φ (x: = 1),…. Všimnite si, že na rozdiel od pravidla Ext nenastáva podmienka, že x sa nevyskytuje voľne v M alebo N.
6. Konzistentnosť počtu A
Je λ-počet konzistentný? Otázka nemusí byť dobre položená. A-počet nie je logikou zdôvodňovania tvrdení; nejestvuje zjavná predstava o protirečení (⊥) ani o metóde tvorby absurdných tvrdení (napr. p ∧ ¬ p). Teda „nekonzistentnosť“počtu A nemôže znamenať, že ⊥ alebo nejaký vzorec rovný ⊥ je možné odvodiť. K dispozícii je však vhodný pojem „konzistentný“. Intuitívne je logika nekonzistentná, ak nám to umožňuje odvodiť príliš veľa. Teória λ je teória rovníc. Môžeme teda považovať nekonzistentnosť λ, čo znamená: všetky rovnice sú odvoditeľné. Takáto vlastnosť, ak by platila pre λ, by jasne ukázala, že λ je málo užitočná ako formálna teória.
Rané formulácie myšlienky A-počtu od A. Church boli skutočne nekonzistentné; pozri diskusiu (Barendregt, 1985, dodatok 2) alebo (Rosser, 1985). Aby sme prijali konkrétny problém: ako vieme, že rovnica K = I nie je veta o λ ? Tieto dva pojmy sú očividne intuitívne odlišné. K je funkciou dvoch argumentov, zatiaľ čo ja je funkciou jedného argumentu. Ak by sme dokázali, že K = I, potom by sme dokázali, že KK = IK, odkiaľ KK = K bude veta λ, spolu s mnohými ďalšími rovnicami, ktoré nás považujú za intuitívne neprijateľné. Keď však skúmame formálnu teóriu, ako je λ, intuitívna neprijateľnosť v žiadnom prípade neznamená nedotknuteľnosť. Chýba hlbšie pochopenie β-redukcie.
Skorý výsledok, ktorý dal také porozumenie, sa nazýva Cirkev-Rosserova veta:
Veta (Church-Rosser) Ak P β β Q a P ⊳ β R, potom existuje pojem S tak, že Q ⊳ β S aj R β β S.
(Dôkaz tejto vety je dosť netriviálny a značne presahuje rámec tohto záznamu.) Výsledkom je hlboký fakt o redukcii β. Hovorí sa, že bez ohľadu na to, ako sa odkloníme od P pomocou β-redukcií, vždy sa môžeme opäť zblížiť do spoločného termínu.
Cirkevná-Rosserova veta nám okrem iného dáva, že obyčajný λ-počet - to znamená, teória λ rovníc medzi λ-výrazmi - je konzistentný v tom zmysle, že nie všetky rovnice sú odvoditeľné.
Na ilustráciu môžeme použiť Cirkev-Rosserovu vetu na vyriešenie predchádzajúceho problému preukázania, že dva pojmy K a I nie sú identifikované pomocou λ. Tieto dva termíny sú v beta-normálnej forme, takže z nich neexistujú vôbec žiadne p-redukčné sekvencie. Ak K = I boli teorém Á, potom by termín M, z ktorej je β-redukcia cesta ako I a K. Cirkev-Rosserova veta potom naznačuje, že obe cesty, ktoré sa od M odlišujú, sa dajú spojiť. To je však nemožné, pretože K a I sú odlišné β-normálne formy.
Cirkev-Rosserova veta predpokladá existenciu ß-redukčných sekvencií začínajúcich od K a od I, ktoré končia spoločným termínom. Ale nie sú tam žiadne sekvencie β-redukčné vôbec, ktoré začína od Aj, pretože je v beta-normálnej forme, a podobne pre K.
Veta λ je konzistentná v tom zmysle, že nie každá rovnica je veta.
Na preukázanie vety je postačujúce vytvoriť jednu nedochádzajúcu rovnicu. Už sme prešli príkladom: použili sme Church-Rosserovu vetu, aby sme ukázali, že rovnica K = I nie je veta o λ. O týchto dvoch výrazoch samozrejme nie je nič zvláštne. Významnou zovšeobecnenie tohto výsledku je k dispozícii: ak je M a N v beta-normálnej forme, ale M je odlišný od dusíka, potom rovnica M = N nie je teorém lambda. (Táto jednoduchá podmienka nedotknuteľnosti obvykle neplatí, ak k λ pridáme ďalšie pravidlá dedukcie.)
Teórie λη a λω sú rovnako konzistentné. Dá sa dokázať, že tieto výsledky konzistencie sú v súlade s dôkazom konzistencie pre λ rozšírením vety Church-Rosserovej na širšie zmysly odvoditeľnosti týchto teórií.
7. Sémantika A-počtu
Aj keď je λ-kalkul „o“výpočte funkciami substitúciou hodnôt argumentmi, tento jednoduchý pohľad nemôže podporovať sémantiku pre (atypický) λ-kalkul, ak „funkciou“rozumieme, ako je štandard v teórii množín, vzťah R taký, že pre každý pár (x, y) a (x, z) v R s rovnakou prvou zložkou x máme y = z. Pre množiny X a Y nech X Y označuje množinu funkcií, ktorých doménou je Y, as hodnotami v X. Intuitívne, ak X je doménou interpretácie A-počtu, potom by X malo byť v istom zmysle izomorfné pre X Xpretože doména by mala byť uzavretá pod abstrakciou (rovnako ako aplikácia). Brať doslovne, aj keď to izomorfismus je nemožné, pretože mohutnosť X je vždy striktne menšia ako mohutnosť X X.
Ak sa zaujíma iba o existenciu nejakého modelu λ-kalkulu, ktorého doména nemusí nevyhnutne pozostávať z funkcií, možno ich nájsť rôznymi známymi „syntaktickými“konštrukciami, ktoré zahŕňajú teóriu λ, na rozdiel od dobre - známe konštrukcie Henkin. Tieto takzvané termínové modely sú však neuspokojivým riešením otázky, či existujú „matematické“modely počtu A.
Argument kardinality ukazuje, že ak máme mať sémantiku pre λ-počet, interpretácia λ-výrazov nemôže byť jednoducho funkciami v množinovo-teoretickom zmysle slova. Existujú však interpretácie A-počtu. Prvý model, D ∞, bolo zistené, D. Scott; ďalšie modely sa našli neskôr. Tieto modely vyriešiť problém mohutnosť obmedzením domény X výkladu, tak, že v nich, X je vo vhodnom zmysle izomorfné k, priestoru funkcií 'X X.
Jednou z výhod odlišných interpretácií je to, že vidíme rôzne aspekty rovnosti: každý z týchto modelov má odlišný pohľad na to, čo sa λ-termíny identifikujú. Definície D ∞ a iné interpretácie, overenia, či sú skutočne modelmi λ-kalkulu, a charakterizácie λ-teórií týchto modelov sú mimo rozsahu tejto položky; pozri (Barendregt, 1985, kapitola 18) pre podrobnosti.
8. Rozšírenia a variácie
8.1 Kombinovaná logika
Sesterský formalizmus počtu A, ktorý sa vyvinul o niečo skôr, sa zaoberá kombináciami bez premenných. Kombinovaná logika je dokonca ešte jednoduchšia ako počet A, pretože jej chýba pojem variabilnej väzby.
Jazyk kombinačnej logiky je zostavený z kombinátorov a premenných. Existuje určitá flexibilita v ktorej presne kombinátory sú vybrané ako základný, ale niektoré z nich sú štandardné I, K, S, B a C. (Názvy nie sú ľubovolné.)
Podobne ako v prípade počtu A sa kombinovanou logikou zaujíma redukovateľnosť a preukázateľnosť. Hlavné redukčné vzťahy sú:
Combinator
Axiom redukcie
ja
I x = x
K
K xy = x
S
S xyz = xz (yz)
B
B xyz = x (yz)
C
C xyz = xzy
Existuje preklad z počtu A do kombinovanej logiky prekladom. Ukazuje sa, že hoci kombinačnej logike chýba pojem abstrakcie, je možné definovať takúto predstavu a tým simulovať A-počet v kombinačnej logike. Tu je jeden preklad; je definovaný rekurzívne.
pravidlo
vyjadrenie
preklad
podmienka
1
X
X
(Nepodmienené)
2
MN
M * N *
(Nepodmienené)
3
λ x [M]
K M
x sa nevyskytuje voľne v M
4
λ x [x]
ja
(Nepodmienené)
5
λ x [M x]
M
x sa nevyskytuje voľne v M
6
λ x [MN]
B M (λ x [N)] *
x sa nevyskytuje voľne v M
7
λ x [MN]
C (X x [M]) * N
x sa v N nenachádza voľne
8
λ x [MN]
S M * N *
x sa vyskytuje voľne v M aj N
Tento preklad funguje skôr zvnútra, ako zvonku. Pre ilustráciu:
Preklad termínu AY [y], predstaviteľ funkcie identity, je mapovaný týmto prekladom do kombinátora I identity (kvôli pravidlu 4), ako sa očakávalo.
Λ-termín λ x [λ y [x], ktorý nazývame „ K “, je týmto prekladom mapovaný na:
λ x [λ y [x]
≡
⟨Pravidlo 1⟩
λ x [ K x]
≡
⟨Pravidlo 3⟩
K
Λ-termín λ x [λ y [yx], ktorý prepína svoje dva argumenty, je týmto prekladom mapovaný na:
λ x [λ y [yx]
≡
⟨Pravidlo 8⟩
λ x [ C (λ y [y]) * x]
≡
⟨Λ y [y] ≡ Ja, na základe pravidla 4⟩
λ x [ CI x]
≡
⟨Článok 7⟩
B (CI) (λ x [x]) *
≡
⟨(Λ x [x]) * ≡ I, podľa pravidla 4⟩
B (CI) I
Môžeme potvrdiť, že λ-termín λ x [λ y [yx] a preložený kombinačný logický výraz B (CI) I majú analogické aplikačné správanie: pre všetky λ-termíny P a Q máme
(Xx [Xy [yx]) PQ Xa [y P]) QP;
podobne pre všetky kombinatívne logické výrazy P a Q máme
B (CI) I PQ ⊳ (CI) (I P) Q ⊳ I Q (I P) ⊳ Q (I P) ⊳ QP
Môžeme dať len pohľad na kombinatickú logiku; Viac informácií o tejto téme nájdete v časti o kombinovanej logike. Mnohé z problémov, o ktorých sa tu diskutuje pre počet A, majú analógiu v kombinatickej logike a naopak.
8.2 Pridávanie typov
V mnohých kontextoch uvažovania a výpočtov je prirodzené rozlišovať medzi rôznymi druhmi objektov. Tento rozdiel sa zavádza tak, že sa vyžaduje, aby určité vzorce, funkcie alebo vzťahy akceptovali argumenty alebo umožnili nahradenie iba niektorých druhov objektov, a nie iných. Mohli by sme napríklad požadovať, aby sčítanie + čísla ako argumenty. Účinkom tohto obmedzenia je zakázať napríklad pridanie 5 a funkciu identity xx. x. (4). Regulovanie objektov do typov je tiež myšlienka prechodu z (netriedenej alebo jednotriedenej) logiky prvého poriadku k mnohým triedeným logikám prvého poriadku. (Pozri (Enderton, 2001) a (Manzano, 2005), kde nájdete viac informácií o mnohorakej logike prvého poriadku.) V súčasnej podobe nepodporuje λ-kalkul tento druh diskriminácie; akýkoľvek výraz sa môže vzťahovať na akýkoľvek iný výraz.
Je ľahké rozšíriť nerozvetvený λ-kalkul tak, aby rozlišoval medzi rôznymi druhmi objektov. Táto položka sa obmedzuje na λ-počet bez typu. Podrobnejšie informácie o rozšíreniach počtu λ-kalkúl, ktoré dostaneme pri pridávaní typov, nájdete v položkách teória typov a cirkevná teória typov.
9. Aplikácie
9.1 Logika à la
Tu sú dva zmysly, v ktorých je λ-počet spojený s logikou.
9.1.1 Pojmy ako logické konštanty
V tabuľke kombinátorov vyššie sme definovali kombinátory T a F a povedali sme, že slúžia ako reprezentácie v A-kalkulu hodnôt pravdy pravdivé a nepravdivé. Ako tieto pojmy fungujú ako hodnoty pravdy?
Ukazuje sa, že keď človek zaobchádza s λ-kalkulmi ako s nejakým druhom programovacieho jazyka, je možné napísať podmienené výroky „Ak P, potom A, B“jednoducho ako PAB, kde sa samozrejme P, A a B chápu ako výrazy λ., Ak je P ⊳ T, to znamená, že P je „pravda“, potom to tak je
ak- P-én-A -elóza- B: = PAB ⊳ T AB ⊳ A,
(pripomeňte, že podľa definície T ≡ K) a ak P ⊳ F, to znamená, že P je „nepravdivé“, potom
ak-P-én-A-eláza-B: = PAB ⊳ F AB ⊳ B,
(pripomeňme si, že z definície, F ≡ KI), čo je presne to, čo očakávame od pojmu if-then-else. Ak sa P nezníži ani na T, ani na F, potom všeobecne nemôžeme povedať, čo je -P-potom-A-elel-B.
Kódovanie, ktoré sme práve načrtli v súvislosti so niektorými známymi hodnotami pravdy a logickými spojivami klasickej logiky pravdivých tabuliek, nepreukazuje, že λ-počet a klasická logika spolu úzko súvisia. Kódovanie ukazuje len niečo viac ako vložiteľnosť pravidiel výpočtu klasickej logiky pravdivostnej tabuľky do λ-kalkulu. Logika iná ako klasická logika pravdivostnej tabuľky môže byť rovnako zastúpená v kalkulu λ, ak má človek dostatok prepočítateľných zložiek pre danú logiku (napr. Ak je vzťah logických dôsledkov porovnateľný alebo ak je porovnateľný vzťah odvoditeľný atď.)). Viac informácií o výpočte pomocou počtu A nájdete v časti 9.2 nižšie. Podrobnejší vzťah medzi logikou a A-počtom je diskutovaný v nasledujúcej časti.
9.1.2 Typizovaný počet λ-kalkul a korešpondencia Curry-Howard-de Bruijn
Korešpondencia, ktorá sa má tu popísať medzi logikou a A-kalkulom, sa pozoruje pomocou prístroja známeho ako typy. Táto časť načrtáva začiatky vývoja predmetu známeho ako teória typov. Zaujímame sa o vývoj teórie typov, iba ak chceme zviditeľniť takzvanú Curry-Howard-de Bruijnovu korešpondenciu. Podrobnejšie spracovanie možno nájsť v položke teória typov; pozri tiež (Hindley 1997).
Teória typov obohacuje netypovaný λ-počet tým, že vyžaduje, aby boli dané termíny dané typy. V netypovanom λ-kalkulu je aplikácia MN právnym pojmom bez ohľadu na to, čo sú M a N. Takáto sloboda dovoľuje vytvárať takéto termíny ako podozrivé xx a odtiaľ termíny ako paradoxné Combinator Y. Dalo by sa chcieť vylúčiť pojmy ako xx z dôvodu, že x slúži ako funkcia (na ľavej strane aplikácie), ako argument (na pravej strane aplikácie). Teória typov nám poskytuje prostriedky na spresnenie tohto intuitívneho argumentu.
Priradenie typov k pojmom Teória jazyka typu začína (nekonečnou) množinou typových premenných (ktorá sa považuje za disjunktnú zo súboru premenných λ-kalkulu a od samotného symbolu „λ“). Súbor typov sa skladá z typových premenných a operácie σ → τ. Premenné v teórii typov teraz prichádzajú s anotáciou typu (na rozdiel od neoznačených termínových premenných netypovaného λ-kalkulu). Zadané premenné sú vykreslené 'x: σ' intuitívne čítanie je „premenná x má typ σ“. Intuitívne čítanie rozsudku „t: σ → τ“je také, že výraz t je funkciou, ktorá transformuje argumenty typu σ na argumenty typu τ. Priraďovanie typov termínom premenné má pravidlá písania:
(M: σ → τ) (N: σ): τ
a
(λ x: σ [M: τ]): σ → τ
Vyššie uvedené dve pravidlá definujú priradenie typov k aplikáciám a abstrakčným podmienkam. Súbor pojmov teória typov je množina pojmov vytvorených podľa týchto pravidiel formovania.
Vyššie uvedená definícia množiny pojmov teória typov je dostatočná na vylúčenie pojmov ako xx. „Xx“samozrejme nie je napísaný výraz z jednoduchého dôvodu, že mu neboli priradené žiadne typy. Rozumie sa tým, že neexistuje typ σ, ktorý by mohol byť priradený k x tak, že by sa „xx“mohlo legálne označovať ako typovaný výraz. Nemôžeme priradiť premennej typu xa, pretože potom by typ ľavej strany x nebol funkčným typom (tj typom tvaru σ → τ '). Navyše nemôžeme priradiť funkčnému typu xa σ → τ, pretože potom by sa σ rovnalo σ → τ, čo je nemožné.
Ako hlavný príklad uvážte typy, ktoré sú priradené kombinátorom I, K a S:
Combinator
Typ [5]
ja
a → a
K
a → (b → a)
S
a → (b → c) → ((a → b) → (a → c))
(Podrobnejší zoznam nájdete v tabuľke hlavných typov Hindley (1997).) Ak čítame '→' ako implikačné a typové premenné ako výrokové premenné, potom v pravom stĺpci tabuľky rozpoznáme tri známe tautológie. Používaný jazyk je skromný: existujú len výrokové premenné a implikácie; neexistujú žiadne iné spojenia.
V tabuľke je uvedená zaujímavá korešpondencia medzi počtom A. Naozaj je možné, že typy priradené vzorcom, keď sa chápu ako logické vzorce, sú platné? Áno, hoci „platnosť“sa nemusí chápať ako klasická platnosť:
Veta Ak τ je typom nejakého λ-termínu, potom τ je intuitionisticky platná.
Obrátenie tejto vety platí rovnako:
Veta Ak je φ intuitívne platný logický vzorec, ktorého jedinou konektívnou je implikácia (→), potom φ je typ nejakého λ-termínu.
Korešpondencia je viditeľná, keď človek identifikuje intuicionistickú platnosť s odvoditeľnosťou v určitom prirodzenom formalizáte dedukcie. Dôkaz týchto dvoch teórií je uvedený v (Hindley, 1997, kapitola 6).
Korešpondencia vyjadrená predchádzajúcimi dvoma teorémami medzi intuicionálnou platnosťou a typizovateľnosťou je známa ako Curryho-Howard-de Bruijnová korešpondencia po tom, čo si to traja logici všimli nezávisle. Ako je uvedené, korešpondencia je iba medzi výrokovou intuičnou logikou a obmedzuje sa na fragment obsahujúci iba implikovanú spojivovú →. Je možné rozšíriť korešpondenciu aj na ďalšie spojivá a na kvantifikátory, ale najostrejšia korešpondencia je na úrovni fragmentu, ktorý je implicitný. Podrobnosti pozri (Howard, 1980).
9.2 Výpočty
Prírodné čísla je možné jednoduchým spôsobom znázorniť takto:
Definícia (usporiadaná n-tica, prirodzené čísla) Usporiadaný n-tica ⟨a 0, i … n ⟩ z lambda-požiadaviek je definovaný ako λ x [x a 0 i … n]. Jeden potom definuje lambda-term ⌜ n ⌝ zodpovedajúce prirodzené číslo n, ako sú: ⌜0⌝ = I, a pre každé k, k + ⌜ 1⌝ = ⟨ F, ⌜ k ⌝⟩.
Termín λ zodpovedajúci číslu 1 v tomto znázornení je:
⌜1⌝
≡
⟨ F, ⌜0⌝⟩
≡
⟨ F, I ⟩
≡
λ x [x FI]
Termín λ zodpovedajúci číslu 2 v tomto znázornení je:
⌜2⌝
≡
⟨ F, ⌜1⌝⟩
≡
λ x [x F λ x [x FI]
Podobne ⌜3⌝ je λ x [x F λ x [x F λ x [x FI].
K dispozícii sú rôzne reprezentácie prirodzených čísel; táto reprezentácia je iba jedna. [6]
Použitím prísad, ktoré poskytuje A-kalkul, môžu predstavovať všetky rekurzívne funkcie. To ukazuje, že model je presne taký výrazný ako iné modely počítačov, napríklad Turingove stroje a registračné stroje. Priorita sa týka Turingovej definície jeho stroja, ale cirkevný návrh počtu A sa vyvinul takmer v rovnakom čase.
Veta Pre každú rekurzívnu funkciu f arity n existuje λ-termín f * taký, že
pre všetky prirodzené čísla a 1, … a n: f (a 1, i … n) = y práve vtedy, keď lambda ⊢ f * ⟨a 1, i … n ⟩ = y
Dôkaz je uvedený v prílohe.
Pretože trieda rekurzívnych funkcií je adekvátnym zastúpením triedy všetkých vypočítateľných (číselno-teoretických) funkcií, vďaka vyššie uvedenej práci zistíme, že všetky vypočítateľné (číselne teoretické) funkcie môžu byť v A-kalkulu verne zastúpené.
9.3 Vzťahy
Motivácia pre počet A na začiatku záznamu bola založená na čítaní výrazov X ako opisu funkcií. Rozumeli sme teda, že 'x [M]' je (alebo) funkciou, ktorá vzhľadom na x dáva M (ktoré všeobecne, aj keď nie nevyhnutne, zahŕňa x). Nie je však potrebné čítať výrazy λ ako funkcie. Dalo by sa chápať výrazy λ ako označujúce vzťahy a čítali by abstrakčný výraz „λ x [M]“ako unárny vzťah R, ktorý obsahuje argument x len v prípade, že to tak je. Pri relačnom čítaní chápeme aplikačný termín MN ako formu predikcie. Dá sa zmysel týchto pojmov pomocou princípu β-konverzie:
(λ x [M]) a = M [x: = A],
ktorý hovorí, že abstrakčný vzťah λ x [M], predikovaný A, je vzťah získaný zapojením A pre všetky voľné výskyty x vo vnútri M.
Ako konkrétny príklad tohto druhu prístupu k počtu A možno uvažovať o rozšírení logiky prvého poriadku, kde je možné pomocou nových výrazov λ vytvárať nové atómové vzorce nasledujúcim spôsobom:
Syntax: Pre akýkoľvek vzorec φ a akúkoľvek konečnú sekvenciu x 1, …, x n premenných je výraz „λ x 1 … x n [φ]“predikátnym symbolom arity n. Rozšíriť pojem voľných a viazaných premenných (pomocou funkcií FV a BV) takým spôsobom, že
FV (λ x 1 … x n [φ]) = FV (φ) - {x 1, … x n }
a
BV (λ x 1 … x n [φ]) = BV (φ) ∪ {x 1,… x n }
Odpočítanie Predpokladajme ako axiómy univerzálne uzávery všetkých ekvivalencií
λ x 1 … x n [φ] (t 1, … t n) ↔ φ [x 1, … x n: = t 1, … t n]
kde φ [x 1, … x n: = t 1, … t n] znamená súčasné nahradenie výrazov t k premenným x k (1 ≤ k ≤ n).
sémantika Pre štruktúru A prvého poriadku a priradenie prvkov A premenným definujte
⊨ λ x 1 … x n [φ] (t 1, … t n) [s], práve ⊨ φ [x 1, … x n: = t 1, … t n] [s]
Podľa tohto prístupu je možné použiť λ na ošetrenie v podstate ľubovoľného vzorca, dokonca aj zložitého, akoby boli atómy. Princíp β-redukcie vidíme vo deduktívnej a sémantickej časti. To, že tento prístup dodržiava relačné čítanie výrazov λ, je zreteľne viditeľné v sémantike: podľa štandardnej sémantiky Tarskiho štýlu pre logiku prvého poriadku interpretácia vzorca (prípadne s voľnými premennými) označuje skupinu n-tíc prvky štruktúry, pretože meníme priradenie premenných, ktoré premenným priradí prvky štruktúry.
Tento funkčný prístup je možné „internalizovať“. Toto sa deje v prípade rôznych majetkových teórií, formálnych teórií zdôvodňovania vlastností ako metafyzických objektov (Bealer 1982, Zalta 1983, Menzel 1986 a Turner 1987). Tento druh teórie sa používa v určitých metafyzických výskumoch, kde vlastnosti sú metafyzické entity, ktoré sa majú skúmať. V týchto teóriách sú predmetom záujmu metafyzické vzťahy; rovnako ako pridávame výrazy budujúce termíny + a × do formálnych teórií aritmetiky na vytváranie čísel, λ sa používa v teórii vlastností na vytváranie vzťahov. Tento prístup je v rozpore s vyššie uvedeným prístupom. Tam sa k gramatike logiky prvého poriadku pridalo λ, čo z neho urobilo recept na vytvorenie atómových vzorcov; bol to nový operátor výroby receptúr, napríklad ∨ alebo → alebo iných pripojení. V prípade majetkových teórií λ zohráva rolu podobnú + a × vo formálnych teóriách aritmetiky: používa sa na vytváranie vzťahov (ktoré sa v tomto nastavení majú chápať ako určitý metafyzický objekt). Na rozdiel od + a × však λ viaže premenné.
Na ilustráciu toho, ako sa λ používa v tomto prostredí, preverme gramatiku typickej aplikácie (McMichael a Zalta, 1980). Jeden má typicky operátora predikácie (alebo presnejšie skupinu operátorov predikácie) p k (k> 0). V jazyku, v ktorom máme výrazy mary a john a binárny vzťah miluje, môžeme formálne vyjadriť:
John miluje Máriu: miluje (john, mary)
Majetok, ktorý John miluje Mary: λ [miluje (john, mary))] (všimnite si, že λ nezaväzuje žiadne premenné; mohli by sme ju nazvať „vákuovou väzbou“. Takéto vlastnosti možno chápať ako výroky.)
Majetok objektu x, ktorý ho John miluje: λ x [miluje (john, x)].
Majetok, ktorý Máriu miluje niečo: λ [∃ x (miluje (x, mary)))] (ďalší príklad vákuovej väzby, tj. Výrok)
Predikcia vlastnosti x, ktorú John miluje x voči Márii: p 1 (λ x [miluje (john, x)], mary).
(0-ary) predikcia majetku, ktorý John miluje Mary: p 0 (λ x [miluje (john, mary))])).
Vlastnosť objektov xay, ktoré x miluje y: λ xy [miluje (x, y)].
Vlastnosť objektov x, ktoré x miluje sama seba: λ x [miluje (x, x)].
Predikcia vlastností objektov xay, ktoré x miluje y, pre Johna a Máriu (v tomto poradí): p 2 (λ xy [miluje (x, y)], john, mary).
Tieto λ-termíny odôvodňujeme pomocou princípu β-konverzie, ako napríklad:
p n (λ x 1, … X n [A], t 1, …, t n) ↔ A [x 1, … x n: = t 1, … t n]
Formálne je operátor predikcie p k (k +1) -arytový predikátový symbol. Prvý argument je zamýšľaný ako argument λ-term k a zvyšok argumentov je určený ako argument tela λ-term. Vyššie uvedený p-princíp hovorí, že predikcia n-tarych λ-termínov L až n platí presne vtedy, keď telo L drží tieto výrazy.
Ukazuje sa, že v týchto teóriách môžeme alebo nemusíme byť schopní plne sa zaviazať k princípu β-konverzie. V niektorých teóriách nehnuteľností skutočne úplný princíp β-konverzie vedie k paradoxu, pretože keď je zavedený úplný princíp β-konverzie, je možné prehrať argument Russellovho štýlu. V takýchto nastaveniach jeden obmedzuje tvorbu A-vzorcov tým, že vyžaduje, aby telo A-termínu neobsahovalo ďalšie X-výrazy alebo kvantifikátory. Pre ďalšiu diskusiu pozri (Orilia, 2000).
Bibliografia
Baader, Franz a Tobias Nipkow, 1999, Term Rewriting and All That, Cambridge: Cambridge University Press.
Barendregt, HP, 1985, The Lambda Calculus: jeho syntax a sémantika (Štúdie v logike a základy matematiky 103), 2. vydanie, Amsterdam: Severný Holland.
Barendregt, HP, 1993, „Lambda kalkulu s typmi“, v S. Abramsky, D. Gabbay, T. Maibaum a H. Barendregt (ed.), Handbook of Logic in Computer Science, Zväzok 2, New York: Oxford University Stlačte na str. 117 - 309.
Bealer, G., 1982, Quality and Concept, Oxford: Clarendon Press.
van Benthem, Johan, 1998, Manuál intenzívnej logiky, Stanford: Publikácie CSLI.
Church, A., 1932, „Súbor postulátov na založenie logiky“, Annals of Mathematics (2. séria), 33 (2): 346–366.
Cutland, NJ, 1980, Computability, Cambridge: Cambridge University Press.
Doets, Kees a Jan van Eijk, 2004, Haskellova cesta k logike, matematike a programovaniu, Londýn: College Publications.
Enderton, Herbert B., 2001, Matematický úvod do logiky, 2. vydanie, San Diego: Harcourt / Academic Press.
Frege, Gottlob, 1893, Grundgesetze der Arithmetik, Jena: Verlag Hermann Pohle, Band I. Čiastočný preklad ako základné aritmetické zákony, M. Furth (trans.), Berkeley: University of California Press, 1964.
Kleene, Stephen C., 1981, „Pôvod teórie rekurzívnej funkcie“, Annals of the History of Computing, 3 (1): 52–67.
Heim, Irene a Angelika Kratzer, 1998, sémantika v generatívnej gramatike, Malden, MA: Blackwell.
Hindley, J. Roger, 1997, základná teória jednoduchého typu (Cambridge Tracts v teoretickej informatike 42), New York: Cambridge University Press.
Hindley, J. Roger a Jonathan P. Seldin, 2008, Lambda-Calculus and Combinators: Úvod, 2. vydanie, Cambridge: Cambridge University Press.
Howard, W., 1980, „Konštrukčný vzorec typu stavebníctva“, J. Hindley a J. Seldin (ed.), HB Curry: Eseje o kombinovanej logike, Lambda-Calculus a formalizmus, Londýn: Academic Press, s. 479 - 490.
Manzano, Maria, 2005, Rozšírenia logiky prvého poriadku (Cambridge Tracts v teoretickej informatike 19), Cambridge: Cambridge University Press.
McCarthy, John, 1960, „Rekurzívne funkcie symbolických výrazov a ich výpočet pomocou počítača (časť I)“, Komunikácia ACM, 3 (4): 184–195.
McMichael, Alan a Edward N. Zalta, 1980, „Alternatívna teória neexistujúcich objektov“, Journal of Philosophical Logic, 9: 297–313.
Menzel, Christopher, 1986, „Úplná logika vlastností, vzťahov a návrhov druhého rádu bez typov“, technická správa č. CSLI-86-40, Stanford: Publikácie CSLI.
Nederpelt, R., s H. Geuvers a R. de Vriejer (ed.), 1994, Selected Papers on Automath (Štúdie v logike a základy matematiky 133), Amsterdam: North-Holland.
Orilia, Francesco, 2000, „Teória vlastností a teória revízií definícií“, Journal of Symbolic Logic, 65 (1): 212–246.
Partee, Barbara H., s Alice ter Meulen a Robert E. Wall, 1990, Matematical Methods in Linguistics, Berlin: Springer.
Revesz, GE, 1988, Lambda-Calculus, kombinátory a funkčné programovanie, Cambridge: Cambridge University Press; dotlač 2008.
Rosser, J. Barkley, 1984, „Highlights of the History of the Lambda-Calculus“, Annals of the History of Computing, 6 (4): 337–349.
Schönfinkel, M., 1924. „O stavebných kameňoch matematickej logiky“v J. van Heijenoort (ed.), Od Frege po Gödel: Zdrojová kniha v matematickej logike, Cambridge, MA: Harvard University Press, 1967, s. 355 - 366.
Troelstra, AS a H. Schwichtenberg, 2000, Basic Proof Theory (Cambridge Tracts in Theoretical Computer Science 43), 2. vydanie, Cambridge: Cambridge University Press.
Turing, AM, 1937, „Vyčísliteľnosť a λ-definovateľnosť“, Journal of Symbolic Logic, 2 (4): 153–163.
Turner, R., 1987, „Teória vlastností“, Journal of Symbolic Logic, 52 (2): 455–472.
Zalta, E., 1983, Abstraktné objekty: Úvod do axiomatickej metafyziky, Dordrecht: D. Reidel.
Akademické nástroje
ikona sep muž
Ako citovať tento záznam.
ikona sep muž
Ukážku verzie tohto príspevku vo formáte PDF si môžete pozrieť na stránke Friends of the SEP Society.
ikona
Vyhľadajte túto vstupnú tému v projekte Indiana Philosophy Ontology Project (InPhO).
ikona phil papiere
Vylepšená bibliografia tohto záznamu vo PhilPapers s odkazmi na jeho databázu.
Ďalšie internetové zdroje
Lambda kalkulačka, nástroj na prácu s λ-termmi s ohľadom na ich použitie vo formálnej sémantike prirodzeného jazyka.
Lambda Evaluator, na vizualizáciu redukcií. Štandardné kombinátory a cirkevné číslice sú preddefinované.
Pracovný stôl redukcie počtu Lambda, na vizualizáciu redukčných stratégií
λ-počet: Potom a teraz, užitočný leták o míľnikoch, prispievateľoch a bibliografia o počte λ, ktorý bol predstavený na niekoľkých konferenciách Turing Centennial.
