algorithm - Kolmogorov 复杂度逼近算法

Question

我正在寻找一种可以计算给定输入字符串的 Kolmogorov 复杂度近似值的算法。因此，如果 K 是字符串 S 的 Kolmogorov 复杂度，而 t 表示时间，则该函数的行为类似于这样...... limit(t->inf)[K_approx(t,S)] = K。

Answer 1

理论上，随着运行时间接近无穷大，程序可以收敛于其输入字符串的 Kolmogorov 复杂度。它可以通过并行运行输入字符串长度或更短的每个可能的程序来工作。当找到给定长度的程序时，该长度被标识为目前已知的最小长度，并被打印出来，并且不再尝试>=该长度的程序。该算法(很可能)将永远运行，打印越来越短的长度，在给定无限时间的情况下收敛于精确的 Kolmogorov 复杂度。

当然，运行指数级数量的程序是非常棘手的。一个更有效的算法是发布一个 code golf on StackOverflow .一些缺点:

• 可能需要几天时间才能找到好的结果。
• 它占用了我们大量最宝贵的计算资源，造成了数千美元的生产力损失。
• 随着资源转移到 other，随着时间的推移，生成结果的频率会降低computations .
• 算法 terminates prematurely对于许多输入，这意味着它通常不起作用。