Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity (Q1820127)

We consider the problem of noiseless coding of combinatorial (nonstochastic) sources. The cost of the optimal code is shown to equal to the Hausdorff dimension of the source. The same problem is solved with algorithmic constraints on the code in two settings: coding and decoding realized by Turing machines and by finite automata. The lower bounds on the cost of the code in these cases are expressed in terms of the Kolmogorov complexity and the quasi-entropy, respectively. Optimal codes are constructed for sources generated by formal grammars.