
arXiv: 2307.04530
The fine approach to measure information dependence is based on the total conditional complexity CT(y|x), which is defined as the minimal length of a total program that outputs y on the input x. It is known that the total conditional complexity can be much larger than than the plain conditional complexity. Such strings x, y are defined by means of a diagonal argument and are not otherwise interesting. In this paper we investigate whether this happens also for some natural objects. More specifically, we consider the following objects: the number of strings of complexity less than n and the lex first string of length n and complexity at least n. It is known that they have negligible mutual conditional complexities. In this paper we prove that their mutual total conditional complexities may be large. This is the first example of natural objects whose plain conditional complexity is much less than the total one.
23 pages, 5 figures
FOS: Computer and information sciences, Computer Science - Information Theory, Information Theory (cs.IT), 68
FOS: Computer and information sciences, Computer Science - Information Theory, Information Theory (cs.IT), 68
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
