Können typisierte Lambda-Kalküle * alle * Algorithmen unterhalb einer bestimmten Komplexität ausdrücken?

21

Ich weiß, dass die Komplexität der meisten Varietäten von typisierten Lambda-Kalkülen ohne das Y-Kombinator-Primitiv begrenzt ist, dh es können nur Funktionen mit begrenzter Komplexität ausgedrückt werden, wobei die Grenze größer wird, wenn die Ausdruckskraft des Typensystems zunimmt. Ich erinnere mich, dass zB die Konstruktionsrechnung höchstens doppelt exponentielle Komplexität ausdrücken kann.

Meine Frage ist, ob die typisierten Lambda-Kalküle alle Algorithmen unterhalb einer bestimmten Komplexitätsgrenze ausdrücken können oder nur einige? Gibt es beispielsweise Exponentialzeit-Algorithmen, die durch keinen Formalismus im Lambda-Würfel ausgedrückt werden können? Was ist die "Form" des Komplexitätsraums, der vollständig von verschiedenen Ecken des Würfels bedeckt ist?

jkff
quelle
Ich denke, die Antwort lautet ja: Wir können die zeitlich begrenzte universelle Turing-Maschine ausdrücken.
Kaveh
3
Sind Sie sich über die doppelt exponentielle Obergrenze sicher? Wenn ich mich recht erinnere, ist der CoC die ausdrucksstärkste "Ecke" des Lambda-Würfels, was bedeutet, dass er das System F (dh den polymorphen λ Kalkulus) enthält, der weit über das zweifach Exponentielle hinausgeht ... Auf jeden Fall lautet die Antwort "Ja" Siehe zum Beispiel meine Antwort hier . Ich kann eine ausführlichere Antwort posten, wenn Sie möchten.
Damiano Mazza
1
Sorry, ich falsch verstehe Ihre Frage, Sie fragen nicht über einig getippt λ -calculi aber speziell über die typisierten λ -calculi der Lambda - Cube. Ich befürchte, dass es dort keine interessante Komplexität gibt, sie sind alle viel zu ausdrucksstark, obwohl ich die genaue Antwort nur für System F und System F ω kenne . ω
Damiano Mazza
4
Die Ackermann-Funktion kann in der Konstruktionsrechnung ausgedrückt werden, so dass es nicht richtig sein kann, dass diese einfach doppelt exponentiell ist.
Andrej Bauer
Ich glaube, ich habe darüber im Coq'Art-Buch gelesen, aber ich irre mich sehr wahrscheinlich. Vielen Dank!
JKFF

Antworten:

19

Ich werde eine teilweise Antwort geben, ich hoffe, andere werden die Lücken füllen.

In typisierten lgr; -Kalkülen kann man gewöhnlichen Darstellungen von Daten ( N a t für kirchliche (unäre) Ganzzahlen, S t r für binäre Zeichenfolgen, B o o l für Boolesche) einen Typ geben und sich fragen, wie komplex die Funktionen sind / Probleme darstellbar / entscheidbar durch eingegebene Begriffe. Ich kenne eine genaue Antwort nur in einigen Fällen, und in dem einfach getippten Fall hängt sie von der Konvention ab, die bei der Definition von "darstellbar / entscheidbar" verwendet wird. Jedenfalls kenne ich keinen Fall, in dem es eine doppelt exponentielle Obergrenze gibt.λNatStrBOOl

Zunächst ein kurzer Rückblick auf den Lambda Cube. Die 8 Kalküle werden erhalten, indem die folgenden 3 Arten von Abhängigkeiten über den einfach eingegebenen Kalkül (STLC) aktiviert oder deaktiviert werden :λ

  • Polymorphismus : Begriffe können typabhängig sein;
  • abhängige Typen : Typen können von Begriffen abhängen;
  • höhere Ordnung : Typen können von Typen abhängen.

(Die Abhängigkeit von Begriffen von Begriffen ist immer da).

