Kombinátor s pevným bodem

Kombinátor pevného bodu (nebo operátor pevného bodu ) je funkce vyššího řádu , která vypočítává pevný bod jiné funkce.

Nejznámějším kombinátorem s pevnou čárkou je Y-kombinátor v λ-kalkulu , který zavedl slavný americký vědec Haskell Curry jako

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

Někdy se název tohoto kombinátoru chybně používá k označení všech kombinátorů s pevnou čárkou obecně.

Programovací jazyky, které umožňují kombinátor s pevnou čárkou, umožňují opakování anonymních funkcí bez přiřazení hodnoty takové funkce proměnné.

Věta o pevném bodě

Jak v λ-kalkulu, tak v kombinatorické logice, pro každý člen existuje alespoň jeden člen takový, že . Navíc existuje takový kombinátor $X$ $P$ $XP=P$ $Y$ $YX=X(YX)$

Viz také

Literatura

Wolfenhagen VE Kombinatorická logika v programování. Výpočty s objekty v příkladech a úlohách. — M.: MEPhI, 1994. — 204 s.; 2. vyd., M.: JSC Center YurInfoR, 2003. - 336 s. ISBN 5-89158-101-9 .
Mayer Goldberg, (2005) O rekurzivní sčítatelnosti kombinátorů s pevným bodem , BRICS Report RS-05-1, University of Aarhus
Matyáš Felleisen . Přednáška o Proč Y archivována 29. září 2007 na Wayback Machine .