Vikipedio:Projekto matematiko/Lambda kalkulo

El Vikipedio

Ĉi tiu artikolo montras stilajn aŭ/kaj gramatikajn aŭ/kaj strukturajn problemojn kaj bezonas poluradon por konformi al pli bona nivelo de kvalito. Post plibonigo movu la artikolon al Lambda kalkulo (eble la nomo mem bezonas korekton) Se la ligo estas ruĝa, vi povas movi la artikolon. Se la ligo estas blua, la alia artikolo pri la temo jam ekzistas kaj tiun kaj ĉi tiun artikolon necasas kunigi.

En komputiko, la lambda kalkulo estas formala sistemo (dizajnita, desegnita) al esplori funkcia difino, funkcia apliko, kaj rekursio. Ĝi estis prezentita per Alonzo Church kaj Stephen Kleene en la 1930-aj jaroj; Preĝejo uzita la lambda kalkulo en 1936 al doni negativa esti konforma al la _Entscheidungsproblem_. La kalkulo povas kutimi pure difini kia komputebla funkcio estas. La demando de ĉu du lambdaj kalkulaj esprimoj estas ekvivalento ne povas esti solvita per ĝenerala algoritmo, kaj ĉi tiu estis la unua demando, (ebena, para, eĉ) antaŭ la problemo de haltado, por kiu _undecidability_ povis esti (pruvita, pruvis). Lambda kalkulo havas grande influita (funkcionalo, funkcia) programlingvoj, aparte Lispi.

La lambda kalkulo povas nomiĝi la (plej minuskla, plej malgranda) universala programlingvo. La lambda kalkulo konsistas de sola transforma regulo ((variablo, varianta) anstataŭo) kaj sola funkcia difina projekto. La lambda kalkulo estas universala en la (senso, senco) (tiu, ke, kiu) (ĉiu, iu) komputebla funkcio povas esti esprimita kaj pritaksis uzanta ĉi tiu formalismo. Ĝi estas tial ekvivalento al la Maŝino de Turing formalismo. Tamen, la lambda kalkulo emfazas la uzi de transformaj reguloj, kaj ne zorgi pri la realaj maŝinaj realigantaj ilin. Ĝi estas (maniero, proksimiĝi, proksimiĝo) pli rilatanta al programaro ol al aparataro.

Ĉi tiu artikolo (kontraktoj, kontraktas) kun la "_untyped_ lambda kalkulo" kiel originale koncipis per Preĝejo. Ekde tiam, iu tipita λ kalkuloj havi estas ellaborita.

Enhavo 1 Historio 2 Neformala priskribo 3 Formala difino 3.1 α-konvertiĝo 3.2 β-malpligrandiĝo 3.3 η-konvertiĝo 4 Aritmetiko en lambda kalkulo 5 Logiko kaj (predikatoj, predikatas) 6 Rekursio 7 Komputeblaj funkcioj kaj lambda kalkulo 8 _Undecidability_ de ekvivalento 9 Lambda kalkulo kaj programlingvoj 10 Vidu ankaŭ jenon: 11 Referencoj 12 Ekstera (ligoj, ligas)

[redaktu] Historio

Originale, Preĝejo havis (penita, provita) al konstrui plenumi formala sistemo por la fundamentoj de matematiko; kiam la sistemo (turnita, turnis) ekster al esti _susceptible_ al la analoga de Paradokso de Russell, li apartigita ekster la lambda kalkulo kaj uzita ĝi al studi komputebleco, _culminating_ en lia negativa esti konforma al la _Entscheidungsproblem_.

[redaktu] Neformala priskribo

En lambda kalkulo, ĉiu esprimo staras por funkcio kun sola argumento; la argumento de la funkcio estas laŭvice funkcio kun sola argumento, kaj la valoro de la funkcio estas alia funkcio kun sola argumento. Funkcio estas anonime difinita per λ esprimaj kiuj ekspresoj la funkcia ago sur ĝia argumento. Ekzemple, la "adicii-du" funkcio f tia (tiu, ke, kiu) <_tt_> f(x) = x + 2 </_tt_> devus esti esprimita en lambda kalkulo kiel <_tt_> &λ; x. x + 2 </_tt_> (aŭ ekvivalente kiel <_tt_> &λ; y. y + 2</_tt_>;  la nomo de la formala argumento estas indiferenta) kaj la nombro <_tt_>f(3)</_tt_> devus esti skribita kiel <_tt_> (λ x. x + 2) 3</_tt_>.  Funkcia apliko estas (maldekstre, restita) asocieca: <_tt_> f x y = (f x) y</_tt_>.  Konsideri la funkcio kiu prenas funkcio kiel argumento kaj aplikas ĝi al la argumento <_tt_>3</_tt_>:<_tt_> &λ; f. f 3</_tt_>.  Ĉi tiu lasta funkcio povis esti aplikita al nia pli frua "adicii-du" funkcio kiel sekvas: <_tt_> (λ f. f 3) (λ x. x+2)</_tt_>.  La tri esprimoj

