Effects of Kolmogorov Complexity Present in Inductive Inference as Well

Abstract

For all complexity measures in Kolmogorov complexity the effect discovered by P. Martin-Löf holds. For every infinite binary sequence there is a wide gap between the supremum and the infimum of the complexity of initial fragments of the sequence. It is assumed that that this inevitable gap is characteristic of Kolmogorov complexity, and it is caused by the highly abstract nature of the unrestricted Kolmogorov complexity. We consider the complexity of inductive inference for recursively enumerable classes of total recursive functions. This object is considered as a rather simple object where no effects from highly abstract theories are likely to be met. Here, similar gaps were discovered. Moreover, the existence of these gaps is proved by an explicit use of the theorem by P. Martin-Löf. In our paper, we study a modification of inductive inference complexity. The complexity is usually understood as the maximum of mindchanges over the functions defined by the first n indices of the numbering. Instead we consider the mindchange complexity as the maximum over the first n functions in the numbering (disregarding the repeated functions. Linear upper and lower bounds for the mindchange complexity are proved. However, the gap between bounds for all n and bounds for infinitely many n , remains.