Ich weiß, dass in imperativen Programmiersprachen eine while-do-Schleife als Kontrollflusskonstrukt ausreicht, um die Sprache Turing-complete zu machen (was den Kontrollfluss betrifft - natürlich brauchen wir auch unbegrenzten Speicher und bestimmte Operatoren ...) . Der Kern meiner Frage lautet: Hat eine do-while-Schleife die gleiche Rechenleistung wie eine while-do-Schleife? Mit anderen Worten, kann eine Sprache Turing-vollständig sein, wenn es unmöglich ist, Anweisungen vollständig zu überspringen?
Mir ist klar, dass einige der Semantiken hier etwas mehrdeutig sein können. Lassen Sie mich die eigentliche Frage mit einem bestimmten Beispiel formulieren:
Brainfuck (BF) ist ein Turing-Tarpit, bei dem der einzige Kontrollfluss eine while-do-Schleife ist [...]
(am Ende der Frage befindet sich eine vollständige Sprachspezifikation, falls Sie mit Brainfuck nicht vertraut sind). Definieren wir eine neue Sprache BF *, in der ,.+-<>
die gleiche Semantik wie in BF verwendet wird, stattdessen []
jedoch {}
eine do-while-Schleife. Das heißt, der einzige Unterschied zu BF besteht darin, dass jede Schleife mindestens einmal ausgeführt wird, bevor weitere Iterationen übersprungen werden können.
Ist BF * Turing-complete? Wenn ja, würde mich interessieren, wie ich BF in BF * übersetzen könnte. Wenn nicht, wie beweise ich das?
Einige meiner Beobachtungen:
- Nicht jedes BF-Programm kann in BF * übersetzt werden. Beispielsweise ist es unmöglich, ein Programm in BF * zu schreiben, das einen Wert lesen oder nicht lesen oder drucken kann. Wenn das Programm möglicherweise einen oder mehrere Werte druckt, wird immer mindestens einer ausgegeben. Möglicherweise gibt es jedoch eine Turing-vollständige Teilmenge von BF, die in BF * übersetzt werden kann.
- Wir können nicht einfach
[f]
(wof
ist irgendein beliebiges, nur aus Brainfuck bestehendes Programm+-[]<>
) in (in dem Versuch, den Effekt der ersten Iteration aufzuheben) übersetzen, weil a) nicht jede berechenbare Funktion eine berechenbare Inverse hat und b) selbst wenn dies der Fall ist, müßte nicht notwendigerweise weniger Schleifen als so rekursiv diesen Schritt der Anwendung gewährleistet ist nicht in erster Linie zu beenden.f-1{f}
f-1
f
Hier ist ein kurzer Überblick über die Brainfuck-Sprache. Brainfuck arbeitet auf einem unendlichen Band, wobei jede Zelle einen Bytewert enthält, der anfänglich Null ist. Überläufe werden umgangen, sodass eine Erhöhung um 255 0 ergibt und umgekehrt. Die Sprache besteht aus 8 Anweisungen:
+ Increment the current cell.
- Decrement the current cell.
> Move tape head to the right.
< Move tape head to the left.
, Input a character from STDIN into the current cell.
. Output the current cell as a character to STDOUT.
[ If the current cell is zero, jump past the matching ].
] If the current cell is non-zero, jump back to just behind the matching [.
[]
definiert in BF nicht genau eine "while do" -Schleife. Wie in Ihrer Tabelle wird in der linken und rechten Klammer die aktuelle Zellennull / Nichtnull ausgewertet. Wie lautet also die genaue Beschreibung der entsprechenden{}
Klammerbewertungslogik? Schlagen Sie einen weiteren Dialog / eine Diskussion im Computer Science Chat vor . auch deine "Beobachtungen" sind eher wie "Postulate" oder "Sätze" ohne Beweise.{}
zu machen wäre{
nichts und tun}
das gleiche wie]
. Ich werde in den nächsten Tagen nicht viel Zeit haben, aber ich werde mich mit Ihnen unterhalten, wenn ich etwas Zeit finde.{}
und zum Mitnehmen gegeben[]
. mit dem Verständnis, dass BF[]
ein Konstrukt ist, das nur einer while-do-Schleife in Turing- Gesamtsprachen ähnelt .Antworten:
Ich kenne Brainfuck nicht, also musst du ein paar Übersetzungen von meinem Pseudocode machen. Unter der Annahme, dass sich Brainfuck vernünftig verhält (ha!), Sollte jedoch alles untenstehende zutreffen.
do-while entspricht while-do.
do X while Y
ist äquivalent zuX; while Y do X
und, vorausgesetzt Sie haben Bedingungen,while Y do X
ist äquivalent zuif Y then (do X while Y)
.Das Leben ist ein bisschen schwieriger, wenn Sie keine Bedingungen haben. Wenn Sie Zeit haben, können Sie die Simulation folgendermaßen durchführen
if Y then X
:Aber was ist, wenn Sie nur Zeit haben? Ich behaupte, dass das Folgende simuliert
if Y then X
, vorausgesetzt, dass esX
mit dem aktuellen Wert der Variablen endet. (Dies kann nicht garantiert werden: Das Programm wirdif y=0 then loopforever
beendety != 0
, obwohlX
Schleifen für einen beliebigen Wert der Variablen ausgeführt werden.) Lassen SieV1
, ...,Vn
werden die modifizierten Variablen durchX
und lassen SieX'
werdenX
so modifiziert, dass es verwendetVi'
stattVi
für jede dieser Variablen.swap(A,B)
bezeichnet den offensichtlichen Code, der die VariablenA
und vertauschtB
.Die Idee ist die folgende. Angenommen, das
Y
ist falsch. Wir simulierenX
einmal und speichern die Ergebnisse inV1''
, ...,Vn''
;V1'
, ...,Vn'
behalten die ursprünglichen Werte vonV1
, ...,Vn
. Dann weisen wir zuV1 := V1'; ...; Vn := Vn'
, was nichts bewirkt. WennY
also falsch ist, haben wir nichts getan. Angenommen, dasY
ist wahr. Wir simulieren jetztX
zweimal und speichern die Ergebnisse in den Variablen "primed" und "double-primed". Jetzt haben die Zuweisungen am Ende der Schleife den Effekt,X
der einmal berechnet wurde. Beachten Sie, dass diesY
nur von den "nicht grundierten" Variablen abhängt, sodass der Wert nicht durch wiederholtes Ausführen der Schleife beeinflusst wird.OK, was ist, wenn
X
der aktuelle Wert der Variablen möglicherweise nicht beendet wird? (Vielen Dank an Martin Ender, der auf diese Möglichkeit hingewiesen hat.) In diesem Fall müssen wirX
Anweisungen für Anweisungen simulieren und dabei ähnliche Ideen wie oben verwenden. Jeder Befehl wird definitiv beendet, damit wir dieif
obige Simulation verwenden können, um die Befehlsdecodierung gemäß den Anweisungen von "Wenn der Opcode foo ist, tue dies; wenn es ein Balken ist, tue das; ..." durchzuführen. Nun verwenden wir eine Schleife, um die Anweisungen zu durchlaufenX
, indem wir einen Anweisungszeiger usw. verwenden, damit wir wissen, welche Anweisung als Nächstes auszuführen ist. Überprüfen Sie am Ende jeder Iteration der Schleife,Y
ob sieX
noch angehalten hat. Wenn diesY
falsch ist, können wir mit der Swap-Technik die Auswirkungen von rückgängig machenX
erste Anweisung.quelle
Y
falsch ist,X
aber nicht mit dem aktuellen Satz von Variablenwerten endet.if Y then X
wird beendet, Ihre Übersetzung jedoch nicht, da sie immerX'
mindestens einmal ausgeführt werden muss.X
Anweisung für Anweisung zu simulieren undY
nach jeder Anweisung zu überprüfen . Jeder Befehl wird garantiert beendet, damit alles funktioniert. Aber es ist ein Schmerz, es aufzuschreiben.X
, wenn es mit einer while-Schleife / Bedingung selbst beginnt. Ich muss noch etwas darüber nachdenken.X'
nicht linear ist. Würde es Ihnen etwas ausmachen, mehr Details für ein einfaches, aber nicht triviales Spielzeug anzugebenX
? ZBdo (while A do B) while C
? (Das Äußeredo while
kommt von dem Äußerenwhile do
, das wir gerade übersetzen)