Reicht eine Do-While-Schleife für die Turing-Vollständigkeit aus?

22

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](wo fist 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-1f

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 [.
Martin Ender
quelle
2
Sehr ähnliche Frage .
Raphael
interessant, aber denke, es ist nicht vollständig sorgfältig konstruiert. []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.
VZN
@vzn Das sind gute Punkte. Ich stellte dar , dass die offensichtliche Definition {}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.
Martin Ender
Leider ist dies anscheinend etwas subtil zu stellen und es scheinen hier zwei völlig unterschiedliche Fragen zu sein. (1) Wenn eine Turing-vollständige Sprache mit einer while-do-Schleife (und "anderem Zeug") angegeben wird, kann sie stattdessen mit nur einer do-while-Schleife in eine Turing-vollständige Sprache konvertiert werden. aber dann muss man mehr über das "andere Zeug" im Detail wissen, um darauf zu antworten. (2) Ist BF * Turing vollständig, wird BF und ein neues BF * mit gegebener Definition von {}und zum Mitnehmen gegeben []. mit dem Verständnis, dass BF []ein Konstrukt ist, das nur einer while-do-Schleife in Turing- Gesamtsprachen ähnelt .
VZN
1
@vzn Teil (1) war nur der TL; DR Teil meiner Frage. Mir ist völlig bewusst, dass dies wahrscheinlich nicht für "irgendeine Sprache" zu beantworten ist. Aus diesem Grund habe ich die eigentliche Frage in Bezug auf eine sehr einfache Spielzeugsprache (BF) formuliert, um sie wirklich auf das Verhalten der Schleifen einzugrenzen (weil ich dachte, wenn BF * als TC dargestellt werden kann, würde dies die Sache einfacher machen) um es für andere Sprachen anzuzeigen, die nur do-while-Schleifen haben). Ich bin mir nicht sicher, wie Sie denken, dass BF-Loops sich von den while-do-Loops anderer Sprachen unterscheiden.
Martin Ender

Antworten:

10

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 Yist äquivalent zu X; while Y do Xund, vorausgesetzt Sie haben Bedingungen, while Y do Xist äquivalent zu if 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:

B := true
while (Y and B) do
    X
    B := false
endwhile

Aber was ist, wenn Sie nur Zeit haben? Ich behaupte, dass das Folgende simuliert if Y then X, vorausgesetzt, dass es Xmit dem aktuellen Wert der Variablen endet. (Dies kann nicht garantiert werden: Das Programm wird if y=0 then loopforeverbeendet y != 0, obwohl XSchleifen für einen beliebigen Wert der Variablen ausgeführt werden.) Lassen Sie V1, ..., Vnwerden die modifizierten Variablen durch Xund lassen Sie X'werden Xso modifiziert, dass es verwendet Vi'statt Vifür jede dieser Variablen. swap(A,B)bezeichnet den offensichtlichen Code, der die Variablen Aund vertauscht B.

V1' := V1; ...; Vn' := Vn
V1'' := V1; ...; Vn'' := Vn
C := 0
do
    X'
    swap (V1',V1''); ...; swap (Vn',Vn'')
    C := C+1
while Y and C<2
V1 := V1'; ...; Vn := Vn'

Die Idee ist die folgende. Angenommen, das Yist falsch. Wir simulieren Xeinmal und speichern die Ergebnisse in V1'', ..., Vn''; V1', ..., Vn'behalten die ursprünglichen Werte von V1, ..., Vn. Dann weisen wir zu V1 := V1'; ...; Vn := Vn', was nichts bewirkt. Wenn Yalso falsch ist, haben wir nichts getan. Angenommen, das Yist wahr. Wir simulieren jetzt X zweimal und speichern die Ergebnisse in den Variablen "primed" und "double-primed". Jetzt haben die Zuweisungen am Ende der Schleife den Effekt, Xder einmal berechnet wurde. Beachten Sie, dass dies Ynur von den "nicht grundierten" Variablen abhängt, sodass der Wert nicht durch wiederholtes Ausführen der Schleife beeinflusst wird.

OK, was ist, wenn Xder 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 wir XAnweisungen für Anweisungen simulieren und dabei ähnliche Ideen wie oben verwenden. Jeder Befehl wird definitiv beendet, damit wir die ifobige 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 durchlaufen X, 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, Yob sie Xnoch angehalten hat. Wenn dies Yfalsch ist, können wir mit der Swap-Technik die Auswirkungen von rückgängig machenXerste Anweisung.

David Richerby
quelle
1
Dies ist eine nette Idee, aber ich denke, es gibt hier ein Problem: Betrachten Sie den Fall, in dem Yfalsch ist, Xaber nicht mit dem aktuellen Satz von Variablenwerten endet. if Y then Xwird beendet, Ihre Übersetzung jedoch nicht, da sie immer X'mindestens einmal ausgeführt werden muss.
Martin Ender
1
@ MartinBüttner Urgh. Du hast recht. Wir müssen also die Schleife verwenden, um XAnweisung für Anweisung zu simulieren und Ynach jeder Anweisung zu überprüfen . Jeder Befehl wird garantiert beendet, damit alles funktioniert. Aber es ist ein Schmerz, es aufzuschreiben.
David Richerby
1
Ich bin nicht ganz sicher, ob es möglich ist, so zu dekonstruieren X, wenn es mit einer while-Schleife / Bedingung selbst beginnt. Ich muss noch etwas darüber nachdenken.
Martin Ender
Außerdem: "Jetzt verwenden wir eine Schleife, um die Anweisungen von X mit einem Anweisungszeiger usw. zu durchlaufen, damit wir wissen, welche Anweisung als Nächstes auszuführen ist." Ich habe das Gefühl, dass dies an sich eine Bedingung erfordern könnte.
Martin Ender
1
Ich bin mir immer noch nicht ganz sicher, wie Sie "jede Anweisung" definieren, wenn sie X'nicht linear ist. Würde es Ihnen etwas ausmachen, mehr Details für ein einfaches, aber nicht triviales Spielzeug anzugeben X? ZB do (while A do B) while C? (Das Äußere do whilekommt von dem Äußeren while do, das wir gerade übersetzen)
Martin Ender