Kolmogorov复杂度

Question

如果有人能够向我解释柯尔莫哥洛夫复杂度是如何与随机性和随机投入相关的，我会感激不尽。

另一件我不明白的事情 - 我们知道计算给定输入X的Kolmogorov复杂性是不可判定的。既然如此，它怎么可能是一种随机性的衡量？

感谢

Answer 1

洛夫随机是“随机”的模糊概念，直观的一个特定的定义 - 你指的要求（仅供参考http://en.wikipedia.org/wiki/Random_number）的关系时，哪些其他的定义？

我不会追问你的思维模式，为什么在一般情况下，为了使概念明确定义，必须能够确定哪些字符串是Kolmogorov随机数。你能否详细说明给你带来什么麻烦？如果没有别的，请允许我指出停止问题 - 当然，程序暂停的概念是明确定义的，尽管在一般情况下不可能确定一个特定程序是否显示该属性。

Answer 2

你应该思考另一种方式。如果不是随机的，这意味着它遵循一些法律，并且该法可以给出信息的更简单的描述。想想zip：代替文件，你给了一个过程来生成通常比源文件更紧凑的文件。这是可能的，因为源文件包含一些顺序：如果源文件是随机字符序列，则不可能进行压缩。

如果您对此主题感兴趣，我强烈建议您使用Andre'Nies的“Computability and Randomness”，Oxford Logic Guides n.51。