ALGORITHMIC INFORMATION AND SIMPLICITY IN STATISTICAL PHYSICS

Applications of algorithmic information theory to statistical physics rely (a) on the fact that average conditional algorithmic information can be approximated by Shannon information and (b) on the existence of simple states described by short programs. More precisely, given a li st of N states with probabilities 0 < p(1) less than or equal to ...le ss than or equal to P-N, the average conditional algorithmic informati on (I) over bar to specify one of these states obeys the inequality H less than or equal to (I) over bar < H + O(1), where H = -Sigma p(j) l og(2)p(j) and O(1) is a computer-dependent constant. We show how any u niversal computer can be slightly modified in such a way that (a) the inequality becomes H less than or equal to (I) over bar < H + 1 and (b ) states that are simple with respect to the original computer remain simple with respect to the modified computer, thereby eliminating the computer-dependent constant from statistical physics.