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

22

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 [.
Martin Ender
fonte
interessante, mas acho que não é totalmente construído com cuidado. []não está definindo exatamente um loop "while do" no BF. como em sua tabela, os colchetes esquerdo e direito avaliam a célula atual zero / diferente de zero. então, qual é a descrição exata da {}lógica de avaliação de chaves correspondente ? sugerir mais diálogo / discussão no bate-papo sobre ciência da computação . também suas "observações" são mais parecidas com "postulados" ou "proposições" sem provas.
vzn
@vzn Esses são bons pontos. Imaginei que a definição óbvia de {}seria {fazer nada e }igual a ]. Não terei muito tempo nos próximos dias, mas me juntarei a você no bate-papo quando encontrar algum tempo.
Martin Ender
então, infelizmente, isso é aparentemente um pouco sutil e parece haver duas perguntas totalmente diferentes aqui. (1) dado qualquer idioma completo de Turing com um loop while-do (e "outras coisas"), ele pode ser convertido em um idioma completo de Turing apenas com um loop do-while. mas é preciso saber mais sobre as "outras coisas" em detalhes para responder. (2) dado AM e um novo AM * com determinada definição {}e retirada [], é AM * Turing completo. com o entendimento de que o BF []é uma construção apenas algo parecido / análogo a um loop while-do em linguagens completas de Turing.
vzn 29/09/2015
1
A parte @vzn (1) era apenas a parte TL; DR da minha pergunta. Estou perfeitamente ciente de que provavelmente é impossível responder a "alguma linguagem". É por isso que eu formulei a pergunta real em termos de uma linguagem de brinquedo muito simples (BF) para realmente reduzi-la ao comportamento dos loops (porque eu imaginei se BF * pode ser mostrado como TC, o que tornaria mais simples para mostrá-lo em outros idiomas que possuem apenas loops do-while). Não tenho certeza de como você acha que os loops BF são diferentes dos loops while-do de outras línguas.
Martin Ender

Respostas:

10

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

David Richerby
fonte
1
Essa é uma ideia interessante, mas acho que há um problema aqui: considere o caso em que Yé falso, mas Xnão termina no conjunto atual de valores de variáveis. if Y then Xtermina, mas sua tradução não, porque sempre precisa ser executada X'pelo menos uma vez.
Martin Ender
1
@ MartinBüttner Urgh. Você está certo. Portanto, precisamos usar o loop para simular Xinstrução por instrução e verificar Yapós cada instrução. Cada instrução é garantida para terminar, para que tudo funcione. Mas é uma pena escrever.
precisa saber é o seguinte
1
Não tenho certeza se é possível desconstruir Xassim se começar com um loop while / próprio. Vou ter que pensar um pouco mais sobre isso.
Martin Ender
Além disso, "agora, usamos um loop para percorrer as instruções de X, usando um ponteiro de instruções e assim por diante, para sabermos qual instrução executar a seguir". Eu sinto que isso por si só pode exigir algum tipo de condicional.
Martin Ender
1
Ainda não tenho muita certeza de como você define "cada instrução" se X'não for linear. Você se importaria em incluir mais alguns detalhes de um brinquedo simples, mas não trivial X? Por exemplo do (while A do B) while C? (o exterior do whilevem do exterior while doque estamos traduzindo atualmente)
Martin Ender