Kolmogorov复杂度近似算法 [英] Kolmogorov Complexity Approximation Algorithm

问题描述

我正在寻找一种算法，该算法可以计算给定输入字符串的Kolmogorov复杂度。因此，如果K是字符串S的Kolmogorov复杂度，并且t表示时间，则该函数的行为将是这样。.limit（t-> inf）[K_approx（t，S）] = K。

I'm looking for a algorithm that can compute an approximation of the Kolmogorov complexity of given input string. So if K is the Kolmogorov complexity of a string S, and t represents time, then the function would behave something like this.. limit(t->inf)[K_approx(t,S)] = K.

推荐答案

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

In theory, a program could converge on the Kolmogorov complexity of its input string as the running time approaches infinity. It could work by running every possible program in parallel that is the length of the input string or shorter. When a program of a given length is found, that length is identified as the minimum length known for now, is printed, and no more programs >= that length are tried. This algorithm will (most likely) run forever, printing shorter and shorter lengths, converging on the exact Kolmogorov complexity given infinite time.

当然，运行数量成倍的程序非常难处理一种更有效的算法是在StackOverflow上发布高尔夫代码 。缺点：

Of course, running an exponential number of programs is highly intractible. A more efficient algorithm is to post a code golf on StackOverflow. A few drawbacks:

• 要花好几天才能找到好的结果。


• 它使用大量我们最宝贵的计算资源，导致生产力损失数千美元。


• 随着资源转移到其他 计算。


• 算法终止 过早进行许多输入，这意味着它通常无法正常工作。

• It can take a few days before good results are found.
• It uses vast amounts of our most valuable computing resources, costing thousands of dollars in productivity loss.
• Results are produced with less frequency over time as resources are diverted to other computations.
• The algorithm terminates prematurely for many inputs, meaning it does not work in general.

这篇关于Kolmogorov复杂度近似算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！