<_tt_>(λ f. f 3) (λ x. x + 2)   </_tt_> kaj <_tt_>   (λ x. x + 2) 3   </_tt_> kaj <_tt_>   3 + 2   </_tt_>

estas ekvivalento. Funkcio de du (variabloj, variablas) estas esprimita en lambda kalkulo kiel funkcio de unu argumento kiu redonas funkcio de unu argumento (vidi (kareanta, kareado)). Ekzemple, la funkcio <_tt_> f(x, y) = x - y </_tt_> devus esti skribita kiel <_tt_> &λ; x. λ y. x - y</_tt_>. Komuna konvencio estas al mallongigi kareitaj funkcioj kiel, ekzemple, <_tt_> &λ; x y. x - y</_tt_>.

La tri esprimoj

<_tt_>(λ x y. x - y) 7 2   </_tt_> kaj <_tt_>   (λ y. 7 - y) 2   </_tt_> kaj <_tt_>   7 - 2   </_tt_>

estas ekvivalento. Ĝi estas ĉi tiu ekvivalento de λ esprimoj kiu en ĝenerala povas ne esti decidita per algoritmo.

Ne ĉiu λ esprimo povas reduktiĝi al definitiva valoro ŝati la aĵoj pli supre; konsideri ekzemple

<_tt_>(λ x. x x) (λ x. x x)</_tt_>

aŭ

<_tt_>(λ x. x x x) (λ x. x x x)</_tt_>

kaj provi al bildigi kio okazas kiel vi starti al apliki la unua funkcio al ĝia argumento. <_tt_> (λ x. x x) </_tt_> estas ankaŭ sciata kiel la ω _combinator_; <_tt_> ((λ x. x x) (λ x. x x)) </_tt_> estas sciata kiel Ω, <_tt_> ((λ x. x x x) (λ x. x x x)) </_tt_> kiel Ω₂, kaj tiel plu

Dum la lambda kalkula sin ne enhavi (simboloj, simbolas) por (entjeroj, entjeras) aŭ aldono, ĉi tiuj povas esti difinita kiel (mallongigoj, mallongigas) en la kalkulo kaj aritmetiko povas esti esprimita kiel ni estos vidi pli sube.

Lambdaj kalkulaj esprimoj (majo, povas) enhavi libera (variabloj, variablas), kio estas (variabloj, variablas) ne baro per (ĉiu, iu) <_tt_>λ</_tt_>. Ekzemple, la (variablo, varianta) <_tt_> y </_tt_> estas libera en la esprimo <_tt_> (λ x. y) </_tt_>, (figuranta, prezentanta) funkcio kiu ĉiam produktas la rezulto <_tt_> y </_tt_>. Foje, ĉi tiu _necessitates_ la rebaptanta de formala (argumentoj, argumentas), ekzemple por ke redukti

<_tt_>(λ x y. y x) (λ x. y)    al    λ z. z (λ x. y)</_tt_>

Se nur unu formaligas la nocio de funkcia apliko kaj ne permesi λ esprimoj, unu ricevas kombina logiko.

[redaktu] Formala difino

Formale, ni starti kun kalkuleble malfinia aro de (identigiloj, identigas), diri <_tt_>{a, b, c, ..., x, y, z, x₁, x₂, ...}</_tt_>. La aro de ĉiuj λ esprimoj povas tiam esti priskribita per jena ĉirkaŭteksto-libera gramatiko en _BNF_:

1. <_tt_><_expr_> ::= <identigilo><_tt_>
2. <_tt_><_expr_> ::= (λ <identigilo>. <_expr_>)</_tt_>
3. <_tt_><_expr_> ::= (<_expr_> <_expr_>)</_tt_>

La unua du reguloj generi funkcioj, dum la tria priskribas la apliko de funkcio al argumento. Kutime la parantezoj por (lambda-abstraktado, lambda abstraktado) (regulo 2) kaj funkcia apliko (regulo 3) estas nefarita se estas ne multvaloreco sub la (supozoj, supozas) (tiu, ke, kiu) (1) funkcia apliko estas (maldekstre, restita)-asocieca, kaj (2) λ bindas al la tuta esprima sekva ĝi. Ekzemple, la esprimo <_tt_> ((λ x. (x x)) (λ y. y)) </_tt_> povas esti simple skribita kiel <_tt_> (λ x. x x) λ y. y</_tt_>.

