数据压缩问题最简单的形式可能与数字及其符号有关。 数字可以用数字（“十一” 对于数字 11)，数学表达式 (“二十分之一” 1048576），字符串表达式（“五个九” 99999），专有名称（《野兽之数》 对于 666 来说， “图灵去世的那一年” 1954），或其任意组合。 任何指定都是合适的，对话者可以通过它清楚地确定我们正在谈论的数字。 显然，告诉你的对话者 “八的阶乘” 比等效符号更有效 “四万三百二十”。 这里出现了一个逻辑问题：给定数字的最短表示法是什么？
哲学家伯特兰·罗素于 1908 年发表 ，它从反面触及了数字表示法的问题： 不需要八十个字母的最小数字是多少？
这样的数字一定存在：从 3480 个俄语字母和空格中只能组成 3480 个名称，这意味着使用 3480 个字母最多可以指定 XNUMX 个数字。 这意味着不可能以这种方式指定不超过XNUMX的某个数字。
这意味着该数字将对应于指定 “八十个字母不够的最小数字”，只有 78 个字母！ 一方面，这个数字必须存在；另一方面，这个数字必须存在。 另一方面，如果这个数字存在，那么它的名称与之不对应。 悖论！
消除这一悖论的最简单方法是参考口头符号的非正式性。 就像，如果符号中只允许一组专门定义的表达式，那么 “八十个字母不够的最小数字” 不会是一个有效的符号，而实际上有用的符号，例如 “八的阶乘” 仍然可以接受。
是否有正式的方法来描述数字操作的顺序（算法）？ 有很多，它们被称为编程语言。 我们将使用显示所需数字的程序（例如，Python）来代替口头符号。 例如，对于五个 XNUMX，该程序适合 print("9"*5)。 我们将继续对给定数量的最短程序感兴趣。 这样一个程序的长度称为 数字； 它是给定数字可以压缩到的理论极限。
我们现在可以考虑一个类似的悖论，而不是贝里悖论： 千字节程序不够输出的最小数是多少？
我们将按照与之前相同的方式进行推理：有 2561024 KB 文本，这意味着 KB 程序最多只能输出 2561024 个数字。 这意味着不能通过这种方式导出不大于2561024的某个数字。
但是，让我们用 Python 编写一个程序，生成所有可能的千字节文本，运行它们以执行，如果它们输出一个数字，则将该数字添加到可到达文本的字典中。 检查完所有 2561024 种可能性后，无论需要多长时间，程序都会查找字典中缺失的最小数字并打印该数字。 显然，这样的程序将适合 XNUMX KB 的代码 - 并且将输出 XNUMX KB 程序无法输出的数字！
现在有什么问题吗？ 它不能再归因于符号的非正式性！
如果您对我们的程序需要大量内存（包含 2561024 个元素的字典（或位数组））这一事实感到困惑，那么您可以在没有它的情况下执行相同的操作：依次针对 2561024 个数字中的每个数字，遍历所有2561024个可能的方案，直到没有合适的方案为止。 这样的搜索将持续很长时间并不重要：在从号码和程序中检查少于（2561024）2对后，它将结束并找到那个非常珍惜的号码。
还是不会完成？ 事实上，在所有将要尝试的计划中，将会有 while True: pass （及其功能类似物） - 事情不会比测试这样的程序更进一步！
与贝里悖论不同，贝里悖论的问题在于符号的非正式性，在第二种情况下，我们有一个精心伪装的重新表述 。 事实上，不可能在有限的时间内确定程序的输出。 特别是柯尔莫哥洛夫复杂度 ：对于给定的数字，没有算法可以找到打印该数字的最短程序的长度； 这意味着贝里的问题没有解决方案——找到给定数字的最短口头名称的长度。
来源： habr.com