Püsipunktikombinaator

Püsipunktikombinaator (inglise keeles "fixed point combinator") on funktsioon, mis arvutab teiste funktsioonide püsipunkte. See on kõrgemat järku funktsioon, mille parameetriks on funktsioon. 
Funktsiooni püsipunkt on argumendi väärtus, mille see funktsioon samaks jätab ehk mille puhul funktsiooni väärtus võrdub argumendi väärtusega: väärtus formula_1 on funktsiooni formula_2 püsipunkt siis ja ainult siis, kui formula_3. Näiteks 0 ja 1 on ruutfunktsiooni püsipunktid. 
Lambda-arvutuses ja kombinatoorses loogikas on igal funktsioonil mõni püsipunkt. Seal on võimalik genereerida funktsioon (tähis sageli formula_4), mis arvutab iga etteantud funktsiooni mõne püsipunkti: formula_4 on niisugune funktsioon, et kõikide funktsioonide formula_2 korral formula_7. 
Püsipunktikombinaatoreid on võimalik defineerida lambda-arvutuses ja funktsionaalsetes programmeerimiskeeltes. Nende abil on võimalik koostada rekursiivseid definitsioone. 
"Y"-kombinaator lambda-arvutuses.
Klassikalises tüüpimata lambda-arvutuses on igal funktsioonil püsipunkt. Üks implementatsioon püsipunktikombinaatorist on Haskell Curry paradoksaalne "Y"-kombinaator, mille annab
formula_8
Siin on kasutusel lambda-arvutuse standardne kirjapilt ja konventsioonid: "Y" on funktsioon, mis võtab ühe argumendi "f" ja selle funktsiooni tulemuseks on kogu avaldis, mis on kirjas pärast esimest punkti. Avaldis formula_9 tähendab funktsiooni, millel on üks argument "x", mille all mõeldakse funktsiooni, ning tulemuseks on avaldis formula_10, kusjuures formula_11 tähendab funktsiooni "x" rakendumist iseendale. Avaldiste kõrvuti paiknemine tähendab funktsiooni aplikatsiooni, on assotsiatiivne vasakule, ning tehete järjekorra järgi rakendub see enne punkti.
Kinnitamine.
Järgnev arvutus kinnitab, et formula_12 on tõesti funktsiooni "g" püsipunkt:
Lambda term formula_13 ei pruugi üldiselt β-redutseeruda termiks formula_14. Siiski β-redutseerub kumbki term samaks termiks, nagu näidatud.
Kasutamine.
Kui seda rakendada funktsioonile, millel on vaid üks argument, siis "Y"-kombinaator üldjuhul ei peatu. Huvitavamad on tulemused siis, kui rakendada "Y"-kombinaatorit funktsioonidele, millel on kaks või rohkem argumenti. Neid lisatud argumente võib kasutada loenduri või indeksina. Tulemuseks on funktsioon, mis käitub nagu "for-" või "while-"tsükkel imperatiivsetes programmeerimiskeeltes.
Sellisel moel võimaldab "Y"-kombinaator lihtsat rekursiooni. Erinevalt paljudest programmeerimiskeeltest, ei luba lambda-arvutus funktsioonil termina ilmuda omaenda definitsioonis, aga funktsiooni võib edasi anda kõrgemat järku funktsioonile, mis võimaldab selle aplikatsiooni rekursiivselt.
"Y"-kombinaator lubab ette näidata ka Curry paradoksi. Sarnaselt Gödeli arvudele annab "Y"-kombinaator funktsioonidele võime "rääkida iseendast". Lisades tüüpimata lambda-arvutusele loogikatehted, on võimalik tõestada mida iganes, mis näitab, et tüüpimata lambda-arvutus on loogikasüsteemina mittetäielik.
Näide.
Järgnev on näide "Y" implementatsioonist R programmeerimiskeeles:Y &lt;- \(f) {
 g &lt;- \(x) f(x(x))
 g(g)
}Seda saab kasutada selleks, et implementeerida faktoriaal:
fact &lt;- \(f) \(n)
 if (n == 0) 1 else n * f(n - 1)
Y(fact)(5) # annab 5! = 120
"Y" on vajalik vaid siis, kui funktsioonidel pole nimesid. Kui kõik definitsioonid asendada ja ühele reale panna, nii et funktsioonide nimesid pole vaja:
See funktsioon toimib seetõttu, et R toetab laiska väärtustamist.
Keeled, mis kasutavad ranget väärtustamist, näiteks Python, C++ ja teised sarnased keeled, suudavad "Y"-t väljendada, aga selline implementatsioon oleks kasutu, sest see looks lõputu tsükli kuni pinu ületäitumiseni.