Um loop do-while é suficiente para a integridade de Turing?

Eu sei que, em linguagens de programação imperativas, um loop while-do é suficiente como uma construção de fluxo de controle para tornar a linguagem Turing completa (no que diz respeito ao fluxo de controle - é claro que também precisamos de memória ilimitada e de certos operadores ...) . A essência da minha pergunta é: um loop do-while tem o mesmo poder computacional que um loop do while? Em outras palavras, um idioma pode ser completo em Turing se for impossível ignorar completamente as instruções.

Sei que algumas das semânticas aqui podem ser um pouco ambíguas, então deixe-me formular a pergunta real com um exemplo específico:

Brainfuck (BF) é um tarpit de Turing em que o único fluxo de controle é um loop while-do, indicado como [...](há uma especificação completa de idioma na parte inferior da pergunta, caso você não esteja familiarizado com Brainfuck). Vamos definir uma nova linguagem BF *, em que ,.+-<>tenha a mesma semântica que em BF, mas em vez de a []que temos, {}denota um loop do-while. Ou seja, a única diferença para o BF é que cada loop é executado pelo menos uma vez antes que outras iterações possam ser puladas.

O BF * Turing está completo? Se for, eu estaria interessado em como eu poderia traduzir BF para BF *. Se não for, como faço para provar isso?

Algumas observações minhas:

• Nem todo programa BF pode ser traduzido para BF *. Por exemplo, é impossível escrever um programa em BF * que possa ou não ler ou imprimir um valor - se o programa potencialmente imprimir um ou mais valores, sempre imprimirá pelo menos um. No entanto, pode haver um subconjunto completo de Turing do BF que pode ser traduzido para o BF *.
• Não podemos simplesmente traduzir [f](onde fexiste algum programa Brainfuck arbitrário constituído apenas por +-[]<>) para (em uma tentativa de cancelar o efeito da primeira iteração), porque a) nem toda função computável tem um inverso computável eb) mesmo que tivesse, não necessariamente terá menos loops do que a aplicação recursiva dessa etapa não é garantida para terminar em primeiro lugar.f-1{f}f-1f

Aqui está uma rápida visão geral sobre o idioma Brainfuck. Brainfuck opera em uma fita infinita onde cada célula contém valores de bytes, inicialmente zero. Os estouros são contornados, então o aumento de 255 fornece 0 e vice-versa. O idioma consiste em 8 instruções:

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

Eu não conheço Brainfuck, então você terá que fazer alguma tradução do meu pseudocódigo. Mas, supondo que Brainfuck se comporte de maneira sensata (ha!), Tudo a seguir deve ser aplicado.

do-while é equivalente a while-do. do X while Yé equivalente a X; while Y do Xe, supondo que você tenha condicionais, while Y do Xé equivalente a if Y then (do X while Y).

A vida é um pouco mais difícil se você não tem condicionais. Se você tem um tempo de atividade, pode simular if Y then Xusando algo como isto:

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

Mas e se você tiver apenas um tempo? Eu afirmo que o seguinte simula if Y then X, assumindo que Xtermina dado o valor atual das variáveis. (Isso não é garantido: o programa if y=0 then loopforevertermina sey != 0 , embora faça um Xloop para qualquer valor das variáveis). Seja V1, ..., Vnas variáveis ​​modificadas por Xe deixe X'ser Xmodificadas para serem usadas em Vi'vez de Vipara cada uma dessas variáveis. swap(A,B)denota o código óbvio que troca as variáveis Ae 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'

A ideia é a seguinte. Primeiro, suponha que isso Yseja falso. Simulamos fazer Xuma vez e armazenamos os resultados em V1'', ..., Vn''; V1', ..., Vn'mantenha os valores originais de V1, ..., Vn. Então, atribuímos V1 := V1'; ...; Vn := Vn', o que não faz nada. Então, se Yfor falso, não fizemos nada. Agora, suponha que isso Yseja verdade. Agora simularemos X duas vezes , armazenando os resultados nas variáveis ​​"iniciadas" e "iniciadas duas vezes". Portanto, agora, as atribuições no final do loop têm o efeito Xcalculado uma vez. Observe que Ydepende apenas das variáveis ​​"não criadas", portanto, seu valor não é afetado pela execução repetida do loop.

OK, e daí se Xnão for possível finalizar o valor atual das variáveis? (Agradecemos a Martin Ender por apontar essa possibilidade.) Nesse caso, precisamos simular Xinstrução por instrução, usando idéias semelhantes às descritas acima. Cada instrução definitivamente termina para que possamos usar a primeira instrução da.if simulação acima para decodificar as instruções, seguindo as linhas de "Se o código de operação for foo, faça isso; se for barra, faça isso; ...". Então, agora, usamos um loop para iterar pelas instruções de X, usando um ponteiro de instruções e assim por diante, para sabermos qual instrução executar a seguir. No final de cada iteração do loop, verifique Ye verifique se Xainda parou. Se Yfor falso, a técnica de troca nos permite desfazer os efeitos deX