Λ esprimoj kiel <_tt_> &λ; x. (x y) </_tt_> ne difini funkcioj ĉar la aper(aĵ)o de la (variablo, varianta) <_tt_>y</_tt_> estas libera, kio estas, ĝi estas ne baro per (ĉiu, iu) <_tt_>λ</_tt_> en la esprimo. La (bindanta, agrafo) de (aper(aĵ)oj, aper(aĵ)as) de (variabloj, variablas) estas (kun indukto sur la strukturo de la λ esprimo) difinis per jenaj reguloj:

1. En esprimo de la (formo, formi) <_tt_> V</_tt_>,  kie <_tt_>V</_tt_> estas (variablo, varianta), ĉi tiu <_tt_>V</_tt_> estas la sola libera aper(aĵ)o.
2. En esprimo de la (formo, formi) <_tt_> &λ; V. E</_tt_>,  la libera (aper(aĵ)oj, aper(aĵ)as) estas la libera (aper(aĵ)oj, aper(aĵ)as) en <_tt_>E</_tt_> escepti tiuj de <_tt_>V</_tt_>. En ĉi tiu (kesto, okazo) la (aper(aĵ)oj, aper(aĵ)as) de <_tt_>V</_tt_> en <_tt_>E</_tt_> estas dirita al esti baro per la <_tt_>λ</_tt_> antaŭ <_tt_>V</_tt_>.
3. En esprimo de la (formo, formi) <_tt_> (E E′)</_tt_>,  la libera (aper(aĵ)oj, aper(aĵ)as) estas la libera (aper(aĵ)oj, aper(aĵ)as) en <_tt_>E</_tt_> kaj <_tt_>E′</_tt_>.

Super la aro de λ esprima ekvivalentrilato (ĉi tie signifita kiel <_tt_>==</_tt_>) estas difinita (tiu, ke, kiu) (enkaptas, kaptoj, kaptas) la intuicio (tiu, ke, kiu) du esprimoj signifi la sama funkcio. Ĉi tiu ekvivalentrilato estas difinita per la α-konvertiĝa regulo kaj la β-malpligrandiĝa regulo. Iam (alterna, alterni) ekvivalentrilato, ricevis per (adoptanta, filiganta) tria regulo (nomita, vokis) η-konvertiĝo, estas uzita.

[redaktu] α-konvertiĝo

La α-konvertiĝa regulo estas intencita al (ekspreso, esprimi) la ideo (tiu, ke, kiu) la (nomoj, nomas) de la baro (variabloj, variablas) estas malgrava; ekzemple (tiu, ke, kiu) <_tt_> &λ;x.x </_tt_> kaj <_tt_> &λ;y.y </_tt_> estas la sama funkcio. Tamen, la regulo estas ne kiel simpla kiel ĝi unua (aperas, ŝajnas, aspektas). Estas nombro de limigoj sur kiam unu baro (variablo, varianta) (majo, povas) esti (anstataŭigita, anstataŭigis) kun alia.

La α-konvertiĝaj regulaj ŝtatoj (tiu, ke, kiu) se <_tt_>V</_tt_> kaj <_tt_>W</_tt_> estas (variabloj, variablas), <_tt_>E</_tt_> estas λ esprimo, kaj

<_tt_>E[V := W]</_tt_>

(meznombroj, meznombras, signifas) la esprimo <_tt_>E</_tt_> kun ĉiu libera aper(aĵ)o de <_tt_>V</_tt_> en <_tt_>E</_tt_> (anstataŭigita, anstataŭigis) kun <_tt_>W</_tt_>, tiam

<_tt_>λ V. E  ==  λ W. E[V := W]</_tt_>

se <_tt_>W</_tt_> ne aperi libere en <_tt_>E</_tt_> kaj <_tt_>W</_tt_> estas ne baro per <_tt_>λ</_tt_> en <_tt_>E</_tt_> ĉiam ĝi (anstataŭas, anstataŭigas) <_tt_>V</_tt_>. Ĉi tiu regulo diras ni ekzemple (tiu, ke, kiu) <_tt_> &λ; x. (λ x. x) x </_tt_> estas la sama kiel <_tt_> &λ; y. (λ x. x) y</_tt_>.

[redaktu] β-malpligrandiĝo

