Böhm-Jacopini定理

Question

根据Böhm-Jacopini定理，只使用三个语句就可以编写算法：

• 序列
• 选择
• 迭代

很多老师认为这个定理是一种信仰行为，他们教导不使用（转，跳，断，多回等等）因为这些指示是邪恶的。

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

我个人认为这个定理不是假的，但我认为它在现实世界中的适用性并不总是更好的选择。

所以我做了一个小小的搜索，这些是我的疑惑：

1. 该定理已在流程图结构的归纳上得到证实，但它真的适用于计算机程序吗？ 根据维基百科“Böhm和Jacopini的程序转换算法并不是真正实用，因此为这方向的其他研究打开了大门”。
2. 定理的结果证明每个“goto”可以通过归纳转化为选择或迭代，但效率如何呢？我找不到任何证据表明每个算法都可以重写，保留相同的性能。
3. 递归，一个递归算法真的可以只使用序列，选择和迭代编写？我知道一些递归算法可以优化为循环（想想尾部递归），但是真的可以适用于所有人吗？
4. 干净的代码，我知道滥用跳转可以创建一个可怕的代码，但我认为在某些情况下正确使用循环中的break可以提高代码的可读性。

样品：

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

可以改写为：

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

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

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

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

Answer 1

该定理已在流程图结构的归纳上得到证实，但它真的适用于计算机程序吗？根据维基百科“Böhm和Jacopini的程序转换算法并不是真正实用，因此为这方向的其他研究打开了大门”。

它们提供的操作和结构可以很容易地显示出能够复制图灵机的功能。因此，它是图灵等效的计算系统。通过Church-Turing论文，这被认为是我们能做的尽可能多的计算：goto将不会添加任何尚未实现的内容。

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

如果不使用计算机的goto，许多算法的性能很可能会更差。你当然可以证明它是特定问题的情况。这是否会改变渐近复杂性是另一个问题，但据我所知，Bohm和Jacopini并不是一个问题。

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

由于Bohm和Jacopini的系统是图灵等效的，那么你是正确的，递归没有增加新的力量。它当然可以增加可读性。

Answer 2

任何看起来像Type 1/2/3的程序都可以转换为

Answer 3

根据Böhm-Jacopini定理，只使用三个语句就可以编写算法：

• 序列
• 选择
• 迭代

While语言具有以下结构：

1. 任务，V := E
2. 空程序，skip
3. 序列，S1;S2
4. 选择，if B then S1 [elsif Si] else Sn fi，和
5. 迭代。 while B do S od

你省略了赋值和skip，它是一个中性元素，就像算术中的0一样。我还省略了其他结构。这些与程序抽象有关，程序抽象命名语句序列，即函数和过程。但我现在不想过多地扩展它。

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

Kozen是一位非常优秀的作家，他严谨而清晰。

Kozen在证明Böhm-Jacopini定理时表现出命题演算的局限性。原始文章使用了谓词演算。他使用20世纪60年代没有的技术给出了该定理的正确证明。问题出现是因为转换使用变量，这是在命题演算中无法处理的。存在其他转换，它使用带有中断的循环而不是While语言。关于GOTO的所有讨论现在都已被充分理解。这篇文章很有意思，因为它是一个关于如何在一个古老的众所周知的问题中使用更新技术的例子。

你可以使用Böhm-Jacopini定理，因为它产生了一个等价的程序。

我个人认为这个定理不是假的，但我认为它在现实世界中的适用性并不总是更好的选择。

该结果支持结构化编程。但是你不应该使用它，因为你不应该使用数据流图来设计程序。你甚至不应该使用While伪代码来设计程序。

最佳实践是使用抽象的规范语言，该语言更适合表示您要解决的问题。证明您的解决方案，然后编写一个可以转换为您的编程语言代码的文档。这就是文学编程背后的理念。准确解释您对问题领域的了解，说明如何用抽象规范语言表示问题，并将其系统地转换为编程语言。所有的解释都应该在自然语言和数学公式中，并且代码片段应该是可分离的以产生程序代码。为此，您可以使用CWeb和LaTeX等程序。

新的声明性语言非常接近规范语言，但最好坚持上述建议。虽然这些语言推断类型，但有时数据结构中的细节会在设计过程中分散注意力。稍后应该详细说明类型，以便以静态类型编程语言实现程序。这是一种更好的编程习惯。