Welche Funktionen können Kombinatorberechnungsausdrücke berechnen?

13

Ein Kombinatorausdruck (zum Beispiel auf SK-Basis) kann als eine Funktion betrachtet werden, die Kombinatorberechnungsausdrücke auf Kombinatorberechnungsausdrücke abbildet. Das heißt, man kann sich einen Ausdruck X als eine Funktion , wobei die Menge aller syntaktisch gültigen Kombinatorausdrücke in der SK-Basis ist. Diese Zuordnung wird durchgeführt, indem die Eingabe auf den Ausdruck angewendet und dann auf die normale Form reduziert wird, um die Ausgabe zu erhalten.X:LLL

Da die SK-Basis Turing vollständig ist, könnte man naiv annehmen, dass es einen SK-Ausdruck , der jede berechenbare Funktion von bis implementiert . Dies ist jedoch eindeutig nicht der Fall, da das Ergebnis der Reduzierung immer in normaler Form vorliegt. Dies bedeutet, dass es für einen Ausdruck keine Möglichkeit gibt, eine Ausgabe zu erhalten, die nicht in normaler Form vorliegt.XLL

Stattdessen könnte ich mir SK-Kalkülausdrücke als Abbildung von auf , wobei die Menge von SK-Ausdrücken in normaler Form ist. Ist es der Fall, dass es für jede berechenbare Map einen SK-Ausdruck , der diese Map implementiert? Oder gibt es weitere Einschränkungen für die Menge der Funktionen, die auf diese Weise durch Kombinator-Kalkül-Ausdrücke berechnet werden können?LLLf:LLX

Nathaniel
quelle

Antworten:

6

Um den Ball ins Rollen zu bringen und in der Hoffnung, dass andere Menschen tiefere und detailliertere Antworten auf die Struktur der Funktionen L L ′ geben , zitiere ich Korollar 20.3.3 aus Barendregts The Lambda Calculus, Its Syntax and Semantik (aka "die Bibel").λLL

Folgerung 20.3.3: Die Funktion , definiert durch δ ( M , N ) = { T r u e  wenn  M = β η N F a l s e ist  sonst im untypisierten λ - nicht definierbar Kalkül, dh es gibt keinen Term D, so dass D M N = β η δ ( M , N )δ:L2L

δ(M,N)={True wenn M=βηNFeinlse Andernfalls
λD
D M N=βηδ(M,N)
für alle .M,NL

Der Beweis umfasst Überlegungen zu Böhm-Bäumen, die die möglichen "Wirkungen" beliebiger Lambda-Terme auf Normalformen recht gut charakterisieren. Insbesondere kann für jeden nicht konstanten geschlossenen Term on n N und P 1 , ... , P n finden, so dass F x P 1 ... P n = β η x Q 1 ... Q kFnNP1,,Pn

F x P1Pn=βηx Q.1Q.k

kQ.1,,Q.kDδD

Cody
quelle