La β-malpligrandiĝaj regulaj ekspresoj la ideo de funkcia apliko. Ĝiaj ŝtatoj (tiu, ke, kiu)

<_tt_>((λ V. E) E′)  ==  E[V := E′]</_tt_>

se ĉiuj libera (aper(aĵ)oj, aper(aĵ)as) en <_tt_>E′</_tt_> resti libera en <_tt_>E[V := E′]</_tt_>.

La rilato <_tt_>==</_tt_> estas tiam difinis kiel la (plej minuskla, plej malgranda) ekvivalentrilato (tiu, ke, kiu) (verigas, kontentigas) ĉi tiuj du reguloj.

Pli operacia difino de la ekvivalentrilato povas esti donita per aplikanta la reguloj nur de (maldekstre, restis) al (ĝusta, dekstra, rajto). Λ esprimo kiu ne permesi (ĉiu, iu) β malpligrandiĝo, kio estas, havas ne subesprimo de la (formo, formi) <_tt_>((λ V. E) E′)</_tt_>, estas (nomita, vokis) normala formo. Ne ĉiu λ esprimo estas ekvivalento al normala formo, sed se ĝi estas, tiam la normala formo estas unika supren al nomanta de la formala (argumentoj, argumentas). Plue, estas algoritmo por komputantaj normalaj formoj: konservi anstataŭiganta la unua ((maldekstre, restis)-plej) formala argumento kun ĝia (korespondanta, respektiva) (betono, konkreta) argumento, ĝis ne plui malpligrandiĝo estas ebla. Ĉi tiu algoritmo (digas, endigigas, haltas) se kaj nur se la λ esprimo havas normala formo. La Preĝejo-_Rosser_ teoremo tiam ŝtatoj (tiu, ke, kiu) du esprima rezulto en la sama normala formo supren al rebaptanta de la formala (argumentoj, argumentas) se kaj nur se ili estas ekvivalento.

[redaktu] η-konvertiĝo

Estas tria regulo, η-konvertiĝo, kiu (majo, povas) esti adiciita al ĉi tiuj du al (formo, formi) nova ekvivalentrilato. Η-konvertiĝaj ekspresoj la ideo de pligrandigebleco, kiu en ĉi tiu ĉirkaŭteksto estas (tiu, ke, kiu) du funkcioj estas la sama se kaj nur se ili doni la sama rezulto por ĉiuj (argumentoj, argumentas). Η-konvertiĝo konvertas inter <_tt_> &λ; x. f x </_tt_> kaj <_tt_> f </_tt_> ĉiam <_tt_>x</_tt_> ne aperi libera en <_tt_>f</_tt_>. Ĉi tiu povas vidiĝi al esti ekvivalento al pligrandigebleco kiel sekvas:

Se <_tt_>f</_tt_> kaj <_tt_>g</_tt_> estas _extensionally_ ekvivalento, kio estas se <_tt_> f a==g a </_tt_> por ĉiuj λ esprimoj <_tt_>a</_tt_>, tiam en aparta per prenante <_tt_>a</_tt_> al esti (variablo, varianta) <_tt_>x</_tt_> ne (aperanta, ŝajnanta, aspektanta) libera en <_tt_>f</_tt_> nek <_tt_>g</_tt_> ni havi <_tt_> f x == g x </_tt_> kaj de ĉi tie <_tt_> &λ; x. f x == &λ; x. g x</_tt_>,  kaj (do, tiel) per η-konvertiĝo <_tt_> f == g</_tt_>.  (Do, Tiel) se ni preni η-konvertiĝo al validi, ni trovi pligrandigebleco estas valida.

Male se pligrandigebleco estas prenita al validi, tiam ekde per β-malpligrandiĝo por ĉiuj <_tt_>y</_tt_> ni havi <_tt_> (λ x. f x) y == f y</_tt_>,  ni havi <_tt_> &λ; x. f x  ==  f</_tt_>;  kio estas, η-konvertiĝo estas fundamenti al validi.

[redaktu] Aritmetiko en lambda kalkulo

Estas kelkaj ebla (vojoj, vojas) al difini la naturaj nombroj en lambda kalkulo, sed per malproksime la plej komuna estas la Preĝejaj numeraloj, kiu povas esti difinita kiel sekvas:

<_tt_>0 := λ f x. x</_tt_>

<_tt_>1 := λ f x. f x</_tt_>

<_tt_>2 := λ f x. f (f x)</_tt_>

<_tt_>3 := λ f x. f (f (f x))</_tt_>

