Fixed point theorems on partial randomness
Fixed point theorems on partial randomness
复制标题
部分随机性的不动点定理
DOI：
10.1016/j.apal.2011.09.018
复制
发表时间：
2012
影响因子：
0.8
通讯作者：
K. Tadaki
中科院分区：
文献类型：
--
作者：
Kayo Sugitani;Mayuko Sera;Kazuhiro Ogai;Yoshiki Koriyama;Keisuke Wakasugi;Satoru Kato;K. Tadaki
在我们以前的工作中[K. Tadaki，算法信息理论的统计机械解释，在：欧洲2008年可计算性的本地程序，CiE 2008，pp. 425-434，2008年6月15-20日，希腊雅典大学。扩展版本可在arXiv：0801.4194v1]中获得，我们通过在理论中引入温度T下的热力学量的概念，如自由能F（T），能量E（T）和统计机械熵S（T），开发了算法信息理论的统计机械解释。这些量是真实的自变量T>0的真实的函数。然后，我们发现，在解释中，温度T等于所有这些热力学量的值的部分随机性，其中部分随机性的概念是通过程序大小复杂性来更强地表示压缩率。此外，我们还证明了这种情况对于作为热力学量的温度本身也成立。即，配分函数Z（T）值的可计算性给出了T∈（0，1）是部分随机不动点的充分条件。本文证明了上述热力学量的可计算性也给出了充分条件。此外，我们证明了F（T）的可计算性给出了与Z（T）的可计算性完全不同的不动点。
In our former work [K. Tadaki, A statistical mechanical interpretation of algorithmic information theory, in: Local Proceedings of Computability in Europe 2008, CiE 2008, pp. 425–434, June 15–20, 2008, University of Athens, Greece. Extended Version Available at arXiv:0801.4194v1], we developed a statistical mechanical interpretation of algorithmic information theory by introducing the notion of thermodynamic quantities at temperature T, such as free energy F(T), energy E(T), and statistical mechanical entropy S(T), into the theory. These quantities are real functions of real argument T>0. 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 program-size complexity. Furthermore, we showed that this situation holds for the temperature itself as a thermodynamic quantity. Namely, the computability of the value of partition function Z(T) gives a sufficient condition for T∈(0,1) to be a fixed point on partial randomness. In this paper, we show that the computability of each of all the thermodynamic quantities above gives the sufficient condition also. Moreover, we show that the computability of F(T) gives completely different fixed points from the computability of Z(T).