Niektóre z zamieszczonych tu informacji wymagają weryfikacji. Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu. |
Rachunek kombinatorów (ang. Combinatory Calculi) to jeden z najprostszych możliwych uniwersalnych systemów formalnych.
Na język rachunku kombinatorów składają się kombinator stały K, kombinator rozdzielonej aplikacji S, oraz kombinatory aplikacji złożone z pary dowolnych kombinatorów - funkcji i argumentu:
Derywacją rządzą dwie reguły:
Gdzie α, β i γ to dowolne kombinatory.
Tak prosty system jest w stanie wyrazić wszystko, co jest w stanie wyrazić rachunek lambda, dowolna maszyna Turinga czy w ogóle dowolny algorytm.
Kombinatory mają prostą interpretację w rachunku lambda:
Często wprowadza się też kombinator identyczności I z regułą:
Ponieważ system SK już jest kompletny, kombinator ten można przepisać jako (SK)K:
Podobnie jak w rachunku lambda zwykle pomija się nadmiarowe nawiasy, zakładając wiązanie w lewo: α β γ to więc ((α β) γ).
Ponieważ każdy kombinator ma bardzo prostą interpretację w rachunku lambda, badania rachunku kombinatorów są zwykle częścią badań nad rachunkiem lambda.
Z zupełności systemu SK wynika, że każde λ wyrażenie bez zmiennych wolnych (w terminologii rachunku lambda również zwane kombinatorem) można zapisać za pomocą S i K, jednak ze względu na uboższy język, takie wyrażenia mają tendencję do przybierania bardzo dużych rozmiarów.
Uczę się języka hebrajskiego. Tutaj go sobie utrwalam.
Zawartość tej strony pochodzi stąd.