Es ist unmöglich, eine Programmiersprache zu schreiben, die alle Maschinen zulässt, die an allen Eingaben anhalten, und keine anderen. Es scheint jedoch einfach zu sein, eine solche Programmiersprache für jede Standardkomplexitätsklasse zu definieren. Insbesondere können wir eine Sprache definieren, in der wir alle effizienten Berechnungen und nur effiziente Berechnungen ausdrücken können.
Zum Beispiel für etwas wie : Nehmen Sie Ihre bevorzugte Programmiersprache und fügen Sie nach dem Schreiben Ihres Programms (entsprechend Turing Machine ) dem Header drei Werte hinzu: eine Ganzzahl und eine Ganzzahl sowie eine Standardausgabe . Wenn das Programm kompiliert wird, ein Ausgang Turing Maschine , dass die Eingabe gegeben der Größe läuft auf für cn ^ k Schritten. Wenn M ' nicht anhält, bevor die cn ^ k- Schritte abgelaufen sind, geben Sie den Standardausgang d ausM ' c k d M x n M '. Wenn ich mich nicht irre, können wir mit diesen Programmiersprachen alle Berechnungen in und nicht mehr ausdrücken . Diese vorgeschlagene Sprache ist jedoch von Natur aus nicht interessant.
Meine Frage: Gibt es Programmiersprachen, die Teilmengen von berechenbaren Funktionen (z. B. alle effizient berechenbaren Funktionen) auf nicht triviale Weise erfassen? Wenn nicht, gibt es einen Grund dafür?
quelle
Antworten:
Eine Sprache, die versucht, nur polynomielle Zeitberechnungen auszudrücken, ist der weiche Lambda-Kalkül . Das Typensystem basiert auf linearer Logik. Eine aktuelle Arbeit befasst sich mit Polynomzeitkalkülen und bietet eine gute Zusammenfassung der jüngsten Entwicklungen, die auf diesem Ansatz basieren. Martin Hofmann beschäftigt sich schon länger mit dem Thema. Eine ältere Liste relevanter Artikel finden Sie hier ; Viele seiner Arbeiten gehen in diese Richtung.
Bei anderen Arbeiten wird mithilfe abhängiger Typen oder typisierter Assemblersprachen überprüft, ob das Programm eine bestimmte Menge an Ressourcen verwendet .
Noch andere Ansätze basieren auf ressourcengebundenen formalen Kalkülen , wie z. B. Varianten der Umgebungskalkulation.
Diese Ansätze haben die Eigenschaft, dass gut typisierte Programme einige vordefinierte Ressourcengrenzen erfüllen. Die gebundene Ressource kann zeitlich oder räumlich sein und im Allgemeinen von der Größe der Eingaben abhängen.
Frühe Arbeiten in diesem Bereich befassen sich mit stark normalisierenden Kalkülen, was bedeutet, dass alle gut typisierten Programme anhalten. System F , auch bekannt als polymorpher Lambda-Kalkül, normalisiert sich stark. Es gibt keinen Festkommaoperator, aber es ist trotzdem sehr aussagekräftig, obwohl ich nicht glaube, dass es bekannt ist, welcher Komplexitätsklasse es entspricht. Definitionsgemäß drückt jeder stark normalisierende Kalkül eine Klasse von Abschlussberechnungen aus.
Die Programmiersprache Charity ist eine recht ausdrucksstarke Funktionssprache, die bei allen Eingaben anhält. Ich weiß nicht, welche Komplexitätsklasse es ausdrücken kann, aber die Ackermann-Funktion kann in Charity geschrieben werden.
quelle
Werfen Sie einen Blick auf Guillaume Bonfante, der zwei Charakterisierungen für Logspace und Polynomial Time mit Programmiersprachen vorschlug.
Guillaume Bonfante, Einige Programmiersprachen für Logspace und Ptime, AMAST 2006, LNCS 4019, S. 66-80, 2006
quelle
Als Ansatz möchte ich auch die implizite Komplexitätstheorie erwähnen, da ich sie in einigen Fragen gesehen habe, die etwas miteinander zu tun haben. Um diese Antwort von Neel Krishnaswami zu zitieren :
quelle
Ich bin überrascht, dass niemand die primitive Rekursion erwähnt hat. Durch Beschränkung auf begrenzte Schleifen (dh die Anzahl der Iterationen für jede Schleife muss berechnet werden, bevor die Schleife beginnt) ist das resultierende Programm primitiv rekursiv und daher total. Douglas Hofstadter schlug eine Programmiersprache vor, BLOOP, die alle und nur primitive rekursive Funktionen zuließ.
quelle
Siehe auch Pola, eine Sprache für die PTIME-Programmierung und Werke von Japaridze zur PTIME-Arithmetik, zB http://arxiv.org/abs/0902.2969
quelle