algorithm - Kolmogorov 复杂性的最佳已知上限是多少？

Question

给定infinite time ，我们可以接近字符串的确切 Kolmogorov complexity .如果我们没有无限时间，我们仍然可以计算字符串的 Kolmogorov 复杂度的上限:

...simply compress the string s with some method, implement the corresponding decompressor in the chosen language, concatenate the decompressor to the compressed string, and measure the length of the resulting string...(Wikipedia)

是否有一种算法——保证在有限的时间内终止——提供比 len(compressed string) + len(decompressor) 更严格的 Kolmogorov 复杂度上限？ ？

Answer 1

不幸的是，K(x) 不可近似。没有上限。考虑压缩 pi。存在一个产生 pi 的小程序，所以 K(pi) 很小。但是“标准”压缩程序(zip 等)不能将 pi 压缩太多。所以 compress(pi) 很大——任意大。因此 compress(pi) - K(pi) 是无界的。

换句话说:我们不知道 K(x) 可能有多小，因此我们无法为近似值设置上限。