Please use this identifier to cite or link to this item:
|Publication type:||Article in scientific journal|
|Type of review:||Peer review (publication)|
|Title:||Chaitin’s Omega and an algorithmic phase transition|
|Published in:||Physica A: Statistical Mechanics and its Applications|
|Publisher / Ed. Institution:||Elsevier|
|Subjects:||Chaitin's Omega; Turing machine; Complexity; Algorithmic thermodynamics|
|Subject (DDC):||510: Mathematics|
|Abstract:||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 Ω. 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.|
|Fulltext version:||Published version|
|License (according to publishing contract):||CC BY 4.0: Attribution 4.0 International|
|Departement:||School of Engineering|
|Organisational Unit:||Institute of Data Analysis and Process Design (IDP)|
|Appears in collections:||Publikationen School of Engineering|
Files in This Item:
|2021_Schmidhuber_Chaitins-Omega.pdf||1.24 MB||Adobe PDF|
Show full item record
Schmidhuber, C. (2021). Chaitin’s Omega and an algorithmic phase transition. Physica A: Statistical Mechanics and Its Applications, 586, 126458. https://doi.org/10.1016/j.physa.2021.126458
Schmidhuber, C. (2021) ‘Chaitin’s Omega and an algorithmic phase transition’, Physica A: Statistical Mechanics and its Applications, 586, p. 126458. Available at: https://doi.org/10.1016/j.physa.2021.126458.
C. Schmidhuber, “Chaitin’s Omega and an algorithmic phase transition,” Physica A: Statistical Mechanics and its Applications, vol. 586, p. 126458, Oct. 2021, doi: 10.1016/j.physa.2021.126458.
Schmidhuber, Christoph. “Chaitin’s Omega and an Algorithmic Phase Transition.” Physica A: Statistical Mechanics and Its Applications, vol. 586, Oct. 2021, p. 126458, https://doi.org/10.1016/j.physa.2021.126458.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.