Showing cs.ITShow all
2 papers · 1 filter
cs.IT2025
All Kolmogorov complexity functions are optimal, but are some more optimal?
Bruno Bauwens, Alexander Kozachinskiy, Alexander Shen
Kolmogorov (1965) defined the complexity of a string as the minimal length of a program generating . Obviously this definition depends on the choice of the programming langu…
cs.IT2020
Inequalities for space-bounded Kolmogorov complexity
Bruno Bauwens, Peter Gács, Andrei Romashchenko +1
There is a parallelism between Shannon information theory and algorithmic information theory. In particular, the same linear inequalities are true for Shannon entropies of tuples o…