kaj tiel plu. Intuicie, la nombro <_tt_>n</_tt_> en lambda kalkulo estas funkcio (tiu, ke, kiu) prenas funkcio <_tt_>f</_tt_> kiel argumento kaj redonas la <_tt_>n</_tt_>Ona komponaĵo de <_tt_>f</_tt_>. Tio estas al diri, Preĝeja numeralo estas funkcio de pli alta ordo -- ĝi prenas sola-argumenta funkcio <_tt_>f</_tt_>, kaj redonas alia sola-argumenta funkcio.

((Tononomo, Noto, Noti) (tiu, ke, kiu) en (Eklezia, Kirka, Preĝeja) originala lambda kalkulo, la formala parametro de λ esprimo estis postulita al okazi almenaŭ iam en la funkcia korpo, kiu farita la pli supre difino de 0 neebla.) Donita ĉi tiu difino de la Preĝejaj numeraloj, ni povas difini postanta funkcio, kiu prenas nombro <_tt_>n</_tt_> kaj redonas <_tt_>n + 1</_tt_>:

<_tt_>_SUCC_ := λ n f x. f(n f x)</_tt_>

Aldono estas difinita kiel sekvas:

<_tt_>_PLUS_ := λ m n f x. m f (n f x)</_tt_>

<_tt_>_PLUS_</_tt_> povas esti penso de kiel funkcio prenante du naturaj nombroj kiel (argumentoj, argumentas) kaj redonanta natura nombro; ĝi estas amuzado al kontroli (tiu, ke, kiu)

<_tt_>_PLUS_ 2 3   </_tt_> kaj <_tt_>   5</_tt_>

estas ekvivalento λ esprimoj. Multipliko povas tiam esti difinita kiel

<_tt_>_MULT_ := λ m n. m (_PLUS_ n) 0</_tt_>,

la ideo estante (tiu, ke, kiu) multiplikante m kaj n estas la sama kiel m (tempoj, tempas) adicianta n al nulo. Alternative

<_tt_>_MULT_ = λ m n f. m (n f)</_tt_>

La (antaŭulo, antaŭanto) <_tt_> _PRED_ n = n - 1 </_tt_> de pozitiva entjero n estas pli malfacila:

<_tt_>_PRED_ := λ n f x. n (λ g h. h (g f)) (λ u. x) (λ u. u) </_tt_>

aŭ alternative

<_tt_>_PRED_ = λ n. n (λ g k. (g 1) (λ u. _PLUS_ (g k) 1) k) (λ v. 0) 0 </_tt_>

(Tononomo, Noto, Noti) la artifiko <_tt_>(g 1) (λ u. _PLUS_ (g k) 1) k</_tt_> kiu pritaksas al <_tt_>k</_tt_> se <_tt_>g(1)</_tt_> estas nulo kaj al <_tt_>g(k) + 1</_tt_> alie.

[redaktu] Logiko kaj (predikatoj, predikatas)

Per konvencio, jeno du (difinoj, difinas) (sciata kiel Preĝejo _booleans_) estas uzitaj por la bulea (valoroj, valoras) <_tt_>VERO</_tt_> kaj <_tt_>Malvero</_tt_>:

<_tt_>VERO := λ x y. x</_tt_>

<_tt_>Malvero := λ x y. y</_tt_>

((Tononomo, Noto, Noti) (tiu, ke, kiu) <_tt_>Malvero</_tt_> estas ekvivalento al la Preĝeja numerala nulo difinis pli supre)

Tiam, kun ĉi tiuj du λ-(termoj, kondiĉoj, terminoj, termas, terminas), ni povas difini iu logiko (operatoroj, operatoras):

<_tt_>KAJ := λ p q. p q Malvero</_tt_>

<_tt_>_OR_ := λ p q. p VERO q</_tt_>

<_tt_>NOT := λ p. p Malvera VERO</_tt_>

<_tt_>_IFTHENELSE_ := λ p x y. p x y</_tt_>

Ni estas nun pova komputi iuj logikaj funkcioj, kiel ekzemple:

<_tt_>KAJ VERa Malvero<_tt_>

<_tt_>≡ (λ p q. p q Malvero) VERa Malvero →_β VERa Malvera Malvero

<_tt_>≡ (λ x y. x) Malvera Malvero →_β Malvero</_tt_>

kaj ni vidi (tiu, ke, kiu) <_tt_>KAJ VERa Malvero</_tt_> estas ekvivalento al <_tt_>Malvero</_tt_>.

predikato estas funkcio kiu redonas bulea valoro. La plej fundamenta predikato estas <_tt_>_ISZERO_</_tt_> kiu redonas <_tt_>VERO</_tt_> se ĝia argumento estas la Preĝeja numeralo <_tt_>0</_tt_>, kaj <_tt_>Malvero</_tt_> se ĝia argumento estas (ĉiu, iu) alia Preĝeja numeralo:

<_tt_>_ISZERO_ := λ n. n (λ x. Malvero) VERO</_tt_>

La havebleco de (predikatoj, predikatas) kaj la pli supre difino de <_tt_>VERO</_tt_> kaj <_tt_>Malvero</_tt_> fari ĝi oportuna al skribi "se-tiam-alia" (propozicioj, frazoj, ordonoj) en lambda kalkulo.

[redaktu] Rekursio

Rekursio estas la difino de funkcio uzanta la funkcia sin; sur la (vizaĝo, edro) de ĝi, lambda kalkulo ne permesi ĉi tiu. Tamen, ĉi tiu efekto estas iluzia. Konsideri ekzemple la faktoriala funkcio <_tt_>f(n)</_tt_> rekursie difinis per

<_tt_>f(n) = 1, se n = 0; kaj n·f(n-1), se n>0</_tt_>.

En lambda kalkulo, unu ne povas difini funkcio kiu inkluzivas sin. Al preni ĉirkaŭ ĉi tiu, unu (majo, povas) starti per difinanta funkcio, ĉi tie (nomita, vokis) <_tt_>g</_tt_>, kiu prenas funkcio <_tt_>f</_tt_> kiel argumento kaj redonas alia funkcio (tiu, ke, kiu) prenas <_tt_>n</_tt_> kiel argumento:

<_tt_>g := λ f n. (1, se n = 0; kaj n·f(n-1), se n>0)</_tt_>.

La funkcio (tiu, ke, kiu) <_tt_>g</_tt_> redonas ĉu redonas la konstanto <_tt_>1</_tt_>, aŭ redonas n (tempoj, tempas) la apliko de la funkcio <_tt_>f</_tt_> al <_tt_>n-1</_tt_>. Uzanta la <_tt_>_ISZERO_</_tt_> predikato, kaj bulea kaj algebra (difinoj, difinas) priskribita pli supre, la funkcio <_tt_>g</_tt_> povas esti difinita en lambda kalkulo.

Tamen, <_tt_>g</_tt_> per sin estas ankoraŭ ne rekursie; por ke uzi <_tt_>g</_tt_> al krei la rekursie faktoriala funkcio, la funkcio (trapasita, pasis) al <_tt_>g</_tt_> kiel <_tt_>f</_tt_> devas havi specifaj propraĵoj. Nome, la funkcio (trapasita, pasis) kiel <_tt_>f</_tt_> devas elvolvi al la funkcio <_tt_>g</_tt_> (nomita, vokis) kun unu argumento -- kaj (tiu, ke, kiu) argumento devas esti la funkcio (tiu, ke, kiu) estis (trapasita, pasis) kiel <_tt_>f</_tt_> denove!

En alia (vortoj, vortas), <_tt_>f</_tt_> devas elvolvi al <_tt_>g(f)</_tt_>. Ĉi tiu (voko, voki) al <_tt_>g</_tt_> estos tiam elvolvi al la pli supre faktoriala funkcio kaj kalkuli suben al alia nivelo de rekursio. En (tiu, ke, kiu) elvolvaĵo la funkcio <_tt_>f</_tt_> estos aperi denove, kaj estos denove elvolvi al <_tt_>g(f)</_tt_> kaj daŭri la rekursio. Ĉi tiu speco de funkcio, kie <_tt_>f = g(f)</_tt_>, estas (nomita, vokis) fikspunkto de <_tt_>g</_tt_>, kaj ĝi (kurbiĝoj, kurbiĝas, turnas, tornas, kurbigas) ekster (tiu, ke, kiu) ĝi povas esti realigita en la lambda kalkula uzanta kio estas sciata kiel la paradoksa operatoro aŭ fikspunkta operatoro kaj estas (prezentita, prezentis) kiel <_tt_>Y</_tt_> -- la Y _combinator_:

<_tt_>Y = λ g. (λ x. g (x x)) (λ x. g (x x))</_tt_>

En la lambda kalkulo, <_tt_>Y g</_tt_> estas fikspunkto de <_tt_>g</_tt_>, kiel ĝi elvolvas al <_tt_>g (Y g)</_tt_>. Nun, al plenumi nia rekursie (voko, voki) al la faktoriala funkcio, ni devus simple (voko, voki) <_tt_> g (Y g) n</_tt_>,  kie n estas la nombro ni estas kalkulanta la faktorialo de.

