Charakterisierung unsichtbarer Äquivalenzen durch konfluente Umschreiberegeln

14

Als Antwort auf eine andere Frage, Erweiterungen der Beta-Theorie der Lambda-Rechnung , bot Evgenij die Antwort an:

Beta + die Regel {s = t | s und t sind unlösbare Begriffe}

wo ein Term M lösbar ist, wenn wir eine Folge von Termini finden können, so dass die Anwendung von M auf sie gleich I ist .

Evgenijs Antwort gibt eine Gleichungstheorie über den Lambda-Kalkül, aber keine Theorie, die durch ein Reduktionssystem charakterisiert ist, dh einen konfluenten, rekursiven Satz von Umschreiberegeln.

Nennen wir eine unsichtbare Äquivalenz zu einer Theorie des Lambda-Kalküls, einem Reduktionssystem, das einige nichttriviale Mengen geschlossener unlösbarer Lambda-Terme gleichsetzt, aber keine neuen Gleichungen mit lösbaren Termen hinzufügt.

Gibt es unsichtbare Äquivalenzen zur Beta-Theorie der Lambda-Rechnung?

Postscript Ein Beispiel, das eine unsichtbare Äquivalenz kennzeichnet, aber nicht konfluent ist. Es sei M = (λx.xx) und N = (λx.xxx) , zwei unlösbare Terme. Das Hinzufügen der Regel, die NN zu MM umschreibt , führt zu einer unsichtbaren Äquivalenz mit MM = NN , hat jedoch das fehlerhafte kritische Paar, bei dem NN auf MM und MMN reduziert wird , von denen jedes eine Umschreibung zur Verfügung hat, die sich selbst umschreibt.

pl.programming-languages lambda-calculus lo.logic Charles Stewart
quelle
Der Begriff der unsichtbaren Äquivalenz hängt mit dem Begriff der konservativen Ausdehnung zusammen . Eine konservative Erweiterung einer Theorie ist eine Sammlung von zusätzlichen Begriffen und Gleichungen zur Theorie, die keine neuen Gleichungen zwischen Begriffen in der ursprünglichen Theorie hinzufügen.
Dave Clarke
@supercooldave: Unlösbare Terme sind normale Terme der Theorie, wie (λx.xx) (λx.xx) , und können auf andere (unlösbare) Terme reduziert werden, sind also Teil der normalen Theorie der Lambda-Rechnung. Der Punkt ist, dass sie orthogonal zur Semantik des Lambda-Kalküls sind, das wir aus dem Satz von Böhm erhalten.
Charles Stewart
Sie suchen also nach plus einigen Regeln der gleichen Art wie die Beta-Regel (angegeben durch Syntax statt durch Semantik), so dass <Rest des Posts>? λβ
Evgenij Thorstensen
@Evgenij: Ja. Es ist von entscheidender Bedeutung, dass die neuen Regeln konsequent sind, und natürlich ist es trivial, Beispiele zu finden, wenn dies nicht der Fall ist. Ich werde ein Beispiel hinzufügen, um das Problem zu zeigen.
Charles Stewart

Antworten:

6

Ja. Betrachten Sie bei M = (λx.xx) pro Frage das Umschreiben ζ, das MM p zu MM führt .

Es ist konfluent und charakterisiert so ein Reduktionssystem gegenüber der Lambda-Rechnung. Argumentskizze zur Konfluenz: Da MM geschlossen ist, müssen nur kritische Paare der Form MMN 1 ... N k berücksichtigt werden . Diese können gelöst werden.

Es ist eine unsichtbare Äquivalenz, weil Terme der Form MMI ... I (mit null oder mehr I s) geschlossene unlösbare Terme sind, die sich im Basis-Lambda-Kalkül nur auf sich selbst reduzieren, also verschieden sind, und somit die unendliche Menge von diesen Begriffe sind nichttrivial und werden offensichtlich mit obviously gleichgesetzt.

Ich akzeptiere meine Antwort auf meine Frage nicht gern, daher akzeptiere ich eine Antwort von jemandem, der ein weniger absurd unvollständiges Konfluenzargument liefert.

Charles Stewart
quelle