Wie kann die Angemessenheit einer Kodierung der Lambda-Rechnung an sich festgestellt werden?

In der Arbeit Diskriminierung codierter Lambda-Terme - Henk Barendregt ist ein Codierungs- eines Lambda-Terms ein Term, bei dem (und seine Teile) auf Lambda-definierbare Weise daraus rekonstruiert werden können. Im Wesentlichen müssen wir in der Lage sein, einen Selbstinterpreter zu schreiben : $\ulcorner M \urcorner$ $M$ $M$ $\mathsf E$

E ⌜ M ⌝ =_{β} M .

$\mathsf E \ulcorner M \urcorner =_\beta M.$

Es gibt eine Vielzahl von Codierungen wie die von Kleene, bei denen natürliche Zahlen verwendet werden. Die effizienteste moderne Codierung ist eine Syntax höherer Ordnung von Mogensen. Eine andere mögliche (triviale) Codierung ist die Identitätsfunktion, dann ist der Interpreter wieder die Identitätsfunktion.

Gibt es eine vernünftige Vorstellung von einer "angemessenen Codierung", die triviale Codierungen verbietet?

Diese Frage tauchte auf, wenn man das Stoppproblem betrachtet, das eher für Lambda-Berechnungen als für Turing-Maschinen gilt: Wenn es in Bezug auf die triviale Codierung angegeben wird, gilt dies aus dem trivialen Grund, dass wir mit einem zitierten Lambda-Begriff im Wesentlichen nichts tun können.

Anders ausgedrückt: Welche Funktionen sollten wir erwarten, um mit zitierten Lambda-Begriffen rechnen zu können?

Ich kann einige auflisten wie: Zählen der Tiefe des Begriffs, Aufnehmen von Subtermen, Ermitteln, ob der Wurzelknoten eines Begriffs ein Lambda oder eine Anwendung ist, ... aber ich würde zögern, eine "angemessene Codierung" zu definieren, indem ich nur verschiedene Funktionen aufführe das kam mir in den Sinn.

lambda-calculus encoding Brennan.Tobias
quelle

Wählen Sie eine bestimmte konkrete "angemessene Kodierung" (z. B. die von Kleene). Angenommen, eine Codierung ist ausreichend, wenn ein Begriff einen codierten Term für die Kleene-Codierung verwendet. Das ist ein bisschen albern, aber würde das für Ihre Zwecke funktionieren?

ι

$\iota$

λ

$\lambda$

ι

$\iota$

ι (M)

$\iota(M)$

Cody

Ich denke, Sie haben tatsächlich die Schlüsseloperationen aufgelistet: die Art des Begriffs (Variable, Abstraktion, Anwendung) angeben und gegebenenfalls Unterbegriffe verwenden. Der einzige heikle Punkt ist die Darstellung der Bindung von Lambdas, aber Sie können dies mit der De-Bruijn-Notation tun. Daraus folgt jede andere sinnvolle Operation (z. B. Zählen der Tiefe), da Sie einen Begriff vollständig dekonstruieren können. Würdest du zustimmen?

Damiano Mazza

Was @DamianoMazza gesagt hat. Ich habe versucht, einige davon in math.andrej.com/2016/01/04/…

Andrej Bauer

@Andrej Bauer Ich kann nicht glauben, dass du all das Zeug brauchst. Mein Problem nicht zu lösen.

Andrea Asperti

Natürlich nicht, das relevante Bit ist am Anfang nur ein Absatz, der erklärt, was für eine akzeptable Syntaxcodierung erforderlich ist.

Andrej Bauer

Antworten:

Wie von anderen hervorgehoben, besteht die offensichtliche Definition einer "angemessenen" Codierung darin, dass sie mit jeder Standardcodierung gleichübersetzbar ist. Die Frage ist daher, solche Codierungen im Hinblick auf elementarere Eigenschaften zu charakterisieren.

( Historischer Hinweis . Smullyan untersuchte diese Frage im Kontext der kombinatorischen Logik. Als ich Student war, schlug Henk Barendregt mir Smullyans Vermutungen als Forschungsproblem vor - was zu meiner ersten wissenschaftlichen Veröffentlichung führte.) Siehe

http://drops.dagstuhl.de/opus/volltexte/2011/3249/ $\newcommand{\code}[1]{\overline{#1}}$

Zusammenfassend betrachten wir anhand einer Zuordnung , ob es Kombinatoren gibt, die bestimmte Eigenschaften erfüllen. Die wichtigsten sind: $\code{\cdot} : \Lambda \to \Lambda$

$A\, \code{M}\, \code{N} = \code{MN}$
$B\, \code{M} = \code{\code{M}}$
$P_i\, \code{M_0 M_1} = \code{M_i},\quad i \in \{0,1\}$
$Z_b\, \code{M} = \begin{cases} \lambda x y.x &M \equiv b \in \{I,K,S\}\\ \lambda xy.y &otherwise \end{cases}$
$\Delta\, \code{M}\, \code{N} = \begin{cases} \lambda x y. x &M \equiv N\\ \lambda x y.y &otherwise \end{cases}$
$U\, \code{M} = \code{M}^s$ , wobei eine Standardcodierung ist $\code{\cdot}^s$
$U^{-1}\, \code{M}^s = \code{M}$

Es ist leicht zu erkennen, dass jede adäquate Codierung diese Eigenschaften aufweist. Das Hauptergebnis des Papiers (Folgerung 14) ist, dass für eine angemessene Codierung eine der folgenden Angaben ausreicht:

$A + \Delta$ ;
$U^{-1} + \Delta$ ;
$U^{-1} + P_i + Z_b$ ;
$P_i + Z_b +$ "Der Bereich von ist in einer rekursiv aufzählbaren Menge enthalten, und es gibt einen Kombinator, der entscheidet, ob ein bestimmtes Element dieser Menge im Bereich liegt oder nicht." $\code{\cdot}$

Andrew Polonsky
quelle

Dies ist keine Antwort. Es ist eine Ausarbeitung der Frage, die für mich interessant aussieht und vielleicht mehr Aufmerksamkeit verdienen sollte, als sie tatsächlich erhalten hat.

Lassen Sie mich zunächst sagen, dass die Definition von Barendregt eine wichtige Bedingung enthält, die von Brennan weggelassen wurde, nämlich die Tatsache, dass in normaler Form muss , was die Identitätsfunktion als angemessene Codierung sofort ausschließt. $\lceil M \rceil$

Nun kann die Frage nach Codys Vorschlag genauer formuliert werden.

Sind sie bei zwei Codierungen rekursiv isomorph? Mit anderen Worten, nehmen wir zwei Codierungen an, so dass

𝖤_{1} ⌈ M ⌉_{1} =_{β} M a n d 𝖤_{2} ⌈ M ⌉_{2} =_{β} M

$𝖤_1 \lceil M \rceil_1 =_\beta M \hspace{1cm} and \hspace{1cm}𝖤_2 \lceil M \rceil_2 =_\beta M$ existiert ein Lambda-Term so dass für jeden Term

F

$F$

M

$M$

E_{2} (F ⌈ M ⌉_{1}) =_{β} M

$E_2 (F \lceil M \rceil_1) =_\beta M$ und umgekehrt?

Wenn die Antwort nicht lautet, welche "minimalen" abstrakten Anforderungen müssen hinzugefügt werden, um dies sicherzustellen?

Andrea Asperti
quelle