¿Un bucle do-while es suficiente para completar Turing?

Sé que, en los lenguajes de programación imperativos, un bucle while-do es suficiente como una construcción de flujo de control para completar el lenguaje Turing (en lo que respecta al flujo de control, por supuesto, también necesitamos memoria ilimitada y ciertos operadores ...) . La esencia de mi pregunta es: ¿un ciclo do-while tiene el mismo poder computacional que un ciclo while-do? En otras palabras, ¿puede un idioma ser Turing completo si es imposible omitir las instrucciones por completo?

Me doy cuenta de que algunas de las semánticas aquí podrían ser un poco ambiguas, así que permítanme formular la pregunta real con un ejemplo específico:

Brainfuck (BF) es un tarpit de Turing donde el único flujo de control es un ciclo while-do, denotado como [...](hay una especificación de lenguaje completa en la parte inferior de la pregunta, en caso de que no esté familiarizado con Brainfuck). Definamos un nuevo lenguaje BF *, donde ,.+-<>tenga la misma semántica que en BF, pero en lugar de la []que tenemos, {}denota un ciclo do-while. Es decir, la única diferencia con BF es que cada bucle se ejecuta al menos una vez antes de que se puedan omitir más iteraciones.

¿Está BF * Turing completo? Si es así, me interesaría cómo podría traducir BF a BF *. Si no es así, ¿cómo pruebo eso?

Algunas observaciones mías:

• No todos los programas BF se pueden traducir a BF *. Por ejemplo, es imposible escribir un programa en BF * que pueda o no leer o imprimir un valor; si el programa potencialmente imprime uno o más valores, siempre imprimirá al menos uno. Sin embargo, puede haber un subconjunto de BF completo de Turing que se puede traducir a BF *.
• No podemos simplemente traducir [f](donde fhay algún programa arbitrario, Brainfuck que consiste solo en +-[]<>) a (en un intento de cancelar el efecto de la primera iteración), porque a) no todas las funciones computables tienen un inverso computable yb) incluso si lo hiciera, no necesariamente tendría menos bucles que, por lo tanto, aplicar este paso de forma recursiva no garantiza que termine en primer lugar.f-1{f}f-1f

Aquí hay una descripción rápida sobre el lenguaje Brainfuck. Brainfuck opera en una cinta infinita donde cada celda contiene valores de bytes, inicialmente cero. Los desbordamientos se envuelven, por lo que al incrementar 255 se obtiene 0 y viceversa. El lenguaje consta de 8 instrucciones:

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

No sé Brainfuck, así que tendrás que hacer alguna traducción de mi pseudocódigo. Pero, suponiendo que Brainfuck se comporte con sensatez (¡ja!), Todo lo que sigue debe aplicarse.

do-while es equivalente a while-do. do X while Yes equivalente a X; while Y do Xy, suponiendo que tenga condicionales, while Y do Xes equivalente a if Y then (do X while Y).

La vida es un poco más difícil si no tienes condicionales. Si tiene while-do, puede simular if Y then Xusando algo como esto:

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

Pero, ¿qué pasa si solo tienes do-while? Afirmo que lo siguiente simula if Y then X, suponiendo que Xtermina dado el valor actual de las variables. (Esto no está garantizado: el programa if y=0 then loopforevertermina si y != 0, a pesar de que realiza un Xbucle para cualquier valor de las variables). Sean V1, ..., Vnlas variables modificadas por Xy X'sean Xmodificadas para que se utilicen en Vi'lugar de Vipara cada una de esas variables. swap(A,B)denota el código obvio que intercambia las variables Ay 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'

La idea es la siguiente. Primero, suponga que eso Yes falso. Simulamos hacer Xuna vez, y almacenamos los resultados en V1'', ..., Vn''; V1', ..., Vn'mantenga los valores originales de V1, ..., Vn. Luego, asignamos V1 := V1'; ...; Vn := Vn', que no hace nada. Entonces, si Yes falso, no hemos hecho nada. Ahora, supongamos que eso Yes cierto. Ahora simularemos X dos veces , almacenando los resultados en las variables "cebado" y "cebado doble". Entonces, ahora, las asignaciones al final del ciclo tienen el efecto que Xse calculó una vez. Tenga en cuenta que Ysolo depende de las variables "sin imprimir", por lo que su valor no se ve afectado al ejecutar el bucle repetidamente.

Bien, ¿y qué tal si Xno termina el valor actual de las variables? (Gracias a Martin Ender por señalar esta posibilidad). En ese caso, necesitamos simular Xinstrucción por instrucción, usando ideas similares a las anteriores. Cada instrucción definitivamente termina para que podamos usar la ifsimulación anterior para hacer la decodificación de instrucciones, en la línea de "Si el código de operación es foo, haz esto; si es bar, haz eso; ...". Entonces, ahora, usamos un bucle para iterar a través de las instrucciones de X, usando un puntero de instrucción y así sucesivamente para que sepamos qué instrucción ejecutar a continuación. Al final de cada iteración del ciclo, verifique Yy verifique si se Xha detenido todavía. Si Yes falso, la técnica de intercambio nos permite deshacer los efectos deXLa primera instrucción.