Das Addieren von Polymorphismus ergibt System F. Hier können Sie die Church-Ganzzahlen mit und in ähnlicher Weise für binäre Zeichenfolgen und Boolesche Werte. Girard hat bewiesen, dass System-F-Terme vom Typ N a tN a t genau die numerischen Funktionen darstellen, deren Gesamtheit in der Peano-Arithmetik zweiter Ordnung nachweisbar ist. Das ist so ziemlich alltägliche Mathematik (wenn auch ohne jegliche Wahlmöglichkeit), die Klasse ist also riesig, die Ackermann-Funktion ist eine Art winziger Mikrobe, geschweige denn die Funktion 2 2Neint: =X.(XX)XXNatNat . Ich kenne keine "natürliche" numerische Funktion, die in System F nicht dargestellt werden kann. Beispiele werden normalerweise durch Diagonalisierung oder Codierung der Konsistenz von PA zweiter Ordnung oder anderer selbstreferenzieller Tricks (wie die Entscheidung fürβ) erstellt22nβ Gleichheit in System) erstellt F selbst). Natürlich können Sie in System F zwischen unären ganzen Zahlen und ihrer binären Darstellung S t r konvertieren und dann beispielsweise testen, ob das erste Bit 1 ist, also die Klasse der entscheidbaren Probleme (nach Typ S t rB) o o l ) ist genauso groß.NatStrStrBOOl

Die anderen 3 Kalküle des Lambda-Würfels, die den Polymorphismus enthalten, sind daher mindestens so aussagekräftig wie das System F. Dazu gehört das System F (Polymorphismus + höhere Ordnung), das genau die nachweislich Gesamtfunktionen in PA höherer Ordnung ausdrücken kann, und der Kalkül von Konstruktionen (CoC), die aussagekräftigste Berechnung des Cubes (alle Abhängigkeiten sind aktiviert). Ich kenne keine Charakterisierung der Ausdruckskraft des CoC in Bezug auf arithmetische Theorien oder Mengen-Theorien, aber es muss ziemlich beängstigend sein :-)ω

Ich bin viel unwissender in Bezug auf die Kalküle, die man erhält, wenn man nur abhängige Typen (im Wesentlichen Martin-Löf-Typentheorie ohne Gleichheit und natürliche Zahlen), Typen höherer Ordnung oder beides aktiviert. In diesen Kalkülen sind Typen mächtig, aber Ausdrücke können nicht auf diese Kraft zugreifen, sodass ich nicht weiß, was Sie bekommen. Ich denke, dass Sie rechnerisch nicht viel ausdrucksvoller sind als mit einfachen Typen, aber ich kann mich irren.

Also bleiben wir beim STLC. Soweit ich weiß, ist dies der einzige Kalkül des Würfels mit interessanten (dh nicht ungeheuer großen) Komplexitätsobergrenzen. Es gibt eine unbeantwortete Frage zu TCS.SE, und tatsächlich ist die Situation etwas subtil.

Erstens, wenn Sie ein Atom fixieren und N a t : = ( X X ) X X definieren , gibt es Schwichtenbergs Ergebnis (ich weiß, dass es eine englische Übersetzung dieses Papiers irgendwo im Web gibt, aber ich kann es nicht finden now), was besagt, dass die Funktionen vom Typ N a tN a t genau die erweiterten Polynome sind (mit if-then-else). Wenn Sie einen gewissen "Durchhang" zulassen, dh wenn Sie zulassen, dass der Parameter X nach Belieben instanziiert wird, und Terme vom Typ N a A berücksichtigen ]XNeint: =(XX)XXNatNatX mit A willkürlich kann viel mehr dargestellt werden. Zum Beispiel ein beliebiger Turm von Exponentialen (so dass Sie weit über das zweifache Exponential hinausgehen können) sowie die Vorgängerfunktion, aber immer noch keine Subtraktion (wenn Sie Binärfunktionen berücksichtigen und versuchen, sie mit N a t [ A ] N a t einzugeben [ A ] N a tNat[A]NatANat[A]Nat[A]Nat ). Die in der STLC darstellbare Klasse numerischer Funktionen ist also etwas seltsam, sie ist eine strenge Teilmenge der Elementarfunktionen, entspricht jedoch keiner bekannten.

