Gibt es eine Programmiersprache, die nur die Macht eines deterministischen Push-Down-Automaten hat, und nicht mehr?

Einige Programmierprobleme erfordern nicht die volle Leistung einer Turing-Maschine. Sie können mit viel weniger Energie gelöst werden. Ich suche eine Programmiersprache mit geringerer Macht.Gibt es eine Programmiersprache, die nur die Macht eines deterministischen Push-Down-Automaten hat, und nicht mehr?

Gibt es eine High-Level-Programmiersprache existiert, die gerade diese Fähigkeiten zu unterstützen, beschränkt ist:

Ein Stapel mit Operationen Wert auf den Stack und Pop-Werte vom Stapel zu schieben.
Eine endliche Zustandsmaschine (FSM), um Eingangswerte, von Zustand zu Zustand bewegen, mit dem Stapel in Wechselwirkung treten, und Ausgabeergebnissen.

Ich weiß, dass ich Java oder C oder Python verwenden könnte (etc.) und beschränken Sie die Sprache durch ein Programm zu schreiben, die nur einen Stapel verwendet und einen FSM. Ich suche jedoch eine Programmiersprache, die nur diese Fähigkeiten hat und nicht mehr.

Mit anderen Worten, ich mag nicht, eine Turing-vollständige Programmiersprache verwenden, um Probleme zu lösen, die nur die Leistung eines deterministisch-Pushdown-Automaten erfordern. Ich möchte eine Programmiersprache verwenden, die nur die Macht eines deterministischen Push-Down-Automaten hat.

Quelle

2013-04-09 Roger Costello

Kurz gesagt, du wirst doch nicht um eine Hochsprache mit der kleinen Kraft zu finden. Dies ist nicht strikt per Definition, aber hohe Ebene impliziert eine gewisse Menge an Abstraktion, die der Komplexität entspricht.

Dies ist jedoch kein Problem: Sie müssen nicht über die Verwendung von zu viel Macht besorgt sein müssen. Maschinensprache, die kanonisch effiziente Sprache (minimaler Overhead!) Ist Turing vollständig, was darauf hinweist, dass Effizienz nicht eng an die theoretische Macht gebunden ist.

Quelle

2013-06-05 06:53:15 akroy

Vielleicht war der Fragesteller nicht für Effizienz suchen, sondern die schönen Eigenschaften, die mit weniger Energie als eine Turing-Maschine unter Verwendung eines Rechenmodells kommen? Vielleicht wollte er über Eigenschaften seines Programms nachdenken, die mit einer Turing-Maschine unentscheidbar wären, aber das ist für ein weniger leistungsfähiges Rechenmodell entscheidbar. – Guildenstern

Guter Punkt, danke! Ich denke, die Antwort kommt wahrscheinlich immer noch auf "Sie würden es wahrscheinlich keine Programmiersprache nennen, wenn es diese kleine Macht hätte." Ich vermute, dass Sie diese Art in "Leim" -Sprachen oder vielleicht in einfachen Skript-Engines finden, obwohl ich kein gutes Beispiel finden kann. Reguläre Ausdrücke (in ihrer einfachen Form) sind jedoch kanonisch die gleiche Potenz wie eine endliche Zustandsmaschine. Diese Frage http://stackoverflow.com/questions/315340/practical-non-turing-complete-languages hat einige interessante Antworten. – akroy

Ich bin nicht sicher, ob dies zählt, sondern die LR (1) Grammatiken genau die Leistung von deterministischen PDAs erfassen - wenn es eine LR (1) Grammatik für eine Sprache, da ist ein determinis PDA für sie und umgekehrt . Wenn Sie sich Tools wie yacc oder bison ansehen, sie auf LR (1) Grammatiken beschränken und semantische Aktionen mit beliebigem Code in ihnen verbieten, könnten Sie argumentieren, dass Ihnen eine Programmierumgebung mit genau der Macht übrig bleibt eines deterministischen PDA. Es ist zugegebenermaßen ein bisschen weit hergeholt. :-)

hoffe, das hilft!

Quelle

2014-12-17 01:58:50 templatetypedef

Gibt es eine Programmiersprache, die nur die Macht eines deterministischen Push-Down-Automaten hat, und nicht mehr?

Antwort

Verwandte Themen