Basissätze für die Kombinatorrechnung

Es ist bekannt, dass die S- und K-Kombinatoren einen Basissatz für die Kombinatorrechnung bilden, in dem Sinne, dass alle anderen Kombinatoren in diesen ausgedrückt werden können. Es gibt auch Currys B-, C-, K-, W-Basis, die die gleiche Eigenschaft hat. Es muss unendlich viele solcher Basen geben, aber ich kenne keine anderen.

Mir ist bekannt, dass es eine Reihe von Single-Combinator-Basen gibt, wie den Iota-Combinator und die verschiedenen anderen, die von Fokker konstruiert / überprüft wurden . Dies sind jedoch "falsche" Kombinatoren, was bedeutet, dass sie eher als andere Kombinatoren als als reine Abstraktionen ausgedrückt werden. ¹ Für diese Frage interessieren mich nur Basissätze, die sich aus geeigneten Kombinatoren zusammensetzen.

Gibt es auch eine Untersuchung der anderen möglichen Basissätze? Ideal wäre etwa die Untersuchung Wolframs verschiedener anderer Rechenmodelle, in denen die verschiedenen Kombinationen systematisch untersucht werden. Insbesondere interessiert mich, ob einfache Beispiele für die folgenden Dinge bekannt sind:

• Ein minimaler Basissatz, der den I-Kombinator enthält. (Ich verwende "minimal", um zu bedeuten, dass die SKI-Basis nicht mehr zählt, wenn Sie ein Mitglied entfernen.)
• Ein minimaler Basissatz, der den Y-Kombinator oder den Kombinator (auch Spottdrossel genannt) enthält.$\omega$

Alle anderen Informationen über andere mögliche Grundlagen für kombinatorische Logik als S, K und B, C, K, W wären wirklich hilfreich.

Im weiteren Sinne interessiert mich die Untersuchung des Kombinationskalküls als rein mechanisches System, dh als Satz von Transformationsregeln für Binärbäume mit beschrifteten Knoten, die keiner besonderen semantischen Interpretation bedürfen. Hinweise auf Ressourcen, die diesen Ansatz verfolgen, sind sehr willkommen. ( Um einen Spottdrossel zu verspotten, wird dieser Ansatz gewählt, der jedoch unvollständig dargestellt wird, während Barendregt's Lambda-Kalkül stark an die Semantik gebunden ist, was es mir schwer macht, die rein mechanischen Aspekte zu extrahieren, an denen ich interessiert bin.)

¹ _{Um genau zu sein: Im Lambda-Kalkül ist ein richtiger Kombinator ein Ausdruck der Form , wobei P ( x 1 , x 2 , … ) nur hat , usw. als freie Variablen und enthält keine Abstraktionen. So ist zum Beispiel ein geeigneter Kombinator, aber$(\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) )$ist nicht, weil es enthält, das auf einen Lambda-Term angewendet wird.$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))$

Jeder Satz von Kombinatoren, der einen aufhebenden Kombinator (wie K), einen zusammensetzenden Kombinator (wie B), einen permutierenden Kombinator (wie C), einen duplizierenden Kombinator (wie W) und den Identitätskombinator I enthält, ist eine Basis. Wenn der I-Kombinator zufällig von Ihren vier anderen Kombinatoren abgeleitet ist, reichen diese vier allein aus.

Dies bedeutet, dass etwas wie B, T, M, K, I, wobei Tab = ba und Ma = aa ist, auch eine Basis ist. Tatsächlich genügt B, T, M, K, da ich von B, T, M, K abgeleitet werden kann (dies ist nicht leicht zu beweisen; der Beweis besteht darin, zuerst S von B, T, M abzuleiten und dann I = zu nehmen SKK.)