Im offensichtlichen Widerspruch zu dem oben Gesagten gibt es diesen Aufsatz von Mairson, der zeigt, wie die Übergangsfunktion einer beliebigen Turing-Maschine codiert wird , von der Sie einen Term vom Typ N a t [ A ] B o o l (für einen Typ) erhalten A in Abhängigkeit von M ), der bei einer eingegebenen Church-Ganzzahl n die Ausführung von M ausgehend von einer festen Ausgangskonfiguration für eine Anzahl von Schritten der Form 2 2 n 2 n simuliertMNat[A]BoolAMnM

222n,
mit der Höhe des Turms fest. Dies zeigt nicht , dass jedes Elementarproblem von der STLC entschieden werden kann, da es in der STLC keine Möglichkeit gibt, eine Binärzeichenfolge (vom Typ ), die die Eingabe von M darstellt, in den Typ umzuwandeln , der zur Darstellung der Konfigurationen von M verwendet wirdStrMM in verwendet wird Mairsons Kodierung. Die Codierung ist also irgendwie "ungleichmäßig": Sie können elementar lange Ausführungen von einer festen Eingabe simulieren, indem Sie für jede Eingabe einen eigenen Begriff verwenden, aber es gibt keinen Begriff, der beliebige Eingaben verarbeitet.

Tatsächlich ist der STLC extrem schwach in dem, was er "einheitlich" entscheiden kann. Nennen wir die Klasse von Sprachen, die durch einfache Eingabe von Begriffen vom Typ S t r [ A ] B o o l für einige A (wie oben, Sie erlauben ein beliebiges "Durchhängen" bei der Eingabe) entscheidbar ist. Soweit mir bekannt ist, fehlt eine genaue Charakterisierung von C S T. Wir wissen jedoch, dass C S TL I N T I MCSTStr[A]BoolACSTCSTLINTIME(deterministische lineare Zeit). Sowohl die Eindämmung als auch die Tatsache, dass es streng ist, können durch sehr einfache semantische Argumente gezeigt werden (unter Verwendung der Standard-Denotationssemantik der STLC in der Kategorie der endlichen Mengen). Ersteres wurde kürzlich von Terui gezeigt . Letzteres ist im Wesentlichen eine Neuformulierung alter Ergebnisse von Statman. Ein Beispiel für ein Problem in ist MAJORITY (wenn Sie eine Binärzeichenfolge angeben, geben Sie an, ob sie streng mehr 1s als 0s enthält).LINTIMECST


(Much) Später Add-on: Ich habe gerade herausgefunden , dass die Klasse Ich nenne oben eigentlich nicht eine genaue Charakterisierung hat, die zudem extrem einfach ist. ImCSTHillebrand und Kanellakis beweisen dieser schönen Arbeit von 1996 unter anderem, dass

Satz. (die regulären Sprachen in { 0 , 1 }CST=REG{0,1} ).

(Dies ist Satz 3.4 in ihrer Arbeit).

Ich finde das doppelt überraschend: Ich bin überrascht über das Ergebnis selbst (es ist mir nie in den Sinn gekommen, dass etwas "Ordentliches" entsprechen könnte) und darüber, wie wenig es bekannt ist. Es ist auch amüsant, dass Teruis Beweis der Obergrenze von L I N T I M E die gleichen Methoden anwendet, die von Hillebrand und Kanellakis angewendet werden (Interpretation des einfach typisierten λ- Kalküls in der Kategorie der endlichen Mengen). Mit anderen Worten, Terui (und ich) könnte leicht dieses Ergebnis wieder entdeckt , wären da nicht die Tatsache , dass wir irgendwie glücklich mit waren C S TCSTLINTIMEλCST eine "seltsame" Klasse war :-)

(Meine Überraschung teilte ich übrigens mit dieser Antwort auf eine MO-Frage zu "unbekannten Theoremen").

