柯尔莫哥洛夫复杂度
如果有人能够向我解释柯尔莫哥洛夫复杂性如何与随机性和随机输入相关，我将非常感激。
另一件我无法理解的事情 - 我们知道计算给定输入 X 的 Kolmogorov 复杂度是不可判定的。鉴于此，它如何能够衡量随机性呢？
谢谢
I'll be more than thankful if anyone would be able to explain me how Kolmogorov complexity is related to randomness, and random inputs.
Another thing that I can't understand - we know that calculating Kolmogorov complexity of a given input X isn't decidable. Given that, how can it be a measure of randomness?
thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
柯尔莫哥洛夫随机是“随机”这一模糊直观概念的特定定义 - 在询问关系时您指的是哪个其他定义（参考http://en.wikipedia.org/wiki/Random_number）？
我不遵循您的思维模式来询问为什么人们必须能够在一般情况下确定哪些字符串是柯尔莫哥洛夫随机的，以便明确定义概念。您能详细说明一下是什么给您带来了麻烦吗？如果没有别的事，请允许我向您指出停止问题 - 当然，程序停止的概念是明确定义的，即使在一般情况下没有算法可以确定特定程序是否表现出该属性。
Kolmogorov random is a particular definition of the vague intuitive concept of 'random' - which other definition are you referring to when asking for relationship (for reference http://en.wikipedia.org/wiki/Random_number)?
I don't follow your thought pattern in asking why one would have to be able to determine in the general case which strings are Kolmogorov random in order for the concept to be well-defined. Could you elaborate on what is giving you trouble? If nothing else, allow me to point you to the halting problem - certainly the concept of a program halting is well-defined even though there can be no algorithm for determining, in the general case, whether a particular program exhibits the property.
你应该反过来想。如果某件事不是随机的，则意味着它遵循某种规律，而该规律可以对信息给出更简单的描述。想想 zip：而不是文件，您提供一个过程来生成通常比源文件更紧凑的文件。这是可能的，因为源文件包含某种顺序：如果源文件是随机的字符序列，则不可能进行压缩。
如果您对此主题感兴趣，我强烈推荐“可计算性和随机性”作者：Andre' Nies，《牛津逻辑指南》第 51 期。
You should think the other way round. If something is not random, it means it follows some law, and this law can give a simpler description of the information. Think of zip: instead of the file you give a procedure to generate the file that is usually more compact than the source file. This is possible because the source file contained some order: if the source file was a random sequence of characters no compression would have been possible.
If you are interested in this topic, I strongly recommend "Computability and Randomness" by Andre' Nies, Oxford Logic Guides n.51.