470
个编辑
更改
跳到导航
跳到搜索
第240行：
第240行： + + + + + +
完成第二节B部分的第3、4、5段
当|P|是程序P的比特长度时？从一方面来看，如果有一个固定长度的程序P能生成O的任意若干比特位，那么这个极限将会消失。在我们感兴趣的绝大多数域里，有理数或无理数——比如π, e,√2——属于这个域。这些数域是非常压缩的：程序P是压缩的描述，所以它能捕捉符合描绘O序列的斑图。如果这个极限趋于1，从另一方面来看，我们拥有一个完全未压缩的描述和结论，按柯尔莫哥洛夫和蔡汀的观点，O是随机的【35-38，40，41】。这个结论正是需要的：柯尔莫哥洛夫和蔡汀框架建立了，至少在形式上，单个物体的随机性，不在提出概率描述或重构事件系综。它之所以能做到这样，是涉及到一个确定性的，算法表征——通用图灵机（UTM）。
当|P|是程序P的比特长度时？从一方面来看，如果有一个固定长度的程序P能生成O的任意若干比特位，那么这个极限将会消失。在我们感兴趣的绝大多数域里，有理数或无理数——比如π, e,√2——属于这个域。这些数域是非常压缩的：程序P是压缩的描述，所以它能捕捉符合描绘O序列的斑图。如果这个极限趋于1，从另一方面来看，我们拥有一个完全未压缩的描述和结论，按柯尔莫哥洛夫和蔡汀的观点，O是随机的【35-38，40，41】。这个结论正是需要的：柯尔莫哥洛夫和蔡汀框架建立了，至少在形式上，单个物体的随机性，不在提出概率描述或重构事件系综。它之所以能做到这样，是涉及到一个确定性的，算法表征——通用图灵机（UTM）。
将柯尔莫哥洛夫复杂度应用于自然过程，有一些众所周知的困难。首先，作为数量，它却不能进行通用计算，因为有停机问题【38】。第二，对随机过程它是最大化的。这些可以被建构起来，如同称心的一样，如同刚刚提到的。或者捕捉斑图失败，看个人的目标了。第三，它只能应用于一个过程；再一次地这可能是优点，也可能是缺点。第四，它没有为噪音或失误预留，要求准确地重构。最后，lim n->∞|Pn|/n可能消失，尽管需要运行程序的可计算资源，比如时间和存储，增长到无界。
这个障碍并不能阻止研究者在实际任务中放弃使用柯尔莫哥洛夫-蔡汀复杂度——比如测量自然物体（例子在参考文献【42】），作为归纳推理的理论基石【43，44】，也是捕捉斑图的一般意义【45】。如Rissanen【46， p. 49】所说，这个同“用写程序来学习【数据集】的属性，希望能找到最短的一个”类似。
所列出的各种困难，由后续的工作做了阐述。本内特的逻辑深度统计了时间资源【47】。（实际上它是生成O的最小长度程序所需时间）Koppel的复杂性试图从随机性，或者实际指定的输入数据，分离出程序的“法则”部分【48，49】。最终，这些扩展和泛化保留在了通用图灵机（UTM）中，精确重现设置和继承固有的不可计算性。