Algorithmic information and simplicity in statistical physics

Abstract

Given a list of $N$ states with probabilities $0<p_1\le \cdots \le p_N$, the average conditional algorithmic information $\bar{I}$ to specify one of these states obeys the inequality $H\le \bar{I}<H+O(1)$, where $H=-\sum p_j{\log }_2{p}_j$ and $O(1)$ is a computer-dependent constant. We show how any universal computer can be slightly modified in such a way that the inequality becomes $H\le \bar{I}<H+1$, thereby eliminating the computer-dependent constant from statistical physics.

15 pages in REVTEX 3.0, 3 postscript figures in uuencoded format, submitted to Physical Review E