computation-theory - Kolmogorov 复杂性

Question

如果有人能够向我解释 Kolmogorov 复杂性如何与随机性和随机输入相关，我将不胜感激。

我无法理解的另一件事 - 我们知道计算给定输入 X 的 Kolmogorov 复杂度是不可确定的。鉴于此，它如何成为随机性的衡量标准？

谢谢

Answer 1

Kolmogorov random 是对“随机”这个模糊直观概念的特殊定义——在询问关系时您指的是哪个其他定义（供参考http://en.wikipedia.org/wiki/Random_number）？

我不遵循您的思维模式来询问为什么在一般情况下必须能够确定哪些字符串是 Kolmogorov 随机的，以便明确定义概念。你能详细说明是什么给你带来了麻烦吗？如果不出意外，请允许我指出停止问题——当然，程序停止的概念是明确定义的，即使在一般情况下没有算法可以确定特定程序是否具有该属性。

Answer 2

你应该反过来想。如果某事不是随机的，则意味着它遵循某种规律，而这种规律可以对信息进行更简单的描述。想想 zip：而不是文件，您提供了一个生成文件的过程，该文件通常比源文件更紧凑。这是可能的，因为源文件包含一些顺序：如果源文件是随机的字符序列，则不可能进行压缩。

如果你对这个话题感兴趣，我强烈推荐 Andre' Nies 的“ Computability and Randomness ”，牛津逻辑指南 n.51。