–
Room P3.10, Mathematics Building
On the robustness of "useful" information measures
Given an individual object, how much information does that object contains? Is all that information useful? Kolmogorov complexity rigorously expresses the amount of information of a binary string $x$ by the length of the shortest program that given to a universal Turing machine is able to produce the string $x$. An incompressible string has high Kolmogorov complexity and thus has high information but from the computational complexity point of view it is not very useful, in the sense that, with high probability, one can produce another string as useful as the first one by flipping fair coins. So, how can one quantify, the subjective notion of useful information? There are two known approaches to achieve this goal based on Kolmogorov complexity: one measuring the amount of planing necessary to construct the object (static resources) and the second measuring the computational effort (dynamic resources) needed to produce the object. For the former one divide the smallest program producing the object into two parts: the part accounting for the useful regularities (useful information) and the part accounting for the remaining information present in the object so that the two-part description is as short as the shortest one-part description. The resulting measure is known as Sophistication. The latter approach is based on the time required to generate the object from any short description and the resulting measure is called logical depth. These two measures are formally defined with significance levels, i.e., with parameters that describe how far we are from the optimal solution, namely the Kolmogorov complexity of the object. In this talk I will explain how can we relate these two measures using the busy beaver function and prove that they both are not robust in the sense that, small changes in the significance levels can significantly change the values of the measures. This work was developed jointly with L. Antunes, B. Bauwens and A. Teixeira.