A statistical mechanical interpretation of algorithmic

information theory

Algorithmic information theory (AIT, for short) is a framework to apply information-theoretic and probabilistic ideas to recursive function theory. One of the primary concepts of AIT is the program-size complexity H(s) of a finite binary string s, which is defined as the size of the shortest program for a universal decoding algorithm U to output s. By the definition, H(s) can be regarded as the size of the optimal compression of a finite binary string s. Furthermore, the notion of program-size complexity enables us to consider the notion of compression rate for an infinite binary string, or equivalently, a real.

In this talk, we develop a statistical mechanical interpretation of AIT by introducing the notion of thermodynamic quantities at temperature T, such as partition function Z(T), free energy F(T), energy E(T), and statistical mechanical entropy S(T), into AIT. These quantities are real functions of a real argument T > 0, and are defined using all programs of U based on the identifications of programs of U with energy eigenstates in statistical mechanics and of the length of the programs with the energy of the energy eigenstates. We investigate the properties of these quantities by means of program-size complexity from the point of view of AIT. It is then discovered that, in the interpretation, the temperature T equals to the compression rate of the values of all these thermodynamic quantities if T is a computable real in (0,1).

Furthermore, we show that this situation holds for the temperature T itself as a thermodynamic quantity. Namely, we show that, for every T in (0,1), if the value of partition function Z(T) is computable, then the compression rate of T equals to T itself. Thus, the computability of the value of partition function Z(T) gives a sufficient condition for T in (0,1) to be a fixed point on compression rate. In addition, we show that the computability of each of the thermodynamic quantities F(T), E(T), and S(T) also gives the sufficient condition. Moreover, based on the statistical mechanical relation F(T) = - T \log_2 Z(T), we show that the computability of F(T) gives completely different fixed points from the computability of Z(T), in particular.

Retrieved from http://www.lix.polytechnique.fr/~bournez/PC2009/i.php/Main/KohtaroTadaki

Page last modified on August 03, 2009, at 11:04 AM