Abstract:
The statistical mechanical interpretation of algorithmic
information theory (AIT, for short) was introduced and
developed in our former work [K. Tadaki, Local Proceedings of
CiE 2008, pp.425–434, 2008], where we introduced the notion
of thermodynamic quantities into AIT. These quantities are real
functions of temperature T > 0. The values of all the thermodynamic
quantities diverge when T exceeds 1. This phenomenon
corresponds to phase transition in statistical mechanics. In this
paper we introduce the notion of strong predictability for an
infinite binary sequence and then apply it to the partition function
Z(T ), which is one of the thermodynamic quantities in AIT. We
then reveal a new computational aspect of the phase transition in
AIT by showing the critical difference of the behavior of Z(T)
between T = 1 and T < 1 in terms of the strong predictability
for the base-two expansion of Z(T).