64 位可表示的最大数

一个数到底能否仅用 64 位“真正地表示”出来,取决于的不只是硬件限制,还有这 64 位是如何被解释的。评论者对比了整数和 IEEE 754 浮点数等固定数值格式,以及把整个 lambda 演算程序或图灵机编码进去的方案;后者可以让 64 位表示大得难以想象的数(例如通过 Busy Beaver 风格构造),但代价是任意性、不可计算性,以及几乎无法进行实用运算。争论的核心在于:需要什么约束才能避免“作弊”式编码,以及像 lambda 演算这样的模型是否足够自然、非平凡,可以作为定义这类最大数的基础。

64 位编码的任意性

  • 若干评论认为,任何 64 位字符串都可以表示任意选定的 2⁶⁴ 个值集合;如果没有约束,“最大可表示数”这个问题就没有定义得当。
  • 也有人反驳说,这种说法过于咬文嚼字:更有意思的版本是在一个固定、既有的解释下,询问最大的非平凡数。

Lambda 演算、Busy Beaver 与 Kolmogorov 复杂度

  • 讨论一致认为,文章实际上是把 lambda 演算当作一种简洁、 “自然” 的描述语言,然后询问在这种语言的 64 位中可描述的最大数。
  • 这与 Busy Beaver 风格的增长有关:把一个程序(例如一个 lambda 项)编码进去,其输出数字增长速度超过标准的大数记法。
  • 有人指出,这与 Kolmogorov 复杂度 / 最短描述有关,不同的通用形式系统之间只相差常数因子。

Binary Lambda Calculus 有多“任意”

  • 一方认为:lambda 演算是最不任意的计算形式之一;因此它的编码可以作为有意义的基准。
  • 另一方认为:具体的二进制编码(de Bruijn 索引、unary 编码、自定界格式)仍然包含设计选择,因此并非唯一的标准形式。
  • 支持者回应说,这些选择都很小、比特效率高,而且与该语言的语义高度一致。

可计算与不可计算的数

  • 澄清:每个有限整数都是可计算的;而大多数实数不是。
  • 讨论集中在 Busy Beaver 值(是整数,但函数不可计算)以及 Chaitin 常数(一个规范的不可计算实数)。
  • 争论的一部分是:通过某个预言机“知道”一个值,是否就意味着它可计算;共识是:不是,不可计算性取决于是否存在算法,而不是假想中的预言机知识。

用自定义数制“作弊”

  • 有人提出一些平凡的 64 位方案,例如位模式“1”表示“一个巨大且有名字的数”,或者表示“运行文章里的算法”。
  • 另一些人把这称为“作弊”:你实际上是在把答案写进解释器里,而不是从一个固定、通用的形式系统中推导出来。
  • 一个反复出现的约束建议是:表示方案必须早于这次特定竞赛存在,而且解释器不能内置那个巨型数的硬编码知识。

其他数制与无穷

  • 讨论中提到了 IEEE754 双精度、无穷大、posits 和 unums,但指出它们的范围与用 lambda 演算编码的 Busy Beaver 风格数字相比仍然很小。
  • 有人建议考虑无穷基数(alephs),但原始焦点被澄清为仅限于有限数。