Algorithmus zur Bestimmung der Funktionsgleichheit auf der einfach getippten Lambda-Rechnung?

10

Wir wissen, dass die Beta-Gleichheit von einfach getippten Lambda-Begriffen entscheidend ist. gegebenem M, N: σ → τ entscheidbar, ob für alle X: σ MX NX?β

MaiaVictor
quelle
Einfach eingegeben Lambda Calculus / STLC Wikipedia. Gibt es ein anderes grundlegendes Berechnungsmodell, dem es entspricht, da es nicht vollständig ist? Es könnte auch nützlich sein, den Stopperkennungsalgorithmus zu studieren, der laut Wikipedia für STLC ...
vzn
3
@Marzio: Eigentlich denke ich, dass das Problem hier in der Art und Weise liegt, wie die Frage formuliert ist, was ziemlich ungenau ist. Einmal richtig formuliert, ist dies eine Frage auf Forschungsebene. Eine bessere Formulierung wäre: Wir wissen, dass die Beta-Gleichheit von einfach getippten Lambda-Begriffen entscheidbar ist. In Anbetracht M,N:στ wird entscheidbar , ob für alle X:σ , MXβNX ? Die Antwort ist im Allgemeinen negativ (daher gibt es keinen Algorithmus wie den von Viclib gesuchten). Obwohl dies vielleicht erwartet wird, ist dies a priori nicht offensichtlich und eine Folge einiger Veröffentlichungen aus den 90er Jahren.
Damiano Mazza
@DamianoMazza: ok, in der Tat habe ich nicht dafür gestimmt, es zu schließen ... Ich werde meinen Kommentar löschen, deinen hinterlassen und auf den Kommentar / die Bearbeitung von OP warten.
Marzio De Biasi
@DamianoMazza und Marzio, ich weiß nicht genug, um eine so formelle Frage zu stellen. Ich wünschte, ich hätte es getan, aber das lerne ich nicht an meiner Schule. Selbst wenn ich nach "Beta-Gleichheit" google, was ich tatsächlich versucht habe, bevor ich die Frage gestellt habe, habe ich so wenige Ergebnisse erzielt, dass es fast so ist, als ob dieser Begriff gar nicht existiert hätte. Ich habe also nicht einmal eine Idee, wo Sie darüber lernen und lesen. Würdet ihr mich bitte auf den richtigen Ort hinweisen, um das Thema selbst zu studieren? Frage aktualisiert.
MaiaVictor
1
@Viclib: Beta-Äquivalenz ist ein technischer Begriff, den ich in meiner Antwort nicht erwähnt habe. Ungefähr zwei Begriffe sind Beta-äquivalent, wenn sie das gleiche Ergebnis liefern. So sagen für alle bedeutet , dass und die gleiche Funktion berechnen. In Bezug auf Hinweise zum Erlernen des (typisierten oder untypisierten) Lambda-Kalküls sind die Notizen von Peter Selinger sowie die Vorlesungsnotizen von Sørensen und Urzyczyn zu Curry-Howard ausgezeichnete Ausgangspunkte. MXβNXXMN
Damiano Mazza

Antworten:

13

Wie ich in meinem Kommentar sagte, lautet die Antwort im Allgemeinen nein.

Der wichtige Punkt, den man verstehen muss (ich sage dies für Viclib, der scheinbar etwas über diese Dinge lernt), ist, dass eine Programmiersprache / ein Satz von Maschinen, in denen alle Programme / Berechnungen enden, keineswegs die Funktionsgleichheit impliziert (dh ob zwei Programme / Maschinen berechnen die gleiche Funktion) ist entscheidbar. Ein einfaches Beispiel: Nehmen Sie den Satz polynomisch getakteter Turing-Maschinen. Per Definition enden alle diese Maschinen an allen Eingängen. Nun gibt es für jede Turing-Maschine eine Turing-Maschine , die bei Eingabe der Zeichenfolge simuliert Schritte der Berechnung von an einer festen Eingabe (z. B. der leeren Zeichenfolge) und akzeptiert, wenn höchstens endetMM0x|x|MM|x|Schritte oder lehnt anders ab. Wenn eine Turing-Maschine ist, die immer sofort ablehnt, sind und beide (offensichtlich) polynomisch getaktet, und wenn wir dennoch entscheiden könnten, ob und dieselbe Funktion berechnen (oder in diesem Fall dieselbe Sprache entscheiden), Wir könnten entscheiden, ob (das, wie Sie sich erinnern, eine beliebige Turing-Maschine ist) auf der leeren Zeichenfolge endet.NM0NM0NM

