Czy pętla „do while” jest wystarczająca dla kompletności Turinga?

Wiem, że w imperatywnych językach programowania pętla while-do jest wystarczająca jako konstrukcja przepływu sterowania, aby uzupełnić język Turinga (jeśli chodzi o przepływ sterowania - oczywiście potrzebujemy również nieograniczonej pamięci i niektórych operatorów ...) . Istota mojego pytania brzmi: czy pętla „do-while” ma taką samą moc obliczeniową jak pętla „do-do”? Innymi słowy, czy język może być kompletny przez Turinga, jeśli nie można całkowicie pominąć instrukcji.

Zdaję sobie sprawę, że niektóre semantyki mogą być nieco niejednoznaczne, więc pozwólcie, że sformułuję rzeczywiste pytanie konkretnym przykładem:

Brainfuck (BF) to tarpit Turinga, w którym jedynym przepływem kontrolnym jest pętla while-do, oznaczona jako [...](na dole pytania znajduje się pełna specyfikacja języka, na wypadek, gdyby nie znasz Brainfuck). Zdefiniujmy nowy język BF *, w którym ,.+-<>ma taką samą semantykę jak w BF, ale zamiast tego []mamy {}co oznacza pętlę „do-while”. Oznacza to, że jedyną różnicą w stosunku do BF jest to, że każda pętla jest wykonywana co najmniej raz, zanim możliwe będzie pominięcie kolejnych iteracji.

Czy BF * Turing jest kompletny? Jeśli tak, byłbym zainteresowany tym, jak mógłbym przetłumaczyć BF na BF *. Jeśli nie, to jak to udowodnić?

Kilka moich własnych obserwacji:

• Nie każdy program BF można przetłumaczyć na BF *. Na przykład niemożliwe jest napisanie programu w BF *, który może, ale nie musi, odczytać lub wydrukować wartość - jeśli program potencjalnie wydrukuje jedną lub więcej wartości, zawsze wydrukuje przynajmniej jedną. Jednak może istnieć kompletny podzbiór BF Turinga, który można przetłumaczyć na BF *.
• Nie możemy po prostu tłumaczyć [f](gdzie fjest jakiś arbitralny program składający się tylko z Brainfuck +-[]<>) na (w celu anulowania efektu pierwszej iteracji), ponieważ a) nie każda funkcja obliczalna ma obliczalną odwrotność i b) nawet jeśli tak, niekoniecznie miałoby mniej pętli niż dlatego rekursywne wykonanie tego kroku nie gwarantuje zakończenia.f-1{f}f-1f

Oto krótki przegląd języka Brainfuck. Brainfuck działa na nieskończonej taśmie, w której każda komórka zawiera wartości bajtów, początkowo zerowe. Przepełnienia się zawijają, więc zwiększenie 255 daje 0 i odwrotnie. Język składa się z 8 instrukcji:

+   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 [.

Nie znam Brainfuck, więc będziesz musiał zrobić tłumaczenie z mojego pseudokodu. Ale zakładając, że Brainfuck zachowuje się rozsądnie (ha!), Wszystko poniżej powinno mieć zastosowanie.

do-while jest równoważne do while-do. do X while Yjest równoważne X; while Y do Xi, zakładając, że masz warunki warunkowe, while Y do Xjest równoważne z if Y then (do X while Y).

Życie jest trochę trudniejsze, jeśli nie masz warunkowych. Jeśli masz czas na wykonanie, możesz przeprowadzić symulację, if Y then Xużywając czegoś takiego:

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

Ale co, jeśli masz tylko czas do zrobienia? Twierdzę, że następujące symuluje if Y then X, zakładając, że Xkończy się, biorąc pod uwagę bieżącą wartość zmiennych. (Nie jest to gwarantowane: program if y=0 then loopforeverkończy działanie y != 0, nawet jeśli Xzapętla dowolną wartość zmiennych). Niech V1... Vnbędą zmiennymi modyfikowanymi przez Xi niech X'będą Xmodyfikowane, aby używał Vi'zamiast Vidla każdej z tych zmiennych. swap(A,B)oznacza oczywisty kod, który zamienia zmienne Ai 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'

Pomysł jest następujący. Po pierwsze, załóżmy, że Yto fałsz. Symulujemy zrobienie tego Xraz i przechowujemy wyniki w V1''..., Vn''; V1', ... Vn'zachowaj oryginalne wartości V1, ..., Vn. Następnie przypisujemy V1 := V1'; ...; Vn := Vn', co nie robi nic. Więc jeśli Yjest to fałsz, nic nie zrobiliśmy. Załóżmy, że Yto prawda. Teraz przeprowadzimy symulację X dwa razy , przechowując wyniki zarówno w zmiennych „zagruntowanych”, jak i „podwójnie zagruntowanych”. Zatem teraz przypisania na końcu pętli mają efekt, który Xzostał obliczony raz. Zauważ, że Yzależy tylko od zmiennych „nieprzygotowanych”, więc na jego wartość nie ma wpływu wielokrotne uruchamianie pętli.

OK, a co jeśli Xnie może zakończyć się dla bieżącej wartości zmiennych? (Podziękowania dla Martina Endera za wskazanie tej możliwości.) W takim przypadku musimy przeprowadzić symulację Xinstrukcja po instrukcji, używając podobnych pomysłów do powyższych. Każda instrukcja definitywnie kończy się, więc możemy użyć ifpowyższej symulacji, aby wykonać dekodowanie instrukcji, zgodnie z zasadą „Jeśli kod operacji jest foo, zrób to; jeśli to pasek, zrób to; ...”. Tak więc teraz używamy pętli, aby iterować instrukcje X, używając wskaźnika instrukcji i tak dalej, abyśmy wiedzieli, którą instrukcję wykonać następnie. Na końcu każdej iteracji pętli sprawdź Yi sprawdź, czy Xjeszcze się zatrzymała. Jeśli Yjest fałszem, technika zamiany pozwala nam cofnąć efektyXpierwsza instrukcja.