Abstract:
The quantity of information in a word is measured by its Kolmogorov complexity. But not all words with the same Kolmogorov complexity have the same properties. Beyond complexity, there are some "information" characteristics of a word. These characteristics can be represented not as a single number but rather as a curve: how fast the complexity increase when we bound the time of computation; or, which two-parts descriptions exist for this word; or, how close to the end of the list we put our word while enumerating all words of complexity at most N, etc.
We suppose to survey the basic and simple results and discuss in more detail some more involved ones (by works of Vereshchagin, Vitanyi, gacs, tromp, Antunes, etc.)
|
