Unvollständige Basis von Kombinatoren

Dies ist von dieser Frage inspiriert . Sei die Sammlung aller Kombinatoren, die nur zwei gebundene Variablen haben. Ist kombinatorisch vollständig? $\mathcal{C}$ $\mathcal{C}$

Ich glaube, die Antwort ist negativ, aber ich konnte keine Referenz dafür finden. Ich würde mich auch für Referenzen zum Nachweis der kombinatorischen Unvollständigkeit von Mengen von Kombinatoren interessieren (ich kann sehen, warum die Menge die aus Kombinatoren mit nur einer gebundenen Variablen besteht, unvollständig ist, daher sollten diese Mengen mehr als nur Elemente von ). $\mathcal{D}$ $\mathcal{D}$

lo.logic lambda-calculus combinatory-logic tci
quelle

Können Sie klarstellen, was Sie unter der Anzahl der gebundenen Variablen eines Kombinators verstehen (= geschlossener Lambda-Term)? Gesamtzahl der Lambda-Abstraktionen?

Noam Zeilberger

Ja, das habe ich gemeint.

27.

Vielleicht ist das nicht genau das, was Sie gemeint haben ... vielleicht meinen Sie eher die Gesamtzahl der verschiedenen Variablen, die in Lambda-Abstraktionen verwendet werden, so dass zum Beispiel

hat zwei unterschiedliche gebundene Variablen, obwohl es vier Lambda-Abstraktionen gibt? In diesem Fall scheint Rick Statman genau diese Frage (negativ) in " Zwei Variablen sind nicht genug " beantwortet zu haben .

(λ x . x (λ y . y)) (λ x . λ y . x y)

$(\lambda x.x(\lambda y.y))(\lambda x.\lambda y.x y)$

Noam Zeilberger

Recht. Ich denke, das ist die Antwort, nach der ich gesucht habe, und ich habe definitiv erwartet, dass es ein Ergebnis von Statman ist. Ich habe noch nicht nachgesehen, aber ich denke, dies würde auch eine negative Antwort auf die von mir erwähnte Frage geben. Wenn Sie es als Antwort posten würden, würde ich es gerne akzeptieren.

tci

Antworten:

[Den Kommentar zu einer Antwort erweitern.]

$t$

the total number of distinct bound variable names in t

$\text{the total number of distinct bound variable names in }t$

t = (λ x . x (λ y . y)) (λ x . λ y . y x)

$t = (\lambda x.x(\lambda y.y))(\lambda x.\lambda y.yx)$

α

$\alpha$

t

$t$

α

$\alpha$

t^{'} = (λ x . x (λ y . y)) (λ a . λ b . b a)

$t' = (\lambda x.x(\lambda y.y))(\lambda a.\lambda b.ba)$

t^{'}

$t'$

t

$t$

the maximum number of free variables in a subterm of t

$\text{the maximum number of free variables in a subterm of }t$

α

$\alpha$

$\mathcal{C}$

Es scheint, dass der ursprüngliche Beweis dafür in einem technischen Bericht von Rick Statman enthalten ist:

Kombinatoren erblich der zweiten Ordnung. Technischer Bericht 88-33 der Mathematikabteilung von Carnegie Mellon, August 1988. ( pdf )

$\beta$

Zwei Variablen reichen nicht aus. Tagungsband der 9. italienischen Konferenz für Theoretische Informatik, S. 406-409, 2005. ( acm )

$Hn$ $Hn$ $n+1$ $\beta$ $n$ $S = \lambda x.\lambda y.\lambda z.(xz)(yz)$ $n$ $n$ $Hn$ $n+1$

Noam Zeilberger
quelle