Wie veranschaulicht der Y-Kombinator die Inkonsistenz des Lambda-Kalküls?

44

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 ?λ

Ben I.
quelle
3
FWIW, dieser Absatz ist seit Januar 2014 im Wikipedia-Artikel enthalten, als er in dieser umfassenden Neufassung fast des gesamten Artikels eingeführt wurde .
Ilmari Karonen

Antworten:

51

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.AA¬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=3n=2

Die Curry-Howard-Korrespondenz ist eine Parallele zwischen typisierten Kalkülen und Beweissystemen.

  • Typen entsprechen logischen Aussagen;
  • Begriffe entsprechen Beweisen;
  • bewohnte Typen (dh Typen, bei denen es einen Begriff dieses Typs gibt) entsprechen wahren Aussagen (dh Aussagen, bei denen es einen Beweis für diese Aussage gibt);
  • Programmevaluierung (dh Regeln wie Beta) entsprechen Transformationen von Beweisen (die richtige Beweise besser in richtige Beweise umwandeln sollten).

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.YY(λ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:

  • Die Lambda-Rechnung ist nicht „inkonsistent“, dieses Konzept gilt nicht.
  • Ein typisierter Lambda-Kalkül, der jedem Lambda-Term einen Typ zuweist, ist inkonsistent. Einige typisierte Lambda-Kalküle sind so, andere machen einige Begriffe untypisierbar und sind konsistent.
  • Typisierten Lambda - Kalküle ist nicht die einzige Daseinsberechtigung für das Lambda - Kalkül und sogar widersprüchlich typisierten Lambda - Kalküle sind sehr nützliche Werkzeuge - nicht nur , um die Dinge zu beweisen.
Gilles 'SO - hör auf böse zu sein'
quelle
2
Wow, ich muss hier viel auspacken. Danke für die ausführliche Erklärung. Es wird einige Zeit dauern, bis ich alles in den Griff bekomme.
Ben I.
4
Technisch sehen untypisierten als un i eingegeben haben , können Sie eine CH Entsprechung zwischen dem untypisierten Lambda - Kalkül und einer Logik machen. Es ist nur eine sehr, sehr langweilige (und sicherlich inkonsistente) Logik. Proof-Assistenten wie NuPRL trüben das Wasser ein wenig. Die Objektsprache von NuPRL enthält den untypisierten Lambda-Kalkül, und Sie können den Y-Kombinator leicht definieren. NuPRL teilt die Dinge ein bisschen anders auf, sodass es ein Typverfeinerungssystem anstelle eines Typsystems gibt. Die Übung besteht nicht darin, gut typisierte Begriffe zu erstellen, sondern die Typisierungsableitungen.
Derek Elkins
Bin ich es nur, oder ist es seltsam, das Paradigma "Sätze als Typen" der untypisierten Lambda-Rechnung aufzuzwingen? Ich habe immer gesehen , wie Menschen über Logik in nicht typisierten Lambda - Kalkül sprechen von bestimmten Objekten Einführung die Boolesche Werte zu sein trueund false, 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).
Trivial (beweist jede Aussage) und enthält Widersprüche sind zwei verschiedene Eigenschaften. Während sie in der klassischen Logik gleichwertig sind, kann ein System für parakonsistente Logik inkonsistent und nicht trivial sein.
Taemyr
1
"Inkonsistent" bedeutet für eine λ-kalkülbasierte Logik "ordnet jedem Begriff jeden Typ zu" und nicht "ordnet jedem Begriff einen Typ zu" (obwohl der erstere aus dem letzteren folgt); es gibt viele λ-kalkülbasierte sprachen, die inkonsistenten logiken entsprechen, bei denen jedoch nicht jeder λ-kalkülbegriff typisierbar ist.
Jonathan Cast
6

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.xa(ba)ababa(ba)λx.λy.xy(ab)(ab)(ab)(ab)

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))(aa)a(aa)a

(aa)aaa(¬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(aa)a

Nicht-kontextuelle Rechtschreibung
quelle
1
CH bezieht Typen auf Sätze, Programme auf Beweise und sogar Reduzierungen auf Beweistransformationen. Es geht nicht nur um Typen. Als nächstes entsprechen nur bewohnte Typen Tautologien. ist ein (polymorpher) Lambda-Kalkül-Typ, auch wenn keine Begriffe darin vorkommen. Angenommen, Sie meinen Typen wie , dann ist es völlig in Ordnung, solche Typen zu akzeptieren. Die Frage ist, ob dieser Typ einen Einwohner hat oder nicht. Umgekehrt können wir der STLC primitive Terme hinzufügen, die die entsprechende Logik inkonsistent machen, ohne das Typsystem zu erweitern. a . ( a a ) aa,b.aba.(aa)a
Derek Elkins
@DerekElkins, was für primitive Begriffe? Auch, wenn ich richtig verstehe, ist dies nur anzunehmen (a -> a) -> a wird immer bewohnt, was die Inkonsistenz erzeugt? Es gibt also keine Inkonsistenz mehr mit einer Programmiersprache, die einen Abschlussnachweis erfordert? Oder gibt es eine andere Ursache für Inkonsistenzen in untypisierter oder Hindley-Milner-typisierter Lambda-Rechnung?
Hibou57
1
@ Hibou57 Primitive Begriffe, also Konstanten, mögen 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 xfixAAfix(λx.x)δfix
Derek Elkins