Kiinteän pisteen kombinaattori

Kiinteän pisteen kombinaattori (tai kiinteän pisteen operaattori ) on korkeamman asteen funktio , joka laskee toisen funktion kiinteän pisteen .

Tunnetuin kiinteän pisteen kombinaattori on Y-kombinaattori λ-laskennassa , jonka kuuluisa amerikkalainen tiedemies Haskell Curry esitteli nimellä

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

Joskus tämän kombinaattorin nimeä käytetään virheellisesti viittaamaan kaikkiin kiinteän pisteen kombinaattoreihin yleisesti.

Ohjelmointikielet, jotka mahdollistavat kiinteän pisteen kombinaattorin, mahdollistavat anonyymien funktioiden toistamisen ilman, että funktion arvoa määritetään muuttujalle.

Kiinteän pisteen lause

Sekä λ-laskennassa että kombinatorisessa logiikassa jokaiselle termille on vähintään yksi termi , joka . Lisäksi on olemassa sellainen kombinaattori $X$ $P$ $XP=P$ $Y$ $YX=X(YX)$

Katso myös

Kirjallisuus

Wolfenhagen VE Kombinatorinen logiikka ohjelmoinnissa. Laskutoimitukset esineillä esimerkeissä ja tehtävissä. - M.: MEPhI, 1994. - 204 s.; 2. painos, M .: JSC Center YurInfoR, 2003. - 336 s. ISBN 5-89158-101-9 .
Mayer Goldberg, (2005) Kiinteän pisteen yhdistelmien rekursiivisesta luettatavuudesta , BRICS-raportti RS-05-1, Århusin yliopisto
Matthias Felleisen . Luento miksi Y : stä Arkistoitu 29. syyskuuta 2007 Wayback Machinessa .