Une boucle do-while suffit-elle pour la complétude de Turing?

22

Je sais que, dans les langages de programmation impératifs, une boucle while-do est suffisante comme construction de flux de contrôle pour rendre le langage Turing complet (en ce qui concerne le flux de contrôle - bien sûr, nous avons également besoin d'une mémoire illimitée et de certains opérateurs ...) . L'essentiel de ma question est: une boucle do-while a-t-elle la même puissance de calcul qu'une boucle while-do? En d'autres termes, une langue peut-elle être complète de Turing s'il est impossible de sauter complètement les instructions.

Je me rends compte que certaines sémantiques ici pourraient être un peu ambiguë, alors laissez-moi formuler la question réelle avec un exemple spécifique:

Brainfuck (BF) est un tarpit Turing où le seul flux de contrôle est une boucle while-do, notée [...](il y a une spécification de langue complète au bas de la question, au cas où vous n'êtes pas familier avec Brainfuck). Définissons un nouveau langage BF *, où ,.+-<>ont la même sémantique que dans BF, mais au lieu de []nous avons {}qui dénote une boucle do-while. Autrement dit, la seule différence avec BF est que chaque boucle est exécutée au moins une fois avant que d'autres itérations puissent être ignorées.

BF * Turing est-il complet? Si c'est le cas, je serais intéressé par la façon dont je pourrais traduire BF en BF *. Si ce n'est pas le cas, comment puis-je le prouver?

Quelques observations personnelles:

  • Tous les programmes BF ne peuvent pas être traduits en BF *. Par exemple, il est impossible d'écrire un programme en BF * qui peut ou non lire ou imprimer une valeur - si le programme imprime potentiellement une ou plusieurs valeurs, il en imprimera toujours au moins une. Cependant, il pourrait y avoir un sous-ensemble complet de Turing de BF qui peut être traduit en BF *.
  • Nous ne pouvons pas simplement traduire [f](où fest un programme Brainfuck arbitraire composé uniquement de +-[]<>) en (pour tenter d'annuler l'effet de la première itération), car a) toutes les fonctions calculables n'ont pas un inverse calculable et b) même si c'était le cas, n'aurait pas nécessairement moins de boucles que si l'application de cette étape de manière récursive n'est pas garantie de se terminer en premier lieu.f-1{f}f-1f

Voici un bref aperçu de la langue de Brainfuck. Brainfuck fonctionne sur une bande infinie où chaque cellule contient une valeur d'octets, initialement zéro. Les débordements s'enroulent, donc l'incrémentation de 255 donne 0 et vice versa. La langue se compose de 8 instructions:

+   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
la source
intéressant mais pense qu'il n'est pas entièrement construit avec soin. []ne définit pas exactement une boucle "while do" dans BF. comme dans votre tableau, les crochets gauche et droit évaluent la cellule actuelle zéro / non nulle. alors quelle est la description exacte de la {}logique d'évaluation des accolades correspondante ? suggérer d'autres dialogues / discussions dans le chat informatique . aussi vos "observations" sont plutôt des "postulats" ou des "propositions" sans preuve.
vzn
@vzn Ce sont de bons points. J'ai pensé que la définition évidente de {}serait de {ne rien faire du tout et de }la même manière que ]. Je n'aurai pas beaucoup de temps au cours des prochains jours, mais je vous rejoindrai dans le chat lorsque j'en trouverai un peu.
Martin Ender
donc hélas, c'est apparemment quelque peu subtil à poser et il semble y avoir ici deux questions totalement différentes. (1) étant donné n'importe quel langage complet de Turing avec une boucle while-do (et "d'autres choses"), peut-il être converti en un langage complet de Turing avec seulement une boucle do-while à la place. mais alors il faut en savoir plus sur les "autres trucs" en détail pour répondre. (2) étant donné le BF et un nouveau BF * avec une définition {}et un prélèvement donnés [], le BF * Turing est complet. avec la compréhension que BF []est une construction seulement quelque chose de quelque chose comme / analogue à une boucle while-do dans les langages complets de Turing.
vzn
1
La partie @vzn (1) n'était que la partie TL; DR de ma question. Je suis pleinement conscient qu'il est probablement impossible de répondre à "une certaine langue". C'est pourquoi j'ai formulé la question réelle en termes de langage de jouet très simple (BF) pour le réduire vraiment au comportement des boucles (parce que je me suis dit si BF * peut être montré comme TC qui le rendrait plus simple pour l'afficher pour d'autres langues qui n'ont que des boucles do-while). Je ne sais pas comment vous pensez que les boucles BF sont différentes des boucles while-do d'autres langues.
Martin Ender

Réponses:

10

Je ne connais pas Brainfuck, vous devrez donc faire une traduction de mon pseudocode. Mais, en supposant que Brainfuck se comporte raisonnablement (ha!), Tout ce qui suit devrait s'appliquer.

do-while est équivalent à while-do. do X while Yest équivalent à X; while Y do Xet, en supposant que vous avez des conditions, while Y do Xest équivalent à if Y then (do X while Y).

La vie est un peu plus difficile si vous n'avez pas de conditionnels. Si vous avez du temps, vous pouvez simuler en if Y then Xutilisant quelque chose comme ceci:

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

Mais que faire si vous n'avez que du temps? Je prétends que ce qui suit simule if Y then X, en supposant que se Xtermine étant donné la valeur actuelle des variables. (Ce n'est pas garanti: le programme se if y=0 then loopforevertermine si y != 0, même s'il Xboucle pour n'importe quelle valeur des variables). Soit V1, ..., Vnles variables modifiées par Xet laissons X'être Xmodifié de sorte qu'il utilise à la Vi'place de Vichacune de ces variables swap(A,B)désigne le code évident qui permute les variables Aet 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'

L'idée est la suivante. Tout d'abord, supposons que Yc'est faux. Nous simulons faire Xune fois et stockons les résultats dans V1'', ..., Vn''; V1', ..., Vn'maintiennent les valeurs d'origine de V1, ..., Vn. Ensuite, nous attribuons V1 := V1'; ...; Vn := Vn', ce qui ne fait rien. Donc, si Yc'est faux, nous n'avons rien fait. Maintenant, supposons que Yc'est vrai. Nous allons maintenant simuler X deux fois , en stockant les résultats dans les variables "primed" et "double-primed". Donc, maintenant, les affectations à la fin de la boucle ont l'effet qui a Xété calculé une fois. Notez que cela Yne dépend que des variables "non amorcées", donc sa valeur n'est pas affectée par l'exécution répétée de la boucle.

OK, que se passe-t-il si Xcela ne se termine pas pour la valeur actuelle des variables? (Merci à Martin Ender d'avoir souligné cette possibilité.) Dans ce cas, nous devons simuler Xinstruction par instruction, en utilisant des idées similaires à celles ci-dessus. Chaque instruction se termine définitivement afin que nous puissions utiliser la ifsimulation ci-dessus pour effectuer le décodage des instructions, sur le modèle "Si l'opcode est fou, faites ceci; si c'est une barre, faites cela; ...". Donc, maintenant, nous utilisons une boucle pour parcourir les instructions de X, en utilisant un pointeur d'instruction et ainsi de suite afin de savoir quelle instruction exécuter ensuite. À la fin de chaque itération de la boucle, vérifiez Yet vérifiez si Xelle s'est encore arrêtée. Si Yest faux, la technique de permutation nous permet d'annuler les effets deXest la première instruction.

David Richerby
la source
1
C'est une bonne idée, mais je pense qu'il y a un problème ici: considérez le cas où Yest faux mais Xne se termine pas sur l'ensemble actuel de valeurs de variable. if Y then Xse termine, mais pas votre traduction, car elle doit toujours être exécutée X'au moins une fois.
Martin Ender
1
@ MartinBüttner Urgh. Tu as raison. Nous devons donc utiliser la boucle pour simuler Xinstruction par instruction et vérifier Yaprès chaque instruction. La fin de chaque instruction est garantie afin que tout fonctionne. Mais c'est pénible à écrire.
David Richerby
1
Je ne suis pas tout à fait sûr s'il est possible de déconstruire Xcomme ça s'il commence par une boucle while / conditionnelle elle-même. Je vais devoir y penser un peu plus.
Martin Ender
"Donc, maintenant, nous utilisons une boucle pour parcourir les instructions de X, en utilisant un pointeur d'instruction et ainsi de suite afin de savoir quelle instruction exécuter ensuite." Je pense que cela en soi pourrait nécessiter une condition quelconque.
Martin Ender
1
Je ne sais toujours pas exactement comment vous définissez "chaque instruction" si elle X'est non linéaire. Pourriez-vous inclure plus de détails pour un jouet simple mais non trivial X? Par exemple do (while A do B) while C? (l'extérieur do whilevient de l'extérieur while doque nous traduisons actuellement)
Martin Ender