Ist der SK2-Kalkül eine vollständige Basis, wobei K2 der umgedrehte K-Kombinator ist?

10

Insbesondere, wenn ich ein neues als anstelle von Wäre der -Kalkül eine konkurrierende Basis?K2

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

Meine Vermutung ist "nein", nur weil ich den regulären K-Kombinator nicht aus den , und Kombinatoren konstruieren kann , aber ich habe keinen Algorithmus, dem ich folgen kann, und ich habe auch keine gute Intuition über Dinge aus diesen Kombinatoren zu machen.SIK2

Es scheint, als könnten Sie mit dem regulären -Kalkül definieren, aber ich konnte nicht wirklich rückwärts arbeiten, um eine Ableitung von in Bezug auf und den Rest zu erhalten.

K2=KI
{S,K,(I)}KK2

Mein Versuch, zu beweisen, dass es nicht funktional vollständig war, versuchte im Wesentlichen, jede von diesen Kombinatoren erreichbare Funktion erschöpfend zu konstruieren, um zu zeigen, dass Sie eine Sackgasse erreichen (eine Funktion, die Sie zuvor gesehen haben), unabhängig davon, welche Kombinatoren Sie verwenden. Mir ist klar, dass dies nicht unbedingt für funktional unvollständige Sätze von Kombinatoren zutreffen wird (z. B. wird der Kombinator allein niemals in eine Sackgasse geraten, wenn er auf sich selbst angewendet wird), aber dies war mein bester Gedanke. Ich war immer in der Lage, den Kombinator zu verwenden, um mich aus einer Sackgasse herauszuschleichen, die ich für endgültig hielt, und bin mir daher nicht mehr so ​​sicher, ob dieser Ansatz machbar ist.KS

Ich habe diese Frage auf StackOverflow gestellt , wurde jedoch aufgefordert, sie hier zu posten. Ich habe einige Kommentare zu diesem Beitrag erhalten, bin mir aber nicht sicher, ob ich sie richtig verstanden habe.

Bonus: Wenn es keine vollständige Basis ist, ist die resultierende Sprache dennoch Turing-vollständig?

cole
quelle
Das ist ein schönes Puzzle. Es scheint, dass Sie mit S und K 'nur Terme erzeugen können, deren Kopfnormalformen bis zu drei führende λs haben (dh Terme, die sich auf die Form λx₁.λx₂.λx₃. Xᵢ t₁ ... tₙ normalisieren) ein anderer Weg, um Unvollständigkeit zu beweisen, obwohl es etwas schwierig zu formalisieren scheint. Sie erreichen jedoch definitiv nie eine "Sackgasse": Beginnen Sie mit der Definition von I = λx.x = K2 K2, und wiederholen Sie dann durch Wiederholen der Transformation t ↦ S t K2 λx.x I ... I für jede Zeichenfolge von Is .
Noam Zeilberger
... Und sorry, mit "Unvollständigkeit" meine ich die Unvollständigkeit von SK 'als kombinatorische Grundlage für den untypisierten Lambda-Kalkül. Ich habe auch keine gute Intuition dafür, ob es Turing-vollständig ist oder nicht (was durch kombinatorische Vollständigkeit impliziert würde, aber nicht umgekehrt).
Noam Zeilberger
Cross-posted: stackoverflow.com/q/55148283/781723 , cs.stackexchange.com/q/108741/755 . Bitte posten Sie nicht dieselbe Frage auf mehreren Websites . Jede Community sollte einen ehrlichen Versuch haben, zu antworten, ohne dass jemand Zeit verschwendet.
DW
Mein Fehler @DW, kann ich irgendetwas tun, um dies zu beheben?
Cole

Antworten:

14

Betrachten Sie die Terme des S,K2,I Kalküls als Bäume (wobei Binärknoten Anwendungen darstellen und S,K2 -Blätter die Kombinatoren darstellen.

Zum Beispiel würde der Term S(SS)K2 durch den Baum dargestellt

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

T@K2

S,K2,I

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

TTTTTS,K2,ITK2SK2KK2SK2KS,K2,I

ZAK
quelle
Sehr schönes Argument!
Noam Zeilberger
Sehr glattes und klares Argument. Vielen Dank. Vielleicht werde ich eine separate Frage zur Vollständigkeit von Turing stellen.
Cole
5

S,K2,I


A,B,C

  • 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
quelle
1
Ich mag den Ansatz, aber könnten Sie klarstellen, welche Regeln Sie als sequentiellen Kalkül verwenden?
Noam Zeilberger
Können Sie skizzieren, wie Sie S in diesem eingeschränkten sequentiellen Kalkül beweisen können? Mit den Regeln, von denen ich vermutete, dass Sie sie meinen, scheint es nicht möglich zu sein.
Robin Houston
1
@ robin-houston: siehe meine Bearbeitung (ich habe auch ein anderes semantisches Argument mit der gleichen Schlussfolgerung hinzugefügt).
ZAK
2
Ich stimme Charles Stewart (hier drüben : twitter.com/txtpf/status/1123962607306706944 ) zu, dass es nicht klar ist, wie man mit unbewohntem Lambda-Kalkül von Unbewohnbarkeit zu Unaussprechlichkeit mit Kombinatoren übergeht. Es mag ein spezifisches Argument für K geben, aber der erste Schritt "... dann könnte man auch das Gleiche im einfach typisierten λ-Kalkül tun" gilt im Allgemeinen nicht (Charles erwähnte das Gegenbeispiel des Y-Kombinators). . Sehen Sie, dass dieses Argument rigoros ist?
Noam Zeilberger
1
K