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

10

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

K2=λx.(λy.y)
K=λx.(λy.x)
{S,K2,I}

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 K2 , 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ć

K2=KI
za pomocą zwykłego {S,K,(I)} -kalkulusa, ale tak naprawdę nie mogłem pracować wstecz, aby uzyskać pochodną K w odniesieniu do K2 i pozostałych.

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?

kapusta
źródło
to fajna łamigłówka. Wydaje się, że S i K 'pozwalają tylko na generowanie terminów, których głowy normalne kształty mają do trzech wiodących λ (tj. Terminy, które normalizują się do postaci λx₁.λx₂.λx₃. Xᵢ t₁ ... tₙ), więc może to być kolejna droga do udowodnienia niekompletności, choć formalizacja wydaje się nieco trudna. Na pewno nigdy nie osiągniesz „ślepego zaułka”: zacznij od zdefiniowania I = λx.x = K2 K2, a następnie przez powtórzenie transformacji t ↦ S t K2 możesz wyrazić λx.x I ... I dla dowolnego ciągu Is .
Noam Zeilberger
... I przepraszam, przez „niekompletność” mam na myśli niekompletność SK 'jako kombinacyjną podstawę dla nietypowego rachunku lambda. Nie mam też dobrej intuicji, czy jest to Turing-zupełny (co implikowałoby kombinatoryczna kompletność, ale nie odwrotnie).
Noam Zeilberger
Przeniesiony : stackoverflow.com/q/55148283/781723 , cs.stackexchange.com/q/108741/755 . Proszę nie pisać to samo pytanie na wielu stronach . Każda społeczność powinna rzetelnie odpowiedzieć na pytanie bez marnowania czasu.
DW
Mój błąd @DW, czy mogę coś zrobić, aby temu zaradzić?
cole

Odpowiedzi:

14

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

Na przykład, termin S(SS)K2 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 K2 .

Jak widać z poniższej sztuki ASCII, wszystkie reguły redukcji w rachunku S,K2,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,K2,I się kamienia nazębnego, takie, że TK2S zmniejsza się do K2 . Jednakże KK2S zmniejsza się do K2 , stąd K nie może być wyrażona w S,K2,I rachunek.

ZAK
źródło
Bardzo fajny argument!
Noam Zeilberger
Bardzo zręczny i jasny argument. Dziękuję Ci. Być może otworzę osobne pytanie, by zadać pytanie o kompletność Turinga.
cole
5

EDYCJA: Jak zauważają komentarze, jest to tylko częściowa odpowiedź, ponieważ dotyczy ona tylko prostego rachunku S,K2,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:ABA
  • K2:ABB
  • S:(ABC)(AB)(AC)
  • I:AA

KI,S,K2ABB,(ABC)(AB)(AC),AAAABBABA

t,f,uABB(ABC)(AB)(AC)AAt

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

K2,S,IttABAfuAtBS,K2,I

ZAK
źródło
1
Podoba mi się to podejście, ale czy możesz wyjaśnić, jakie zasady przyjmujesz jako rachunek sekwencyjny?
Noam Zeilberger
Czy potrafisz naszkicować, jak udowodnić S w tym ograniczonym rachunku sekwencyjnym? Wydaje się, że nie jest to możliwe z zasadami, które, jak przypuszczałem, mogą mieć na myśli.
Robin Houston
1
@ robin-houston: proszę zobaczyć moją edycję (dodałem również inny, semantyczny argument z tym samym wnioskiem).
ZAK
2
Zgadzam się z Charlesem Stewartem (tutaj: twitter.com/txtpf/status/1123962607306706944 ), że nie jest jasne, jak przejść od niezamieszkania w prostym typie rachunku lambda do niewyrażalności za pomocą kombinacji. Może istnieć argument specyficzny dla K, ale początkowy krok „... wtedy można również zrobić to samo w prostym typie rachunku λ” ogólnie nie ma miejsca (Charles wspomniał o kontrprzykładzie kombinatora Y) . Czy widzisz, że ten argument jest rygorystyczny?
Noam Zeilberger
1
K