A statistical mechanical interpretation of algorithmic information theory III: Composite systems and fixed points
A statistical mechanical interpretation of algorithmic information theory III: Composite systems and fixed points
复制标题
算法信息论的统计力学解释 III：复合系统和不动点
DOI：
10.1017/s096012951100051x
复制
发表时间：
2012
影响因子：
0.5
通讯作者：
K. Tadaki
中科院分区：
文献类型：
--
作者：
Yamamoto;K.;Murakami;K.;and Tomizawa;S.;K. Tadaki
算法信息论（简称AIT）的统计力学解释在我们之前的论文Tadaki（2008; 2012）中得到了介绍和发展，我们在AIT中引入了热力学量的概念，如配分函数Z(T)、自由能F(T)、能量E(T)和统计力学熵S(T)。然后我们发现，在解释中，温度T等于所有这些热力学量的值的部分随机性，其中部分随机性的概念是通过程序大小复杂性的方式更有力地表示压缩率。进一步，我们证明了这种情况对于温度本身作为一个热力学量成立，即对于上述每一个热力学量，其在温度T处的值的可计算性给出了T∈(0,1)是部分随机性上的不动点的充分条件。在本文中，我们进一步发展了AIT的统计力学解释，并追求其与正规统计力学的形式对应。最优无前缀机是一种通用解码算法，用于定义程序大小复杂度的概念，在此基础上定义了最优无前缀机的停止集。我们证明了存在无穷多个最优无前缀机，它们对AIT中的每一个热力学量给出完全不同的充分条件。我们通过在AIT中引入无前缀机器组合的概念来做到这一点，它对应于正常统计力学中系统组合的概念。
The statistical mechanical interpretation of algorithmic information theory (AIT for short) was introduced and developed in our previous papers Tadaki (2008; 2012), where we introduced into AIT the notion of thermodynamic quantities, such as the partition function Z(T), free energy F(T), energy E(T) and statistical mechanical entropy S(T). We then discovered that in the interpretation, the temperature T is equal 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 the thermodynamic quantities above, the computability of its value at temperature T gives a sufficient condition for T ∈ (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 on the basis of the halting set of an optimal prefix-free machine, which is a universal decoding algorithm used to define the notion of program-size complexity. We show that there are infinitely many optimal prefix-free machines that give completely different sufficient conditions for each of the thermodynamic quantities in AIT. We do this by introducing the notion of composition of prefix-free machines into AIT, which corresponds to the notion of the composition of systems in normal statistical mechanics.