Abstract:
The statistical mechanical interpretation of algorithmic
information theory (AIT, for short) was introduced and
developed by our former works [K. Tadaki, Local Proceedings
of CiE 2008, pp. 425–434, 2008] and [K. Tadaki, Proceedings of
LFCS’09, Springer’s LNCS, vol. 5407, pp. 422–440, 2009], where
we introduced the notion of thermodynamic quantities, such
as partition function Z(T ), free energy F(T ), energy E(T ),
and statistical mechanical entropy S(T ), into AIT. We then
discovered that, in the interpretation, the temperature T equals to
the partial randomness of the values of all these thermodynamic
quantities, where the notion of partial randomness is a stronger
representation of the compression rate by means of program-size
complexity. Furthermore, we showed that this situation holds for
the temperature itself as a thermodynamic quantity, namely, for
each of all the thermodynamic quantities above, the computability
of its value at temperature T gives a sufficient condition
for T 2 (0; 1) to be a fixed point on partial randomness. In
this paper, we develop the statistical mechanical interpretation
of AIT further and pursue its formal correspondence to normal
statistical mechanics. The thermodynamic quantities in AIT are
defined based on the halting set of an optimal computer, which
is a universal decoding algorithm used to define the notion of
program-size complexity. We show that there are infinitely many
optimal computers which give completely different sufficient
conditions in each of the thermodynamic quantities in AIT. We
do this by introducing the notion of composition of computers to
AIT, which corresponds to the notion of composition of systems
in normal statistical mechanics.
