Fixpontos kombinátor

A fixpont- kombinátor (vagy fixpont-operátor ) egy magasabb rendű függvény , amely egy másik függvény fixpontját számítja ki .

A leghíresebb fixpontos kombinátor az Y-kombinátor a λ-számításban , amelyet a híres amerikai tudós, Haskell Curry mutatott be .

Y=\lambda f.(\lambda xf(xx))(\lambda xf(xx)).

Néha ennek a kombinátornak a nevét tévesen használják általában az összes fixpontos kombinátorra.

Azok a programozási nyelvek, amelyek lehetővé teszik a fixpontos kombinátort, lehetővé teszik anonim függvények ismétlődését anélkül, hogy egy ilyen függvény értékét egy változóhoz hozzárendelnék.

Fixpont tétel

Mind a λ-számításban, mind a kombinatorikus logikában minden taghoz van legalább egy olyan tag , hogy . Sőt, létezik olyan kombinátor is $x$ $P$ $XP=P$ $Y$ $YX=X(YX)$

Lásd még

Irodalom

Wolfenhagen VE Kombinatorikus logika a programozásban. Számítások objektumokkal példákban és feladatokban. — M.: MEPhI, 1994. — 204 p.; 2. kiadás, M .: JSC Center YurInfoR, 2003. - 336 p. ISBN 5-89158-101-9 .
Mayer Goldberg, (2005) A fixpontos kombinátorok rekurzív felsorolhatóságáról , BRICS RS-05-1 jelentés, Aarhusi Egyetem
Matthias Felleisen . Előadás Y miértjéről Archiválva : 2007. szeptember 29. a Wayback Machine -nél .