Kleinstmöglicher Universal-Kombinator

17

Ich suche den kleinstmöglichen universellen Kombinator , gemessen an der Anzahl der Abstraktionen und Anwendungen, die erforderlich sind, um einen solchen Kombinator in der Lambda-Rechnung zu spezifizieren . Beispiele für universelle Kombinatoren sind:

  • Größe 23: λf.f (fS (KKKI)) K
  • Größe 18: λf.f (fS (KK)) K
  • Größe 14: λf.fKSK
  • Größe 12: λf.fS (λxyz.x)
  • Größe 11: λf.fSK

wobei S = λxyz.xz (yz) der Größe 6 und K = λxy.x der Größe 2 die Kombinatoren der SK-Kombinatorrechnung sind . Die ersten 4 Beispiele werden in diesem Artikel beschrieben .

Meine Fragen sind:

  • Gibt es universelle Kombinatoren, die kleiner sind?
  • Was ist der kleinstmögliche Universal-Kombinator?

BEARBEITEN: Siehe auch /math//a/180263/76284 , die hat λazbc.bc(a(λy.c))(die Größe 8 wäre , entspricht der Summe der Größen der SK-Basis). Weiß jemand, wie man S und K von diesem Kombinator ausdrückt?

lo.logic computability lambda-calculus universal-computation combinatory-logic user76284
quelle
Vielleicht ist dies von Interesse: wolframscience.com/nksonline/page-1123a-text?firstview=1
Andrej Bauer
Wie definieren Sie Größe? Kannst du es als Funktion schreiben?
Joshua Herman
Da 6 + 2 = 8 <11 ist, frage ich mich, ob {S, K} die kleinste Basis von Kombinatoren ist, gemessen an der Gesamtgröße.
Noam Zeilberger
Ihre letzte Bearbeitung klingt eher wie eine (teilweise) Antwort.
Emil Jeřábek unterstützt Monica
Wie genau definieren Sie " Kombinator "? Muss es von der Form sein, λx*.Ein der Ees abstraktionsfrei ist?
Peter Taylor

Antworten:

9

Es sollte beachtet werden, dass es immer schwierig ist, Kombinatoren mit bestimmten Reduktionseigenschaften zu finden , und das Finden des kleinsten solchen Kombinators kann leicht unentscheidbar sein (aus trivialen Gründen, da es möglicherweise unentscheidbar sein kann, zu beweisen, dass eine bestimmte Anwendung des Kombinators sogar stoppt).

Es gibt mehrere einfache offene Fragen mit einem ähnlichen Geschmack, z. B. die Probleme Nr. 4, Nr. 6 und Nr. 10 aus der TLCA-Liste der offenen Probleme .

Zu beachten ist, dass Ihr Kombinator mindestens zwei gebundene Variablen haben muss, von denen eine (wie jeder vollständige Satz von Kombinatoren) dupliziert und eine gelöscht werden muss. Dies setzt eine Untergrenze von 4, denke ich (2 Abstraktionen und 2 Erscheinungen einer Variablen), die nicht so weit von der Obergrenze von 11 entfernt ist.

Edit: Noams Kommentare und Verweis schieben die Untergrenze auf 5! Es würde mich nicht wundern, wenn der Beweis auch das Erscheinen der zusätzlichen Variablen erfordert, was uns auf 6 treiben würde.

Cody
quelle
3
Tatsächlich reichen zwei Variablen nicht aus ( dl.acm.org/citation.cfm?id=2100917 , cstheory.stackexchange.com/a/36344/674 ), sodass sich eine geringfügig höhere Untergrenze ergibt (Größe 5 = 3 Abstraktionen und 2 Anwendungen).
Noam Zeilberger
@NoamZeilberger in Ordnung, das ist ein fantastisches Ergebnis, das mir nicht bewusst war!
Cody
7

Für Ihre erste Frage glaube ich, dass dieses Papier ein paar helfen kann. Es hat eine 6-Bit-Kombinator-Rechnung, die auch eine UTM ist. Es hat auch einen universellen Kombinator, der Größe 7 zu haben scheint, wobei ein Element gegeben ist, was Sie wollen. Sie nennen es Zot. http://arxiv.org/pdf/cs/0508056v1.pdf

Ich bin mir nicht sicher, ob Sie sagen oder beweisen können, dass es einen minimalen Kombinator gibt. Das Papier würde vorschlagen, dass es mindestens weniger als 6 Bits sein müsste.

Joshua Herman
quelle
2
Zots Kombinator ist tatsächlich der letzte, der im OP aufgeführt ist: λx.xSK (gemeinsam mit den übergeordneten Sprachen Iota und Jot) mit der Länge 11. Im "6-Bit-Kombinator-Kalkül" (Keraia) sind es die "6-Bits" die Größe der UTM; und es sieht so aus, als wäre es nur eine Kodierung des Lambda-Kalküls, kein Kombinator-Kalkül (und daher keinen eingebauten Universal-Kombinator).
2012rcampion