W szczególności, jeśli zdefiniowałem nowy jako
zamiast
czy -calculus byłby podstawą do konkurowania?
Domyślam się, że „nie”, tylko dlatego, że nie wydaje mi się, że jestem w stanie zbudować zwykłego kombinatora K z kombinacji , i , 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 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 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?
źródło
Odpowiedzi:
Rozważ warunki rachunkuS,K2,I jako drzewa (z węzłami binarnymi reprezentującymi aplikacje, a liście S,K2 reprezentujące kombinatory.
Na przykład, terminS(SS)K2 będzie reprezentowane przez drzewo
Do każdego drzewaT skojarzyć jego prawy liść, ten, który otrzymujesz, biorąc odpowiednią gałąź na każdym z nich K2 .
@
. Na przykład, na prawo liść z drzewa powyżej jestJak widać z poniższej sztuki ASCII, wszystkie reguły redukcji w rachunkuS,K2,I zachowują skrajnie prawy liść.
Odtąd łatwo zauważyć, że jeśli jakiś terminT 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.
źródło
EDYCJA: Jak zauważają komentarze, jest to tylko częściowa odpowiedź, ponieważ dotyczy ona tylko prostego rachunkuS,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ęcA,B,C są zmienne):
t,f,u
t
t
t
f
u
t
źródło