Im Fall des einfach typisierten Kalküls (STLC) funktioniert ein ähnliches Argument, außer dass die Messung der Ausdruckskraft des STLC nicht so trivial ist wie im obigen Fall. Als ich meinen Kommentar schrieb, dachte ich an einige Artikel von Hillebrand, Kanellakis und Mairson aus den frühen 90er Jahren, die zeigen, dass man durch die Verwendung komplexerer Typen als der üblichen Art von Church-Ganzzahlen im STLC ausreichend komplex codieren kann Berechnungen für das obige Argument funktionieren. Eigentlich sehe ich jetzt, dass das benötigte Material bereits in Mairsons vereinfachtem Beweis von Statmans Theorem enthalten ist:λ

Harry G. Mairson, Ein einfacher Beweis für einen Satz von Statman. Theoretical Computer Science, 103 (2): 387-394, 1992. ( hier online verfügbar ).

In diesem Artikel zeigt Mairson, dass es bei jeder Turing-Maschine einen einfachen Typ und einen -term , der die Übergangsfunktion von codiert . (Dies ist a priori nicht offensichtlich, wenn man die äußerst schlechte Ausdruckskraft des STLC für kirchliche Ganzzahlen im Auge hat. In der Tat ist Mairsons Kodierung nicht unmittelbar). Daraus ist es nicht schwer, einen Begriff zu konstruierenMσλδM:σσM

tM:nat[σ]bool

(wobei die Instanziierung der Art von Ganzzahlen der Kirche auf ), so dass auf reduziert wird, wenn in höchstens Schritten endet, wenn fütterte die leere Zeichenfolge oder reduzierte sich ansonsten auf . Wenn wir wie oben entscheiden könnten, dass die durch Funktion die konstante -Funktion ist, hätten wir die Beendigung von für die leere Zeichenfolge entschieden.nat[σ]σtMn_1_Mn0_tM0_M

Damiano Mazza
quelle
Es ist wahrscheinlich auch möglich, die Codierung von Multi-Variate-Polynomfunktionen in STLC zu verwenden und dann den Satz von Matiyasevich anzusprechen .
Cody
Der STLC ist also nicht vollständig, aber leistungsstark genug, um die Übergangsfunktion einer Turing-Maschine zu codieren!? Eine Turing-Maschine könnte also als Band plus ein darauf arbeitendes STLC-Programm definiert werden?
MaiaVictor
2
@Viclib: Denken Sie darüber nach: Die Simulation eines Schritts einer beliebigen Turing-Maschine erfordert nicht viel Rechenleistung. Grundsätzlich benötigen Sie nur endliche Datentypen (mit Wenn-Dann-Sonst), Listen (mit den Grundoperationen: Nachteile, Schwanz usw.) und geordnete Paare. (Tatsächlich behauptet die Extended Church-Turing Thesis, dass solch eine geringe Komplexität jedem vernünftigen Maschinenmodell gemeinsam ist). Was der STLC fehlt, ist die Fähigkeit, TM-Übergänge "ad libitum" unabhängig von der Eingabe auszuführen: Sie können sie nur einige Male wiederholen, was einem Turm von Exponentialen in der Eingabegröße entspricht (siehe Mairsons Artikel).
Damiano Mazza
1
@Cody: Danke, ich kannte das Papier nicht. Ich schätze du hast Recht.
Damiano Mazza