Computer Science – Information Theory
Scientific paper
2009-04-06
Computer Science
Information Theory
5 pages, no figures, final manuscript to appear in the Proceedings of the 2009 IEEE Information Theory Workshop, Taormina, Sic
Scientific paper
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 in (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 into AIT, which corresponds to the notion of composition of systems in normal statistical mechanics.
No associations
LandOfFree
A statistical mechanical interpretation of algorithmic information theory III: Composite systems and fixed points does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A statistical mechanical interpretation of algorithmic information theory III: Composite systems and fixed points, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A statistical mechanical interpretation of algorithmic information theory III: Composite systems and fixed points will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-133586