Rachunek kombinatorów

Z Wikipedii

Niektóre informacje zawarte w artykule wymagają weryfikacji.
Zajrzyj na stronę dyskusji, by dowiedzieć się, jakie informacje budzą wątpliwości.

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 rodzielonej aplikacji S, oraz kombinatory aplikacji złożone z pary dowolnych kombinatorów - funkcji i argumentu:

σ = S | K | (σ σ)

Derywacją rządzą dwie reguły:

((K α) β) → α
(((S α) β) γ) → ((α γ) (β γ))

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:

K = λ x . λ y . x
S = λ x . λ y . λ z . (x z) (y z)

Często wprowadza się też kombinator identyczności I z regułą:

(I α) → α

Ponieważ system SK już jest kompletny, kombinator ten można przepisać jako (SK)K:

(((S K) K) α) → ((K α) (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.

[edytuj] Przykłady

Prawda - K
Fałsz - KI = K(SKK)
0 - KI
1 - I = SKK
Następnik - S(S(KS)K)
Operator paradoksalny - S(S(S(KS)K)(K(SII)))(S(S(KS)K)(K(SII))) = S(S(S(KS)K)(K(S(SKK)(SKK))))(S(S(KS)K)(K(S(SKK)(SKK))))

Jak widać po przykładzie operatora paradoksalnego, rachunek kombinatorów może być i jest prostszy, jest jednak o wiele mniej czytelny od rachunku lambda.