Physics and Computation
2009

Furthermore, we show that this situation holds for the

In this talk, we develop a statistical mechanical interpretation

!! Talk from Kohtaro Tadaki

!!! Title

A statistical mechanical interpretation of algorithmic
information theory

!!! Abstract

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.