Damiano Mazza
quelle
3
Ich habe die Antwort gelesen, nur um diesen Namen noch einmal zu sehen. Ich glaube, Sie haben mir schon mehr beigebracht als meine eigenen Professoren. Internet ist eine schöne Sache. Vielen Dank.
MaiaVictor
@ Damiano Mazza. Hat deine Antwort gefallen, aber der Begriff "Uniformität" ist nicht so trivial, oder?
Andrea Asperti
Hi @Andrea, danke. "Einheitlichkeit" ist hier nur die Tatsache, dass Sie eine Sprache mit einem einzigen Programm festlegen, das für alle möglichen Eingaben arbeitet, und nicht mit einer unendlichen Familie von Programmen, die jeweils nur für Eingaben mit fester Länge arbeiten (oder Schlimmer noch, ein Programm für jede Eingabe, wie in Mairsons Artikel). Homogenität ist die Norm im Kalkül ( λ- Terme sind viel zu mächtig, um für uneinheitliche Ansätze verwendet zu werden, es sei denn, man betrachtet Einschränkungen wie Linearität / Affinität) und ist in gewissem Sinne "trivial". Aber vielleicht verstehe ich Ihren Kommentar nicht ...λλ
Damiano Mazza
12

Eine Antwort auf eine Frage, die Damiano in seiner ausgezeichneten Antwort aufgeworfen hat:

Ich bin viel unwissender in Bezug auf die Kalküle, die man erhält, wenn man nur abhängige Typen (im Wesentlichen Martin-Löf-Typentheorie ohne Gleichheit und natürliche Zahlen), Typen höherer Ordnung oder beides aktiviert. In diesen Kalkülen sind Typen mächtig, aber Ausdrücke können nicht auf diese Kraft zugreifen, sodass ich nicht weiß, was Sie bekommen.

Das Hinzufügen abhängiger Typen ändert nichts an der Konsistenzstärke der Theorie. Einfache abhängige Typen haben die gleiche Konsistenzstärke wie das einfach typisierte Lambda, und die Konstruktionsrechnung hat die gleiche Konsistenzstärke wie das System F ω .ω

Tatsächlich kann eine reine Martin-Löf-Typ-Theorie ( im Lambda-Würfel) nicht beweisen, dass 0 = 1 falsch impliziert. Um dies zu tun, müssen Sie mindestens ein Universum - und Universen gigantisch erhöhen die Festigkeit der Theorie. Die Berechnung induktiver Konstruktionen (ungefähr λ P ω plus induktive Typen plus zählbar viele Universen) ist hinsichtlich der Konsistenzstärke mit ZFC mit zählbar vielen unzugänglichen Kardinälen identisch.λPλPω

Ich weiß nicht, wie stark die Berechnung von Konstruktionen ist, wenn man induktive Typen und große Eliminierungen hinzufügt.

Neel Krishnaswami
quelle
Vielen Dank @Neel! Ich denke, jetzt haben wir das ganze Bild.
Damiano Mazza
7

Ich werde versuchen, Damianos ausgezeichnete Antwort zu ergänzen.

Im Allgemeinen kann ein typisierter Kalkül als Sprache von Realisierern für eine bestimmte Logik verwendet werden. Insbesondere ist System F eine Sprache von Realisierern für die Heyting-Arithmetik H A 2 2. Ordnung . Der informelle Satz kann wie folgt angegeben werdenλF HA2

Wenn die Bedingungen für eine typisierte Kalkül die Regisseure für eine Logik L , dann wird die definierbaren Funktionen in T repräsentieren genau die beweisbar Gesamt funktionalen Beziehungen in L .TLTL

Die Details sind natürlich trüber, und muss mindestens Arithmetik enthalten, aber die Anwendung dieser Idee gibtL

  • Die definierbaren Funktionen in System sind die nachweislich Gesamtfunktionen in H A 2 (dies schließt die Ackermann-Funktion und viel, viel schneller wachsende Funktionen ein).FHA2

  • Die definierbaren Funktionen im System TPAF

Es gibt einige typisierte Calculi, die genau erfassenλPTIME

Im Allgemeinen ist dies ein großer Forschungszweig, daher verweise ich nur auf eine meiner vorherigen Antworten .

Cody
quelle
3
Vgl. Stephen Cook und Alasdair Urquharts " Funktionale Interpretationen von durchführbar konstruktiver Arithmetik ", 1993, für eine komplexitätstheoretische Variante.
Kaveh