简单与嵌套
就图灵完整性而言，简单循环是否与嵌套循环一样强大？
Are simple loops as powerful as nested loops in terms of Turing completeness?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
就图灵完整性而言，简单循环是否与嵌套循环一样强大？
Are simple loops as powerful as nested loops in terms of Turing completeness?
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
发布评论
评论（2）
就图灵完备性而言，是的。
证明：可以使用简单的循环编写 Brainf*** 解释器，例如这里：
http://www.hevanet.com/cristofd/brainfuck/sbi.c
In terms of Turing completeness, yes they are.
Proof: It's possible to write a Brainf*** interpreter using a simple loop, for example here:
http://www.hevanet.com/cristofd/brainfuck/sbi.c
具有固定步数的 For 循环（LOOP、FOR 等）：想象一下循环的全部目的是计数到 n。如果我在外循环中循环
i次，在内循环中循环j次，而不是n = i * j，为什么会有区别？仅在一个循环中？假设程序中不允许使用 WHILE、GOTO 或类似的结构（仅赋值、IF 和固定循环）。然后所有这些程序在有限数量的步骤后结束。
提高可表达性的下一步是允许循环，其中迭代次数例如由条件确定，并且不确定是否满足该条件（例如 WHILE）。然后可能会发生程序不会停止的情况。 （这种类型的表达能力也称为图灵完备性）。
与这两种形式的程序相对应的是两种函数，它们在历史上大约在同一时间开发，称为 原始递归函数和μ-递归函数。
嵌套的数量对此不起作用。
For loops with a fixed number of steps (LOOP, FOR and similar): Imagine the whole purpose of a loop is to count to
n. Why should make it a difference if I loopitimes in an outer loop andjtimes in an inner loop as opposedn = i * jin just a single loop?Assume that no WHILE, GOTO or similar constructs are allowed in a program (just assignment, IF, and fixed loops). Then all these programs end after a finite number of steps.
The next step to more expressibility is to allow loops, where the number of iterations is e.g. determined by a condition, and it is not sure, whether this condition is ever satisfied (e.g. WHILE). Then is may happen, that a program won't halt. (This type of expressiveness is also known as Turing-completeness).
Corresponding to these two forms of programs are two kinds of functions, which were historically developed around the same time and which are called primitive recursive functions and μ-recursive functions.
The number of nestings doesn't play a role in this.