loops - 简单与嵌套

Question

就图灵完备性而言，简单循环与嵌套循环一样强大吗？

Answer 1

就图灵完整性而言，是的。

证明：可以使用一个简单的循环来编写一个Brainf***解释器，例如这里：

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

Answer 2

对于具有固定步数的循环（LOOP、FOR 和类似）：想象一下循环的全部目的是计数到n. i如果我在外部循环中循环时间和j在内部循环中循环时间而不是n = i * j在单个循环中循环，为什么要有所作为？

假设程序中不允许使用 WHILE、GOTO 或类似结构（仅允许赋值、IF 和固定循环）。然后所有这些程序在有限数量的步骤后结束。

更可表达性的下一步是允许循环，其中迭代次数由例如条件确定，并且不确定是否曾经满足该条件（例如 WHILE）。然后可能会发生，程序不会停止。（这种表达方式也称为图灵完备性）。

与这两种形式的程序相对应的是两种函数，它们在历史上大约同时发展起来，被称为原始递归函数和μ-递归函数。

嵌套的数量在此不起作用。