In this paper we show that the approximating the Kolmogorov complexity of a set of numbers is equivalent to having common information with the halting sequence. The more precise the approximations are, and the greater the number of approximations, the more information is shared with the halting sequence. An encoding of the 2^N unique numbers and their Kolmogorov complexities contains at least >N mutual information with the halting sequence. We also provide a generalization of the "Sets have Simple Members" theorem to conditional complexity.
翻译:在本文中,我们显示,对一组数字的科尔莫戈罗夫复杂程度的接近程度相当于拥有与停止序列相同的信息。近似越精确,近似数量越多,与停止序列共享的信息就越多。2 ⁇ N的独特数字及其科尔莫戈罗夫复杂程度的编码至少包含有停止序列的 >N 的相互信息。我们还提供了“Sets有简单成员”理论的概括性,以有条件的复杂程度为条件。