也许意大利面密码猜想是错误的

作者:糖果
发布时间:2024-04-10 08:12:16 (9天前)
来源:conjecture-false.html

该面条代码猜想说，忙海狸程序应该是，在某种意义上，是复杂地。Scott Aaronson是这样说的：
Busy Beavers 不应该被“干净地分解”到主程序和子程序中——相反，最大化运行时间的方法应该是通过“意大利面条式代码”或单个 n 状态无定形质量。
这个模糊的猜想是由约书亚·泽林斯基( Joshua Zelinsky ) 提出的，是对范围更窄的猜想的一种概括。这个猜想说Busy Beaver 程序的控制流图应该是强连接的（即每个节点都应该可以从每个其他节点到达）。解释 Spaghetti Code Conjecture 的一种具体方法是作为关于 Busy Beaver 图的一组广泛的预测——节点的入口和出口连接应该被分散，或者反射节点应该不存在（或存在）等。
当我第一次听到意大利面密码猜想时，我认为这听起来是个好主意。我什至希望它可以用作新形式的程序搜索的基础。但我已经开始相信，意大利面代码猜想不仅没有实际用途，甚至不是真的。
首先，考虑搜索某个类的图灵机程序的幼稚方法，即仅枚举所有这些程序。这很快变得不可行。我早期的Beeping Busy Beaver结果实际上来自这种方法，它很悲惨。需要处理的程序太多了，而且其中很多要么是重复的，要么是垃圾。
然后我开始考虑强连通图猜想，这让我想到了一种我称之为图装饰的搜索技术。不是直接枚举程序，而是首先根据各种猜想（强连通性等）枚举图形，然后用打印和移位指令“装饰”这些图形。这确保只生成具有预期图形属性的程序。图装饰方法奏效了，它出现了一个新的冠军程序。
之后，我尝试进一步推动意大利面代码猜想并搜索越来越受限制的图。具体来说，我认为 Busy Beaver 图应该没有地形上明显的特征，并且每个节点都应该尽可能地不可区分。一些有趣的节目以这种方式出现，但没有冠军。
最终我设法实现了经典的树生成方法。这种技术是由Allen Brady在他 1964 年的论文中开发的，它已被用于查找几乎所有当前的 Busy Beaver 冠军。不要直接枚举程序，而是从唯一定义的指令是A0 -> 1RB. 然后运行它直到到达未定义的指令。生成所有可能使用的指令（忽略同构重复），然后递归地在所有程序上运行该过程，这些程序是用生成的指令扩展原始程序而产生的。（一直以来，如果满足某些终止条件就停止。）
Brady 的算法（我们可以这样称呼它）是一种比图装饰更好的生成程序的方法。虽然执行需要更长的时间，因为它需要实际运行的程序，它产生的程序少几个数量级。更少的程序可以运行更长的时间，这样可以找到运行时间更长的冠军。事实上，当我切换到使用树生成时，我发现了一个.
下面的表格根据枚举技术在 4 态 2 色搜索中的使用情况总结了枚举技术之间的差异。“产量”是生成了多少程序；“搜索”是生成的程序可以运行多少步；“冠军”是使用每种方法发现的冠军程序的停止计数。
方法	屈服	搜索	冠军
幼稚的	2 30	2 14	2,819
图形装饰	2 24	2 21	66,349
树生成	2 17	2 28	32,779,478
好的，所以树生成比图形装饰要好得多。但也许各种图形猜想仍然可以用作过滤器？Brady 算法可用于生成程序列表，然后可以删除所有没有强连接图的程序。好吧，我调查了一下，结果发现几乎每个由 Brady 算法生成的程序都已经有一个强连通图。
我相信这让我们可以得出两个结论：
强连通图猜想绝对正确。
它对改进搜索毫无用处。
另一种看待它的方式是说这个猜想并不像它最初出现的那么强。它没有告诉我们任何从树生成中已知的信息。事实上，它似乎足够弱，甚至可以证明。
强连通图猜想只是更广泛的意大利面条代码猜想的一部分。我已经争辩说前者是真的，我现在声称后者可能是假的。要了解原因，请考虑4 状态 2 色 Beeping Busy Beaver 冠军：
1RB 1LC  1RD 1RB  0RD 0RC  1LD 1LA
这个节目绝对不是意大利面。查看它的控制流图（其中蓝色箭头表示从 的转换0，红色表示从 的转换1）：
Spaghetti Code Conjecture 的一种解释是，Busy Beaver 图应该是无特征的。但是这个程序有多种鲜明的特点。仅通过观察图表就可以看出不同节点的作用：
NodeA是一个调度程序，将控制定向到B或C。
节点B和C每个节点都在 上执行 while 循环1。由于磁带上只有有限多个标记，因此这些循环肯定会终止。
Node 在 上D执行一个 while 循环0。磁带上有无数个空白方块，所以这个循环有可能永远运行。人们可能会猜测这种D作为程序驱动程序的力量，而且确实如此。
这个程序远非意大利面，而是优雅的典范。如果您研究它的时间足够长，您将能够准确地弄清楚它是如何工作的，甚至可以自信地对其进行修改。我希望我可以说是我写的，但我没有。一天早上我偶然发现了它，就像一个农民在田里发现了一块古老的石碑。
那么如果不是复杂的意大利面条式代码，那么它是如何运行这么长时间的呢？Shawn Ligocki发现该程序实现了以下类似 Collatz 的函数（L : ℕ -> ℕ）：
L(3k)     = 0
L(3k + r) = L(5k + r + 3)
–> 多汁的开放问题 <–
L 是总吗？也就是说，它总是终止吗？
如果您能以一种或另一种方式证明这一点，请在方便时尽早与我联系。
乍一看，L没有什么特别之处。但考虑L(2)：
2 | 5 | 10 | 19 | 34 | 59 | 100 | 169 | 284 | 475 | 794 | 1325 | 2210 | 3685 | 6144
L(2)的轨道为14 次迭代。这是一个短输入的长轨道，这就是这个程序赢得 BBB(4) 的方式。没有诡计；它只是利用了这个特殊的数学事实。
这让人想起Bigger Number Game的教训：
位值、指数、堆叠指数：每个都可以表示无限大的数字，从这个意义上说，它们都是等价的。但是符号系统在它们可以简明表达的数字方面差异很大……最大的数字竞赛的关键不是快速的笔法，而是简洁地捕捉庞大数字的有效范式。
将 Busy Beaver 游戏视为Bigger Number Game 的一种形式化，所有具有一定长度的图灵机程序相互竞争。在更大的数字游戏中，这是概念而不是技巧，而 BBB(4) 冠军因为它“知道”的数学而获胜。对于较长的程序，为什么会有所不同？可能在所有情况下，冠军程序都是利用奇特和晦涩数学事实的相对简单的程序。
我们还可以查看2001 年C Bignum Bakeoff的结果：
BIGNUM BAKEOFF 的目标是编写一个不超过 512 个字符（不包括空格）的 C 程序，该程序从 main() 返回尽可能大的数字，假设 C 具有可以容纳任意大整数的整数类型。
这场比赛的获胜者原来是一种忙碌的海狸变种：
最后一个获胜的条目……在 Huet-Coquand“构造演算”上对角化。这是一个高度多态的 lambda 演算，因此演算中的每一个格式良好的项都是强归一化的；或者，换句话说，一种相对强大的编程语言，它具有语言中每个格式良好的程序都会终止的特性。
亚军提交者正是Heiner Marxen，他在 1989 年共同发现了 BB(5) 冠军。这个词条实现了Goodstein 函数的一个变体，一个 Peano 算法无法证明是全函数的全函数.
因此，Bigger Number Game 和 Bignum Bakeoff 都表明 Busy Beaver 冠军将通过理论而不是技巧获胜，而 BBB(4) 冠军计划证实了这一点。也许意大利面代码猜想是错误的。但是，如果这是不合理的推断，并且这些早期的 Busy Beaver 结果无法告诉我们任何关于后来的结果呢？正如Timothy Chow所说：
在我看来，四态忙碌的海狸很简单，就像工作中的小数定律。一根 4 厘米长的意大利面条不能太纠结。
当然，我们应该对任何关于 Busy Beaver 的一般行为的广泛结论持怀疑态度。可以证明一些事实，但是意大利面密码猜想无论如何都没有得到证明，这篇文章完全是推测性的。
但 Chow 的第二个论点是，4 州冠军很简单，因为它不得不如此，这意味着复杂性只会出现在较长的程序中。事实并非如此，事实上我们可以展示一个明确的反例：
1RB 0RC  1LB 1LD  0RA 0LD  1LA 1RC
这个程序是由博伊德约翰逊发现的。运行158491 步，然后进入林循环，周期为17620 步。它的控制流图是一个活生生的噩梦：
我不知道这个程序做了什么，但它确实做了一些有趣的事情。
##### –> 深奥的开放问题 <–
这个程序有什么作用？
Boyd 的发现表明，即使在 4 态 2 色程序的空间中，简单性也不是不可避免的。所以 BBB(4) 冠军可能很复杂，但事实并非如此。因此，意大利面条代码猜想在这种情况下是错误的，但并非微不足道的错误。

1 条回复

动动手指，沙发就是你的了！

登录后才能参与评论