Kolmogorov复杂性近似算法

Question

我正在寻找一种算法,可以计算给定输入字符串的Kolmogorov复杂度的近似值.因此,如果K是字符串S的Kolmogorov复杂度,并且t表示时间,那么函数将表现得像这样...... limit(t-> inf)[K_approx(t,S)] = K.

Answer 1

理论上,当运行时间接近无穷大时,程序可以收敛其输入字符串的Kolmogorov复杂度.它可以通过并行运行每个可能的程序来工作,即输入字符串的长度或更短.当找到给定长度的程序时,该长度被识别为现在已知的最小长度,被打印,并且不再有程序> =该长度被尝试.该算法(很可能)将永远运行,打印更短和更短的长度,在无限时间内收敛于精确的Kolmogorov复杂度.

当然,运行指数数量的程序是非常难以控制的.更有效的算法是在StackOverflow上发布代码高尔夫.一些缺点:

• 可能需要几天才能找到好的结果.
• 它使用了大量我们最宝贵的计算资源,耗费了数千美元的生产力损失.
• 随着资源被转移到其他 计算,随着时间的推移产生的结果频率较低.
• 对于许多输入,算法过早终止 ,这意味着它通常不起作用.