Approximations of Kolmogorov Complexity

01/29/2020
by   Samuel Epstein, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset