Czy rachunek SK2 jest kompletną podstawą, gdzie K2 jest odwróconym kombinatorem K?

W szczególności, jeśli zdefiniowałem nowy jako zamiast czy -calculus byłby podstawą do konkurowania?$K_2$

Domyślam się, że „nie”, tylko dlatego, że nie wydaje mi się, że jestem w stanie zbudować zwykłego kombinatora K z kombinacji $S$ , $I$ i $K_2$ , ale nie mam algorytmu do naśladowania ani dobrej intuicji na temat robienia rzeczy z tych kombinatorów.

Wygląda na to, że możesz zdefiniować

Moja próba udowodnienia, że ​​nie była funkcjonalnie kompletna, zasadniczo próbowała wyczerpująco skonstruować każdą funkcję osiągalną z tych kombinatorów, aby pokazać, że osiągasz ślepy zaułek (funkcję, którą widziałeś wcześniej) bez względu na to, jakich kombinatorów używasz. Zdaję sobie sprawę, że niekoniecznie musi tak być w przypadku funkcjonalnie niekompletnych zestawów kombinacji (np. Sam kombinator $K$ nigdy nie będzie ślepy zaułek, gdy zostanie zastosowany do siebie), ale to była moja najlepsza myśl. Zawsze byłem w stanie użyć kombinatora $S$ aby wymknąć się z tego, co uważałem w końcu za ślepy zaułek, więc nie jestem już tak pewien, czy takie podejście jest wykonalne.

Zadałem to pytanie na StackOverflow, ale zachęcono mnie do opublikowania go tutaj. Otrzymałem kilka komentarzy do tego postu, ale nie jestem pewien, czy dobrze je zrozumiałem.

Premia: jeśli nie jest to kompletna podstawa, czy mimo to powstały język jest kompletny?

Rozważ warunki rachunku $S,K_2,I$ jako drzewa (z węzłami binarnymi reprezentującymi aplikacje, a liście $S, K_2$ reprezentujące kombinatory.

Na przykład, termin $S(SS)K_2$ będzie reprezentowane przez drzewo

        @
       / \
      /   \
     @    K2
    / \
   /   \
  S     @
       / \
      /   \
     S     S

Do każdego drzewa $T$ skojarzyć jego prawy liść, ten, który otrzymujesz, biorąc odpowiednią gałąź na każdym z nich @. Na przykład, na prawo liść z drzewa powyżej jest $K_2$ .

Jak widać z poniższej sztuki ASCII, wszystkie reguły redukcji w rachunku $S, K_2, I$ zachowują skrajnie prawy liść.

         @                           @
        / \                         / \
       /   \                       /   \
      @     g    [reduces to]     @     @
     / \                         / \   / \
    /   \                       e   g f   g
   @     f                 
  / \
 /   \
S     e

      @
     / \
    /   \
   @     f    [reduces to]   f
  / \
 /   \
K2    e

Odtąd łatwo zauważyć, że jeśli jakiś termin $T$ redukuje się do $T'$ , wówczas $T$ i $T'$ mają ten sam skrajny prawy liść. W związku z tym, nie ma okres $T$ w $S, K_2, I$ się kamienia nazębnego, takie, że $TK_2S$ zmniejsza się do $K_2$ . Jednakże $KK_2S$ zmniejsza się do $K_2$ , stąd $K$ nie może być wyrażona w $S,K_2, I$ rachunek.

EDYCJA: Jak zauważają komentarze, jest to tylko częściowa odpowiedź, ponieważ dotyczy ona tylko prostego rachunku $S,K_2,I$ (a raczej pokazuje, że nie ma możliwej definicji K, która nie zawiera źle napisany termin). Jeśli nie ma sprzeciwu, nie usunę go, ponieważ stanowi on bardzo produktywną technikę sprawdzania pisanych ustawień.

Przypomnijmy, że nasze kombinatory mają następujące typy (w stylu Curry, więc $A,B,C$ są zmienne):

• $K: A \rightarrow B \rightarrow A$
• $K_2: A \rightarrow B \rightarrow B$
• $S: (A \rightarrow B \rightarrow C) \rightarrow (A \rightarrow B) \rightarrow (A \rightarrow C)$
• $I: A \rightarrow A$

$K$$I,S,K_2$$A \rightarrow B \rightarrow B, (A \rightarrow B \rightarrow C) \rightarrow (A \rightarrow B) \rightarrow (A \rightarrow C), A \rightarrow A$$A$$A \rightarrow B$$B$$A \rightarrow B \rightarrow A$

t,f,u$\rightarrow$$A \rightarrow B \rightarrow B$$(A \rightarrow B \rightarrow C) \rightarrow (A \rightarrow B) \rightarrow (A \rightarrow C)$$A \rightarrow A$t

A B | A -> B
t t | t
t f | f
f t | t
f f | t
t u | f
f u | t
u t | t
u f | f
u u | t

$K_2, S, I$tt$A \rightarrow B \rightarrow A$fu$A$t$B$$S, K_2, I$