Ich interessiere mich weniger für Sprachen, in denen Sie fast alles schreiben können, aber dann müssen Sie einen begleitenden Beweis dafür schreiben, dass das, was Sie geschrieben haben, endet.
Ich interessiere mich mehr für den Entwurfsraum von Sprachen, die von Natur aus konstruktionsbedingt auf bestimmte Komplexitätsklassen beschränkt sind.
Gibt es irgendeine Art von theoretischer Hierarchie für untergeordnete Sprachen?
programming-languages
termination
sfultong
quelle
quelle
Antworten:
Es gibt viele Klassen von Programmiersprachen, in denen alle Programme enden. Die häufigste Form der Durchsetzung der Kündigung sind Typen. Die am weitesten entwickelte Theorie von Typisierungssystemen zum Beenden der Berechnung könnte die des Lambda-Würfels von Barendregt sein, der die Typisierung in drei orthogonale Achsen zerlegt:
Ausgehend von einer abschließenden Sprache wie der einfach eingegebenenλ -calculus kann man eine beliebige Kombination dieser drei Achsen hinzufügen und die Terminierung beibehalten.
Dies hat enge Verbindungen zur Logik über die Curry-Howard-Korrespondenz .
Es gibt viele Erweiterungen und Verfeinerungen, einschließlich Typen, die Komplexitätsklassen erfassen.
quelle
Nach Bellantoni & Cooks grundlegender Arbeit in A New Recursion-Theoretic Characterization of Polytime Functions wurde viel an einfachen Charakterisierungen von Komplexitätsklassen mittels Gesamtsprachen mit starken Verbindungen zur linearen Logik gearbeitet, wie Martin Berger in den Kommentaren feststellt.
Aufbauend auf dieser Arbeit wurden andere Komplexitätsklassen charakterisiert: Leivant und Marion haben PSPACE und ELEM charakterisiert (die letzte ist besonders schön).
Es wurde auch an LOGSPACE gearbeitet , wieder mit Leivant und Ramyaa.
Es ist ein ziemlich aufregendes Feld mit einer jährlichen Konferenz !
quelle