Gibt es eine Programmiersprache, in der jeder String ein gültiges Programm ist?

10

Gibt es eine vollständige Turing-Programmiersprache, so dass für ein festes Alphabet (z. B. ASCII) jede mögliche Permutation dieser Zeichen ein semantisch gültiges Programm ist, das ausgeführt werden kann?

Wir betrachten Endlosschleifen auch als semantisch gültig.

Ich weiß, dass einige Datenformate wie Markdown eine universelle semantische Gültigkeit besitzen (jede Eingabe ist gültig), aber ich kann mir keine Programmiersprache mit dieser Eigenschaft vorstellen.

programming-languages syntax turing-completeness mp-
quelle
@PhilipKendall Das ist eine gültige (wenn auch entartete) Antwort. Natürlich werden fast alle Programme sofort JMP in unbekannten Raum und Absturz. Das heißt aber nicht, dass sie nicht aussagekräftig sind. Erinnert mich an Superoptimierung .
mp-
Angenommen, Sie haben eine triviale Sprache, wenn Sie einen Buchstaben ascii erhalten, der ihn druckt und zum nächsten Zeichen übergeht. Das entspricht technisch Ihrer Definition. Jede Eingabe ist gültig. Es wäre eine ziemlich dumme Sprache, da man damit nichts Produktives machen kann, aber wir sprechen natürlich nicht über Praktikabilität.
Neil
@Neil: das ist keine Turing-vollständige Sprache.
Doc Brown

Antworten:

10

Jede Oktettsequenz kann als gültiger Z80-Code interpretiert werden, da keine ungültigen Opcodes oder Argumente vorhanden sind. Ich kann mir vorstellen, dass dies auch für verschiedene andere Prozessoren gilt. Ich persönlich kenne Z80 nur.

Bei solchen Dingen auf niedriger Ebene stoßen Sie möglicherweise auf Fragen, was es bedeutet, "ein Programm auszuführen":

  • Was passiert, wenn es außerhalb des initialisierten Bereichs springt?
  • Wie endet das "Programm" überhaupt?
Philip Kendall
quelle
1
"Was passiert, wenn es außerhalb des initialisierten Bereichs springt? " - Durch einfaches Hinzufügen einer Regel "Springt in diesem Fall zur Adresse 0" sollte die Handhabung recht einfach sein. Es sollte nicht zu schwierig sein, eine zusätzliche Semantik für das Deaktivieren mit diesen Randfällen zu definieren.
Doc Brown
1
Sprünge außerhalb des initialisierten Raums sind syntaktisch gültig und möglicherweise sogar semantisch gültig (z. B. besteht seine genau definierte Semantik darin, einen Segfault zu erzeugen).
Lie Ryan
9

Solche Fragen zu Programmiersprachen werden fast überall mit Ja beantwortet. Wenn es derzeit keine Sprache gibt, die die angeforderte Eigenschaft hat, können Sie darauf wetten, dass jemand es als Herausforderung ansieht, eine (Spielzeug-) Sprache zu erstellen, die die Eigenschaft hat.

Als Beispiel für eine Sprache, in der jede Permutation der Zeichen des Alphabets syntaktisch gültig ist, ist die Leerzeichen-Sprache , in der das Alphabet der Sprache selbst aus Leerzeichen, Tabulatoren und Zeilenvorschub besteht.

Bart van Ingen Schenau
quelle
4
Da jedes Nicht-Leerzeichen als Kommentar ignoriert wird, ist nicht nur jede Permutation von Leerzeichen, sondern tatsächlich jede Permutation von ASCII-Zeichen auch syntaktisch gültig.
Jörg W Mittag
1
Um es kurz zu machen: Wenn Sie einen kurzen Blick in das Whitespace-Tutorial werfen , scheint es, dass auf eine Stapelmanipulation [Space] kein [Tab] -Zeichen folgen darf. Aber ich denke, es wird einfach sein, die Sprache für diese Sonderfälle zu erweitern (zum Beispiel indem man ihnen No-Op-Semantik gibt).
Doc Brown
@docbrown, in den Beispielen sehe ich Sequenzen von [Space] [Tab], daher bin ich mir nicht sicher, woher Sie Ihre Schlussfolgerung haben.
Bart van Ingen Schenau
@BartvanIngenSchenau: Schauen Sie sich das Tutorial an: Eine Stapelmanipulation wird durch ein [Leerzeichen] gefolgt von einem von vier möglichen Befehlen eingeleitet, die entweder mit einem anderen [Leerzeichen] oder [LF] beginnen. Die Sequenz [Leertaste] [Tab] kann natürlich als Teil einer Zahl oder als Teil eines anderen Befehls auftreten, aber ein [Tab] ist nach einem durch [Leertaste] eingeführten Stapelbefehl kein gültiges Zeichen.
Doc Brown
0

Warum sich mit Zeichenfolgen (von Zeichen) zufrieden geben? Sie sollten diese Frage in "eine beliebige Reihe von Token" umformulieren. Nicht Bits, Bits sind so computerisch des 20. Jahrhunderts.

Endlosschleifen sind also in Ordnung, sagen Sie. Was ist mit der Division durch Null? Wenn Sie mit Ihrer Definition von gültig nachsichtig genug sind, erhalten Sie möglicherweise ein Ja, aber die meisten Kombinationen wären immer noch bedeutungslos. Ich würde also sagen, dass Sie möglicherweise immer ein technisch gültiges Programm erhalten, aber kaum ein semantisch gültiges Programm.

Martin Maat
quelle
"Bits sind so computerisch des 20. Jahrhunderts": Was meinst du damit?
Giorgio
Ich meine, Strings, Zeichen und Bits sind ein technisches Detail, im Wesentlichen sprechen Sie über Anweisungen und Operanten. Wie diese umgesetzt werden, ist für die Frage unerheblich.
Martin Maat
Ja, aber diese Beobachtung war noch vor 50 Jahren wahr (formale Sprachen sind noch älter), daher bin ich mir immer noch nicht sicher, ob ich verstehe, was Sie meinen.
Giorgio
Ich wollte die Frage nur auf das logische Wesentliche bringen. Es geht nicht um Zeichenfolgen oder Bytes, es geht um Anweisungen und Argumente. Können Sie diese auf beliebige Weise verwechseln und sicher sein, ein gültiges Programm zu erhalten?
Martin Maat