Donita n = 5, ekzemple, ĉi tiu elvolvas al:

<_tt_>(λ n.(1, se n = 0; kaj n·((Y g)(n-1)), se n>0)) 5</_tt_>

<_tt_>1, se 5 = 0; kaj 5·(g(Y g)(5-1)), se 5>0</_tt_>

<_tt_>5·(g(Y g) 4)</_tt_>

<_tt_>5·(λ n. (1, se n = 0; kaj n·((Y g)(n-1)), se n>0) 4)</_tt_>

<_tt_>5·(1, se 4 = 0; kaj 4·(g(Y g)(4-1)), se 4>0)</_tt_>

<_tt_>5·(4·(g(Y g) 3))</_tt_>

<_tt_>5·(4·(λ n. (1, se n = 0; kaj n·((Y g)(n-1)), se n>0) 3))</_tt_>

<_tt_>5·(4·(1, se 3 = 0; kaj 3·(g(Y g)(3-1)), se 3>0))</_tt_>

<_tt_>5·(4·(3·(g(Y g) 2)))</_tt_>

<_tt_> ...</_tt_>

Kaj tiel plu, pritaksanta la strukturo de la algoritmo rekursie. Ĉiu rekursie difinis funkcio povas vidiĝi kiel fiksa punkto de iu alia taŭgi funkcio, kaj pro tio, uzanta <_tt_>Y</_tt_>, ĉiu rekursie difinis funkcio povas esti esprimita kiel λ esprimo. En aparta, ni povas nun pure difini la subtraho, multipliko kaj kompara predikato de naturaj nombroj rekursie.

[redaktu] Komputeblaj funkcioj kaj lambda kalkulo

Funkcio <_tt_>F: N → N</_tt_> de naturaj nombroj estas komputebla funkcio se kaj nur se tie ekzistas λ esprimo <_tt_>f</_tt_> tia (tiu, ke, kiu) por ĉiu paro de x, y en <_tt_>N</_tt_>, <_tt_> F(</_tt_>x<_tt_>)</_tt_> = y  se kaj nur se <_tt_> f x == y</_tt_>,  kie <_tt_>x</_tt_> kaj <_tt_>y</_tt_> estas la Preĝejaj numeraloj (korespondanta, respektiva) al x kaj y, respektive. Ĉi tiu estas unu de la multaj (vojoj, vojas) al difini komputebleco; vidi la Preĝejo-Turing-a tezo por diskuto de alia (manieroj, proksimiĝoj) kaj ilia ekvivalento.

[redaktu] _Undecidability_ de ekvivalento

Estas ne algoritmo kiu prenas kiel (enigo, enigi) du λ esprimoj kaj (eligas, eligoj) <_tt_>VERO</_tt_> aŭ <_tt_>Malvero</_tt_> dependanta sur ĉu ĉu ne la du esprimoj estas ekvivalento. Ĉi tiu estis historie la unua problemo por kiu la _unsolvability_ povis esti pruvita. Kompreneble, por ke fari (do, tiel), la nocio de algoritmo havas al esti pure difinita; Preĝeja uzita difino tra rekursiaj funkcioj, kiu estas nun sciata al esti ekvivalento al ĉiuj alia modera (difinoj, difinas) de la nocio.

(Eklezia, Kirka, Preĝeja) pruvo unua reduktas la problemo al (determinanta, difinanta) ĉu donita λ esprimo havas normala formo. Normala formo estas ekvivalenta esprimo kiu ne povas reduktiĝi (ĉiu, iu) plui. Tiam li alprenas (tiu, ke, kiu) ĉi tiu predikato estas komputebla, kaj povas de ĉi tie esti esprimita en lambda kalkulo. Konstruaĵo sur pli frua laboro per Kleene-a kaj konstruanta Gödel-a (numeranta, numerado (teorio de komputado)) por λ esprimoj, li konstruas λ esprimo <_tt_>e</_tt_> kiu proksime sekvas la pruvo de Gödel-a's unua nepleneca teoremo. Se <_tt_>e</_tt_> estas aplikita al ĝia posedi Nombro de Gödel, kontraŭdiraj rezultoj.

[redaktu] Lambda kalkulo kaj programlingvoj

