Combinator Logik Axiome

Question

Ich bin Durchführung einiger Experimente beweisen mit combinator Logik, das ist vielversprechend, aber es gibt einen Stolperstein:es wurde darauf hingewiesen, dass in combinator Logik ist es wahr, dass z.B.I = SKK, aber dies ist kein Satz, es muss Hinzugefügt werden, wie ein axiom.Kennt jemand eine vollständige Liste der Axiome, die Hinzugefügt werden müssen?

Edit:Natürlich können Sie beweisen, von hand, I = SKK, aber es sei denn, mir fehlt etwas, es ist nicht ein Satz im system der combinator Logik mit Gleichheit.Dass gesagt wurde, können Sie nur makro erweitern, ich SKK...aber ich bin noch etwas wichtiges fehlt.Unter der Menge von Klauseln p(X) und ~p(X), die leicht zu lösen sind, um einen Widerspruch in ordinary first-order logic, und konvertiert Sie zu SK, Durchführung der substitution und der Bewertung aller Anrufe von S und K, mein Programm erzeugt die folgende (wo bin ich mit dem ' für Unlambda ist backtick):

"eq "s "s "s" k s "s "s" k s "N 'k' k 'k eq "s "s 'k 'k k 'k k "s" k k 'k' false 'k' true 'k true

Es sieht vielleicht, was ich brauche, ist eine entsprechende Reihe von Regeln für den Umgang mit der partiellen ruft 'k und "s, ich bin einfach nicht sehen, was die Regeln sein sollte, und die ganze Literatur, die ich finden kann, in diesem Bereich geschrieben wurde für eine Zielgruppe von Mathematikern nicht-Programmierer.Ich vermute, die Antwort ist wahrscheinlich ganz einfach, wenn Sie verstehen es.

Answer 1

Manche Lehrbücher definieren Ich als bloße alias für ((N K) K).In diesem Fall sind Sie identisch (als Begriffe) per definitionem.Um zu beweisen, Ihre Gleichheit (als Funktionen), brauchen wir nur zu beweisen, dass die Gleichheit ist reflexiv, was erreicht werden kann durch eine Reflexivität axiom Schema:

• Proposition `E = E"ist ableitbar (Reflexivität axiom-Schema instantiiert für jede mögliche Begriffe gekennzeichnet hier durch die metavariable E)

Also, ich nehme an, in den folgenden, dass Ihre Fragen untersucht ein anderer Ansatz:wenn combinator Ich nicht definiert bloße alias für zusammengesetzte Begriff ((N K) K), aber eingeführt, als standalone-basic combinator konstant auf seinen eigenen, dessen operationelle Semantik erklärt explizit von axiom Schema

• ``(Ich E) = E"ist ableitbar (I-axiom Schema)

Ich nehme an, Deine Frage fragt

ob wir ableiten können formal (noch in das system), dass eine solche standalone-definiert Ich verhält sich genau so, wie ((N K) K), wenn verwendet, als Funktionen in Kürzungen?

Ich denke, wir können, aber wir müssen resort zu einem stärkeren tools.Ich vermuten, dass die übliche axiom-Schemata sind nicht genug, wir haben zu erklären, auch die extensionality Eigenschaft (Gleichheit von Funktionen), das ist der wichtigste Punkt.Wenn wir wollen, zu formalisieren extensionality als ein axiom, müssen wir ergänzen unsere Sprache mit Objekt freie Variablen.

Ich denke, wir haben zu verabschieden, die ein solcher Ansatz für den Aufbau kombinatorischer Logik, die wir haben, ermöglichen auch die Verwendung von Variablen in der Objekt-Sprache.AH, natürlich, ich meine "nur" kostenlos Wertsachen.Verwendung von gebundenen Variablen wäre eine Täuschung, wir haben zu bleiben drinnen das Reich der kombinatorischen Logik.Mit kostenlosen varaibles ist kein Betrug, es ist eine ehrliche Werkzeug.Also, wir können den formalen Nachweis, dass Sie erforderlich.

Neben der unkomplizierten Gleichheit Axiome und Regeln der Inferenz (Transitivität, Reflexivität, Symmetrie, Leibniz-Vorschriften), wir müssen hinzufügen eine extensionality rule of inference für die Gleichstellung.Hier ist der Punkt, wo die freien Variablen egal.

In Csörnyei 2007:157-158, die ich gefunden habe, wurde der folgende Ansatz.Ich denke, dass dieser Weg der Nachweis kann erfolgen.

Einige Bemerkungen:

Die meisten der Axiome sind in der Tat axiom-Schemata, bestehend aus unendlich vielen axiom-Instanzen.Die Instanzen müssen instanziiert werden für jeden möglich E, F, G Bedingungen.Hier benutze ich Kursiv für metavariables.

Die oberflächliche unendliche Natur des axiom-Schemata nicht zu erhöhen die Berechenbarkeit von Problemen, denn Sie können angegangen werden in einer endlichen Zeit:unser axiomensystem ist rekursive.Es bedeutet, dass eine kluge parser entscheiden können, in einer endlichen Zeit (übrigens sehr effektiv), ob eine gegebene Aussage ist ein Beispiel für ein axiom, das Schema, oder nicht.Also, die Verwendung von axiom-Schemata nicht erheben weder theoretische noch praktische Probleme.

Lassen Sie uns jetzt scheinen unsere Rahmen:

Sprache

ALPHABET

Konstanten:Die folgenden drei genannt werden Konstanten: K, S, Ich.

Ich fügte hinzu, die Konstante Ich nur weil Deine Frage setzt Voraus, dass wir haben nicht definiert, wird der combinator Ich als eine bloße alias - /makro für zusammengesetzte Begriff S K K, aber es ist eine standalone-Konstante auf seine eigenen.

Ich werde mich bezeichnen Konstanten durch die fettgedruckten römischen Provinzhauptstädten.

Zeichen der Anwendung:Ein @ - Zeichen `Anwendung" ist genug (Präfix-notation, die mit stelligkeit 2).Als syntaktischen Zucker, das ich hier verwende, Klammern anstelle der expliziten Anwendung anmelden:Ich darf die explizite sowohl das öffnen ( und schließen ) von Zeichen.

Variablen:Obwohl combinator Logik nicht machen Verwendung von gebundenen Variablen, Umfang etc, aber wir können uns vorstellen freien Variablen.Ich vermute, Sie sind nicht nur syntaktischer Zucker, Sie können zur Stärkung der Abzug system.Ich vermuten, dass Deine Frage benötigen Ihre Verwendung.Jede aufzählbare unendliche Menge (disjunkt von der Konstanten und Klammer-Zeichen) dient als das alphabet der Variablen, ich bezeichne Sie hier mit unformatierten römischen Kleinbuchstaben x, y, z...

BEDINGUNGEN

Begriffe sind definiert induktiv:

• Jede Konstante ist ein term
• Jede variable ist ein term
• Wenn E ist ein Begriff, und F ist ein Begriff, zu, dann auch (E F) ist ein Begriff, der

Ich habe manchmal praktische Konventionen als syntaktischen Zucker, z.B.schreiben

E F G H

statt

(((E F) G) H).

Abzug

Konvertierung axiom-Schemata:

• ``K E F = E"ist ableitbar (K-axiom Schema)
• ``S F G H = F H (G H)" ist ableitbar (S-axiom Schema)
• ``Ich E = E"ist ableitbar (I-axiom Schema)

Ich habe den Dritten conversion-axiom (Ich Regel) nur weil Deine Frage setzt Voraus, dass wir haben nicht definiert der combinator Ich als alias/makro für S K K.

Gleichheit axiom-Schemata und Regeln der Inferenz

• ``E = E"ist ableitbar (Reflexivität axiom)
• Wenn "E = F"ist ableitbar, dann "F = E"ist auch ableitbar (Symmetrie rule of inference)
• Wenn "E = F"ist ableitbar, und "F = G"ist ableitbar zu, dann auch "E = G"reduzierbar (Transitivität Regel)
• Wenn "E = F"ist ableitbar, dann "E G = F G"ist auch ableitbar (Leibniz-Regel, die ich)
• Wenn "E = F"ist ableitbar, dann "G E = G F"ist auch ableitbar (Leibniz-Regel II)

Frage

Lassen Sie uns nun untersuchen, Ihre Frage.Ich vermuten, dass der Abzug-system definiert ist bisher nicht stark genug, um zu beweisen, Ihre Frage.

Ist proposition "Ich = S K K"ableitbar?

Das problem ist, dass wir die zum Nachweis der Gleichwertigkeit von Funktionen.Wir betrachten zwei Funktionen äquivalent, wenn Sie dieselbe Weise Verhalten.Funktionen handeln, so dass Sie angewendet werden, um die Argumente.Wir sollten beweisen, dass beide Funktionen die gleiche Weise handeln, wenn angewendet, um jeden möglichen Argumente.Wieder das problem mit der Unendlichkeit!Ich vermute, Axiomen-Schemata können nicht helfen Sie uns hier.So etwas wie

Wenn E F = G F ist ableitbar ist, dann ist auch E = G ist ableitbar

wäre nicht die Arbeit machen:wir können sehen, dass dies nicht das hervor, was wir wollen.Mit es, können wir beweisen, dass

``Ich E = S K K E"ist ableitbar

für jedes E Begriff Instanz, aber diese Ergebnisse sind nur getrennte Instanzen, und kann nicht verwendet werden als ganze für weitere Abzüge.Wir haben nur die konkreten Ergebnisse, die (unendlich vielen), die nicht in der Lage zusammenfassen:

• es gilt für E := K
• gilt für E := S
• es gilt für E := K K
• .
• .
• .

...

wir können nicht fassen, diese fragmentierten Ergebnis Instanzen in einer einzigen tollen Ergebnis, die besagt extensionality!Wir schütten können diese niedrigen-Wert-fragment in die Trichter in der Regel der Schlussfolgerung, dass würde Schmelze Sie zusammen in einen einzigen mehr wertvolles Ergebnis.

Wir müssen uns vermehren die Kraft unserer Abzug-system.Wir haben zu finden eine formelle tool, greift das problem.Ihre Fragen führt zu extensionality, und ich denke, das erklären extensionality Bedürfnisse, die wir darstellen können-Vorschläge, die halten Sie für *****beliebig***** Instanzen.Das ist, warum ich glaube, wir müssen zulassen, dass freie Variablen in unseren Objekt-Sprache.Ich Vermutung, dass der folgende, zusätzliche Regel von Inferenz wird die Arbeit machen:

• Wenn die variable x ist nicht Teil der Begriffe, die weder E noch F, und-Anweisung (E x) = (F x) ist ableitbar, dann E = F ist auch ableitbar (Extensionality rule of inference)

Das harte Ding in diesem axiom, leicht, die zu Verwirrung:x ist ein Objekt Variablen, voll emanzipiert und ANGESEHENE Teile unserer Objekt-Sprache, während der E und G sind metaVariablen, die nicht Teil der Objekt-Sprache, aber nur für eine präzise notation von axiom-Schemata.

(Bemerkung:Genauer gesagt, die extensionality rule of inference sollte formalisiert werden in vorsichtiger Weise, indem Sie eine metavariable x über alle möglichen Objekt Variablen x, y, z... und auch eine andere Art von metavariable E über alle möglichen Laufzeit Instanzen.Aber diese Unterscheidung zwischen den zwei Arten von metavariables plus der Objekt-Variablen ist es nicht so didaktischen hier, es nicht Einfluss auf Ihre Frage zu viel.)

Beweis

Lassen Sie uns beweisen nun die Aussage, dass `Ich = S K K''.

Schritte für die linke Seite:

• proposition `Ich x = x" ist eine Instanz von I-axiom Schema mit instatiation [E := x]

Schritte für die Rechte Seite:

• Proposition "S K K x = K x (K x)" ist eine Instanz von S-axiom Schema-Instanzen [E := K, F := K, G := x], so ist es ableitbar
• Proposition "K x (K x) = x" ist eine Instanz von K-axiom Schema-Instanzen [E := x, F := K x], so ist es ableitbar

Transitivität der Gleichheit:

• Datenschutzerklärung "S K K x = K x (K x)" entspricht der ersten Prämisse Transitivität rule of inference, und die Aussage "K x (K x) = x" entspricht der zweiten Prämisse, dass diese Regel von Inferenz.Die Instanzen sind [E := S K K x, F := K x (K x), G = x].So ist die Schlussfolgerung hält zu: E = G.Umschreiben, den Abschluss mit dem gleichen Instanzen, die wir get-Anweisung "S K K x = x", so ist dies ableitbar.

Symmetrie der Gleichheit:

• Mit "S K K x = x", können wir ableiten "x = S K K x"

Transitivität der Gleichheit:

• Mit "Ich x = x" und "x = S K K x", können wir daraus schließen "Ich x = S K K x"

Jetzt haben wir den Weg geebnet für den entscheidenden Punkt:

• Proposition "Ich x = S K K x" übereinstimmt mit der ersten Prämisse Erweiterung rule of inference:(E x) = (F x), mit Umschreibungen [E := Ich, F := S K K].Daher die Schlussfolgerung muss auch festhalten, dass ist, "E = F"mit dem gleichen Instanzen ([E := Ich, F := S K K]), woraus proposition "Ich = S K K", quod war demonstrandum.

---

Csörnyei, Zoltán (2007): Lambda-kalkulus.A funkcionális programozás alapjai. Budapest:Typotex.ISBN-978-963-9664-46-3.

Answer 2

Sie brauchen nicht mich als Axiom zu definieren. Beginnen Sie mit dem folgenden:

I.x = x
K.x y = x
S.x y z = x z (y z)

Da SKanything = anything, dann SKanything ist eine Identitätsfunktion, genau wie I.

So, I = SKK und I = SKS. Keine Notwendigkeit mich als Axiom definieren, können Sie es als Syntax Zucker, die SKK Aliase definieren können.

Die Definitionen von S und K sind Sie nur Axiome.

Answer 3

Die üblichen Axiome sind vollständig für Beta Gleichheit, aber nicht eta Gleichheit geben. Curry fand einen Satz von etwa dreißig Axiome zu den üblichen Vollständigkeit für Beta-eta Gleichheit zu erhalten. Sie sind aufgeführt in Hindley & Seldin der Einführung in die Kombinatoren und Lambda-Kalkül .

Roger Hindley, Currys Last Problem , listet einige zusätzliche Desiderate wir könnte zwischen dem Lambda-Kalkül und Notizen aus Zuordnungen mögen, dass wir Zuordnungen nicht haben, dass sie alle zufrieden stellen. Sie werden wahrscheinlich nicht kümmern viel über alle Kriterien.