Simple vs. Nested de

Question

sont simples boucles aussi puissantes que des boucles imbriquées en termes de Turing-complet?

Answer 1

En termes de Turing-complet, oui ils sont.

Preuve: Il est possible d'écrire un Brainf *** interprète à l'aide d'une simple boucle, pour par exemple ici:

http://www.hevanet.com/cristofd/brainfuck/sbi.c

Answer 2

Pour les boucles avec un nombre fixe d'étapes (LOOP, FOR et similaires): Imaginez tout l'objet d'une boucle est de compter jusqu'à n. Pourquoi devrait faire une différence si les temps de i boucle I en un temps de boucle externe et j dans une boucle intérieure comme n = i * j opposé en une seule boucle?

On suppose que pas TANDIS, GOTO ou constructions similaires sont autorisés dans un programme (juste affectation, IF et boucles fixes). Ensuite, tous ces programmes se terminent après un nombre fini d'étapes.

L'étape suivante de plus expressibilité est de permettre à des boucles, où le nombre d'itérations est, par exemple déterminé par une condition, et il ne sait pas, si cette condition est toujours satisfaite (par exemple EN). Puis est peut arriver, qu'un programme ne s'arrêtera pas. (Ce type d'expressivité est également connu comme Turing complet ).

correspondant à ces deux formes de programmes sont deux types de fonctions, qui ont été historiquement développées dans le même temps et que l'on appelle fonctions primitives récursives et fonctions µ-récursives .

Le nombre d'imbrications ne joue pas un rôle dans ce domaine.