Plej programlingvoj estas ekvivalento al la lambda kalkulo etendis kun iu aldona programlingvo konstruas. La klasika laboro kie ĉi tiu starpunkto estis atentigi pri estita Peniseto _Landin_'s "A Rilato inter _ALGOL_ 60 kaj (Eklezia, Kirka, Preĝeja) Λ-skribmaniero", (publikigita, publikigis) en _CACM_ en 1965. La ŝlosila punkto estas (tiu, ke, kiu) la lambdaj kalkulaj ekspresoj la speco de _procedural_ abstraktado kaj apliko utila por (ĉiu, iu) programlingvo. Elstare, (funkcionalo, funkcia) programlingvoj estas baze la lambda kalkulo kun iu (konstantoj, konstantas) kaj _datatypes_ adiciis. Lispi uzas varianto de λ skribmaniero por difinantaj funkcioj, sed nur ĝia pure (funkcionalo, funkcia) subaro estas (reale, reele) ekvivalento al lambda kalkulo.

Reale realiganta la lambda kalkulo sur komputilo engaĝas (traktatanta, traktanta, kuracanta) "funkcioj" kiel unua-klaso (objektoj, objektas), kiu (kurbiĝoj, kurbiĝas, turnas, tornas, kurbigas) ekster al esti iom malfacila al atingi uzantaj stako-bazitaj komputilaj lingvoj. Ĉi tiu estas sciata kiel la _Funarg_ problemo.

Teorio de la lambda kalkulo diras (tiu, ke, kiu) lambda kalkulo (kalkuladoj, kalkuladas, komputoj, komputas) povas ĉiam esti portita ekster sinsekve, ne (tiu, ke, kiu) ili devas esti portita ekster sinsekve. La lambda kalkulo estas taŭgi por esprimanta iu (specoj, specas) de _parallelism_ — ekzemple, (voko, voki) per estonta pritakso. Tamen, la lambda kalkulo ne en ĝenerala realigi kunrulo; rilatantaj kalkuloj (kiel la π kalkulo) havi estas (dizajnita, desegnita) al _overcome_ ĉi tiu limigo.

[redaktu] Vidu ankaŭ jenon:

• _SKI_ _combinator_ kalkulo
• H.P. _Barendregt_'s Lambda kubo
• _Jean_-_Yves_ _Girard_'s Sistemo F
• _Thierry_ _Coquand_'s kalkulo de konstruoj
• Tipita lambda kalkulo
• Kareo-_Howard_ izomorfio
• Anonima rekursio
• _Unlambda_

[redaktu] Referencoj

• _Abelson_, _Harold_ & _Gerald_ Garolo _Sussman_. Strukturo kaj Interpretado de Komputilaj Programoj. La _MIT_ Premi. ISBN 0262510871.
• _Barendregt_, _Henk_, La lambda kalkulo, ĝia sintakso kaj (semantiko, semantikoj, semantikas), Nordo-(Holando, Nederlando) (1984), estas la multampleksa referenco sur la (_untyped_) lambda kalkulo; Vidu ankaŭ jenon: la papero Enkonduko al Λ Kalkulo.
• Preĝejo, _Alonzo_, An _unsolvable_ problemo de rudimenta nombroteorio, Amerika Ĵurnalo de Matematiko, 58 (1936), _pp_. 345–363. Ĉi tiu papero enhavas la pruvo (tiu, ke, kiu) la ekvivalento de λ esprimoj estas en ĝenerala ne decidebla.
• _Punit_,_Gupta_, _Amit_ & _Ashutosh_ _Agte_, _Untyped_ λ-kalkulo, α-, β- kaj η- (rabatoj, rabatas, malpligrandiĝoj, malpligrandiĝas) kaj rekursio
• _Henz_, _Martin_, La Λ Kalkulo. Formale (ĝusta, ĝustigi, korekti) evoluo de la Lambda kalkulo.
• Kleene-a, _Stephen_, A teorio de pozitiva (entjeroj, entjeras) en formala logiko, Amerika Ĵurnalo de Matematiko, 57 (1935), _pp_. 153–173 kaj 219–244. Enhavas la lambda kalkulo (difinoj, difinas) de kelkaj familiaraj funkcioj.
• _Larson_, _Jim_, An Enkonduko al Λ Kalkulo kaj Projekto. Dolĉa enkonduko por (programistoj, programistas, komputistoj, komputistas).

Iu (partoj, partas) de ĉi tiu artikolo estas bazita sur materialo de _FOLDOC_, uzita kun .

[redaktu] Ekstera (ligoj, ligas)

• L. _Allison_, Iu _executable_ λ-kalkulo (ekzemploj, ekzemplas)
• _Georg_ P. _Loczewski_, La Λ Kalkulo kaj A++
• Davido C. _Keenan_, Al (Sekci, Malkomponi) _Mockingbird_: A Grafika Skribmaniero por la Λ Kalkulo kun Animis Malpligrandiĝo