玻姆-雅可比尼定理

Question

根据 B\xc3\xb6hm-Jacopini 定理，只需使用三个语句即可编写算法：

\n\n

\n
• 顺序
\n
• 选择
\n
• 迭代
\n

\n\n

许多老师认为定理是一种信仰行为，他们教导不要使用（goto、jump、break、multiple return 等），因为这些指令是邪恶的。

\n\n

但当我要求解释时，没有人能够提供定理的证明。

\n\n

就我个人而言，我不认为该定理是错误的，但我认为它在现实世界中的适用性并不总是更好的选择。

\n\n

所以我做了一点搜索，这些是我的疑问：

\n\n

\n

1. 该定理已经通过流程图结构的归纳得到了证明，但它真的适用于计算机程序吗？
   \n根据维基百科“B\xc3\xb6hm 和 Jacopini\ 的算法作为程序转换算法并不真正实用，因此为该方向的进一步研究打开了大门”。

\n

2. 定理的一个结果证明，每个“goto”都可以通过归纳转化为选择或迭代，但是效率呢？\n我找不到任何证据表明每个算法都可以重写并保持相同的性能。

\n

3. 递归，递归算法真的可以仅使用序列、选择和迭代来编写吗？\n我知道某些递归算法可以优化为循环（想想尾递归），但真的可以适用于所有算法吗？

\n

4. 干净的代码，我知道滥用跳转可能会创建出可怕的代码，但我认为在某些情况下正确使用循环中的中断可以提高代码的可读性。

\n

\n\n

样本：

\n\n

n = 0;\nwhile (n < 1000 || (cond1 && cond2) || (cond3 && cond4) || (cond5 && cond6)) \n{  \n   n++;  \n   //The rest of code  \n}   \n

\n\n

可以重写为：

\n\n

for (n = 0; n < 1000; n++)\n{\n   if (cond1 && cond2) break;\n   elseif (cond2 && cond3) break;\n   elseif (cond4 && cond5) break;\n   elseif (cond6 && cond7) break;\n   //The rest of code\n}\n

\n\n

就我个人而言，我认为这个定理并不是为了编写更好的代码而创建的，并且干净的代码必须遵循这个定理的想法已经因为一个奇怪的主观原因而传播到世界各地。

\n\n

\n
5. 我发现这篇有趣的文章：https://www.cs.cornell.edu/~kozen/papers/bohmjacopini.pdf \n我认为这证明了真实的程序不能被迫遵循 Jaopini 定理。
   \n你有同样的结论吗？
\n

\n\n

总结这个问题，我需要知道仅使用（序列、选择和迭代）的程序是否真的比使用不同语句的任何其他程序更好，以及是否有证明或者是否都是主观的。

\n

Answer 1

\n

该定理已通过流程图结构的归纳得到证明，但它真的适用于计算机程序吗？\n 根据维基百科“B\xc3\xb6hm 和 Jacopini\ 的程序作为程序并不真正实用变换算法，从而为该方向的进一步研究打开了大门”。

\n

\n\n

他们给出的操作和结构可以很容易地证明能够复制图灵机的功能。因此，它是一个图灵等效的计算系统。根据丘奇-图灵理论，这被认为是我们能做的尽可能多的计算：goto不会添加任何不可能的东西。

\n\n

\n

定理的一个结果证明，每个“goto”都可以通过归纳转化为选择或迭代，但是效率呢？我找不到任何证据表明每个算法都可以重写并保持相同的性能。

\n

\n\n

对于不使用计算的许多算法来说，性能很可能会更差goto。您当然可以证明特定问题的情况就是如此。这是否会改变渐近复杂性是另一个问题，但据我所知，这与博姆和雅科皮尼无关。

\n\n

\n

递归，递归算法真的可以仅使用序列、选择和迭代来编写吗？我知道一些递归算法可以优化为循环（想想尾递归），但真的可以适用于所有算法吗？

\n

\n\n

由于玻姆和雅科皮尼的系统是图灵等价的，那么你是对的，递归没有增加新的能力。它肯定会增加可读性。

\n