首页|Chaitin's Omega and an algorithmic phase transition
Chaitin's Omega and an algorithmic phase transition
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
We consider the statistical mechanical ensemble of bit string histories that are computed by a universal Turing machine. The role of the energy is played by the program size. We show that this ensemble has a first-order phase transition at a critical temperature, at which the partition function equals Chaitin's halting probability Omega. This phase transition has curious properties: the free energy is continuous near the critical temperature, but almost jumps: it converges more slowly to its finite critical value than any computable function. At the critical temperature, the average size of the bit strings diverges. We define a non-universal Turing machine that approximates this behavior of the partition function in a computable way by a super-logarithmic singularity, and discuss its thermodynamic properties. We also discuss analogies and differences between Chaitin's Omega and the partition function of a quantum mechanical particle, and with quantum Turing machines. For universal Turing machines, we conjecture that the ensemble of bit string histories at the critical temperature has a continuum formulation in terms of a string theory. (C) 2021 The Author(s). Published by Elsevier B.V.
NSTL
Elsevier
