Auf der Wikipedia-Seite für Fixed Point Combinators ist der eher mysteriöse Text geschrieben
Der Y-Kombinator ist ein Beispiel dafür, was den Lambda-Kalkül inkonsistent macht. Es ist also mit Argwohn zu betrachten. Es ist jedoch sicher, den Y-Kombinator nur dann zu berücksichtigen, wenn er in der mathematischen Logik definiert ist.
Habe ich einen Spionageroman geschrieben? Was in aller Welt ist mit den Aussagen gemeint, dass -calculus "inkonsistent" ist und dass es "mit Argwohn betrachtet" werden sollte ?
Antworten:
Es ist inspiriert von realen Ereignissen, aber die Art und Weise, wie es angegeben wird, ist kaum erkennbar und „sollte mit Argwohn betrachtet werden“ ist Unsinn.
Konsistenz hat in der Logik eine genaue Bedeutung: In einer konsistenten Theorie können nicht alle Aussagen bewiesen werden. Inklassischen Logik, dies auf das Fehlen eines Widerspruchs äquivalent ist, dh eine Theorie ist inkonsistentwenn und nur wenn es eine Aussageso dass die Theorie sowohl beweistund seine Negation.A A ¬A
Was bedeutet das für die Lambda-Rechnung? Nichts. Die Lambda-Rechnung ist ein Umschreibungssystem, keine logische Theorie.
Es ist möglich, die Lambda-Rechnung in Relation zur Logik zu betrachten. Betrachten Sie Variablen als Repräsentation einer Hypothese in einem Beweis, Lambda-Abstraktionen als Beweise unter einer bestimmten Hypothese (repräsentiert durch die Variable) und die Anwendung als Zusammenstellung eines bedingten Beweises und Beweises der Hypothese. Dann entspricht die Beta-Regel der Vereinfachung eines Beweises durch Anwendung von modus ponens , einem Grundprinzip der Logik.
Dies funktioniert jedoch nur, wenn der bedingte Beweis mit einem Beweis der richtigen Hypothese kombiniert wird. Wenn Sie einen bedingten Beweis haben, der annimmt, und Sie auch einen Beweis von , können Sie sie nicht miteinander kombinieren. Wenn Sie diese Interpretation des Lambda-Kalküls anwenden möchten, müssen Sie eine Einschränkung hinzufügen, dass nur Beweise der richtigen Hypothese auf bedingte Beweise angewendet werden. Dies wird als Typsystem bezeichnet. Die Einschränkung ist die Typisierungsregel, nach der beim Übergeben eines Arguments an eine Funktion der Typ des Arguments mit dem Parametertyp der Funktion übereinstimmen muss.n=3 n=2
Die Curry-Howard-Korrespondenz ist eine Parallele zwischen typisierten Kalkülen und Beweissystemen.
Ein typisierter Kalkül mit einem Festkomma-Kombinator wie ermöglicht die Bildung eines beliebigen Terms (versuchen Sie, auszuwerten ). Wenn Sie also die logische Interpretation durch die Curry-Howard-Korrespondenz nehmen, erhalten Sie eine inkonsistente Theorie. Siehe Widerspricht der Y-Kombinator der Curry-Howard-Korrespondenz? für mehr Details.Y Y(λx.x)
Dies ist für die reine Lambda-Rechnung, dh für die typenlose Lambda-Rechnung, nicht sinnvoll.
In vielen typisierten Kalkülen ist es unmöglich, einen Festkomma-Kombinator zu definieren. Diese typisierten Kalküle sind in Bezug auf ihre logische Interpretation nützlich, jedoch nicht als Grundlage für eine Turing-vollständige Programmiersprache. In einigen typisierten Kalkülen ist es möglich, einen Festkomma-Kombinator zu definieren. Diese typisierten Kalküle sind als Grundlage für eine Turing-vollständige Programmiersprache nützlich, jedoch nicht in Bezug auf ihre logische Interpretation.
Abschließend:
quelle
true
undfalse
, und Sätze waren Dinge , die boolean Wert ausgegeben hatte. (und wurden nur als Vorschläge auf dem Gebiet der Dinge , wo es tut Ausgabe einen Booleschen Wert).Ich möchte einen zu dem hinzufügen, was @Giles gesagt hat.
Die Curry-Howard-Entsprechung bildet eine Parallele zwischen Begriffen (genauer gesagt den Typen von Begriffen) und Beweissystemen.λ λ
Zum Beispiel hat den Typ (wobei "Funktion von bis " bedeutet), der der logischen Aussage entspricht, die . Die Funktion hat den Typ , der . Wir können jeden Lambda-Kalkül-Typ in eine logische Tautologie umwandeln, indem wir Funktionen in gewissem Sinne "Mustervergleich" unterziehen.λx.λy.x a→(b→a) a→b a b a⟹(b⟹a) λx.λy.xy (a→b)→(a→b) (a⟹b)⟹(a⟹b)
Das Problem entsteht, wenn wir den Y-Kombinator betrachten, der als . Das Problem tritt auf, weil wir erwarten, dass der Y-Kombinator als "Fixpunkt" -Kombinator den Typ (weil er eine Funktion von einem Typ zu demselben Typ annimmt und einen feststehenden Typ findet). Punkt für diese Funktion, die diesen Typ hat). Die Umwandlung in eine logische Anweisung ergibt . Das ist ein Widerspruch:λf.(λx.f(xx))(λx.f(xx)) (a→a)→a (a⟹a)⟹a
Das Akzeptieren von in einem Typsystem führt zu einer Inkonsistenz des Typsystems. Das heißt, wir können entweder(a→a)→a
quelle
fix
. Sie können einfach behaupten, dass es für jeden Typ eine Konstante gibt . Dies führt bereits zu einem inkonsistenten System in Bezug auf CH, da impliziert wird, dass jeder Typ von bewohnt wird . Sie könnten zusätzlich -Regeln hinzufügen , um compute zu machen, und das würde zum Beispiel die STLC mit Naturals in ein Turing-vollständiges System verwandeln, aber Sie müssen diese Rechenregeln und das System nicht hinzufügen wäre immer noch inkonsistent. A f i x (λx.x)δ f i x