Zbiory podstawowe dla rachunku kombinatorycznego

Dobrze wiadomo, że kombinatory S i K tworzą zestaw podstawowy dla rachunku kombinatorycznego, w tym sensie, że wszystkie inne kombinatory można wyrazić za ich pomocą. Istnieje również podstawa Curry'ego B, C, K, W, która ma tę samą właściwość. Musi istnieć nieskończona liczba takich baz, ale nie znam żadnych innych.

Wiem, że istnieje wiele baz z jednym kombinatorem, takich jak kombinator Iota i różne inne konstruowane / recenzowane przez Fokkera . Są to jednak „niewłaściwe” kombinatory, co oznacza, że ​​są wyrażane raczej w kategoriach innych kombinacji niż czystych abstrakcji. ¹ Na potrzeby tego pytania interesują mnie tylko zestawy bazowe złożone z odpowiednich kombinacji.

Czy istnieje również badanie innych możliwych zestawów podstawowych? Ideałem byłoby coś wzdłuż linii Wolframa badaniu różnych innych modeli obliczeniowych, w których różne kombinacje są systematycznie badane. W szczególności interesuje mnie, czy znane są proste przykłady następujących rzeczy:

• Minimalny zestaw podstawowy, który zawiera kombinator I. (Używam „minimalnego”, co oznacza, że ​​jeśli usuniesz członka, przestanie on być podstawą, więc podstawa SKI się nie liczy).
• Minimalny zestaw podstawowy, który zawiera kombinator Y lub kombinator (inaczej mockingbird)$\omega$

Wszelkie inne informacje o innych możliwych podstawach logiki kombinacyjnej oprócz S, K i B, C, K, W byłyby naprawdę pomocne.

W szerszym ujęciu interesuje mnie badanie rachunku kombinatorycznego jako układu czysto mechanicznego , tj. Jako zestawu reguł transformacji drzew binarnych z oznaczonymi węzłami, które nie wymagają szczególnej interpretacji semantycznej. Wszelkie wskazówki dotyczące zasobów, które przyjmą takie podejście, byłyby bardzo mile widziane. ( Aby wyśmiewać drozda przyjmuje takie podejście, ale daje niepełną prezentację, podczas gdy rachunek Lambda Barendregta jest bardzo związany z semantyką, co utrudnia mi wydobycie aspektów czysto mechanicznych, którymi jestem zainteresowany.)

¹ _{Mówiąc dokładniej: w rachunku lambda właściwy kombinator jest wyrażeniem formy , gdzie ma tylko , itp. jako dowolne zmienne i nie zawiera żadnych abstrakcji. Na przykład jest właściwym kombinatorem, ale nie jest, ponieważ zawiera zastosowane do terminu lambda.$(\lambda.x_1x_2\dots P(x_1,x_2,\dots))$$P(x_1,x_2,\dots)$$x_1$$x_2$$(\lambda x y z. x(z z))$$(\lambda x. x(\lambda y.y) )$$x$}

$C$$T = (\lambda x y. y x)$$W$$\omega = (\lambda x. x x)$$C$$W$$C = B(T(B B T))(B B T)$$W = C(B \omega(B B T))$

Podstawą jest dowolny zestaw kombinatorów, który zawiera kombinator anulujący (jak K), kombinator komponujący (jak B), kombinator permutacyjny (jak C), kombinator powielający (jak W) i kombinator tożsamości I są podstawą. Jeśli kombinator I pochodzi od twoich czterech innych kombinacji, wtedy te cztery same wystarczą.

Oznacza to, że coś w rodzaju B, T, M, K, I, gdzie Tab = ba i Ma = aa, jest również podstawą. Rzeczywiście, B, T, M, K wystarczy, ponieważ mogę pochodzić od B, T, M, K (nie jest to łatwe do udowodnienia; dowodem jest najpierw wyprowadzić S z B, T, M, a następnie przyjąć I = SKK.)