Chaitin’s Omega and an algorithmic phase transition

Schmidhuber, Christoph

doi:10.1016/j.physa.2021.126458

Please use this identifier to cite or link to this item: https://doi.org/10.21256/zhaw-23835

Publication type:	Article in scientific journal
Type of review:	Peer review (publication)
Title:	Chaitin’s Omega and an algorithmic phase transition
Authors:	Schmidhuber, Christoph
et. al:	No
DOI:	10.1016/j.physa.2021.126458 10.21256/zhaw-23835
Published in:	Physica A: Statistical Mechanics and its Applications
Volume(Issue):	586
Page(s):	126458
Issue Date:	1-Oct-2021
Publisher / Ed. Institution:	Elsevier
ISSN:	0378-4371 1873-2119
Language:	English
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.
URI:	https://digitalcollection.zhaw.ch/handle/11475/23835
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:

File	Description	Size	Format
2021_Schmidhuber_Chaitins-Omega.pdf		1.24 MB	Adobe PDF	View/Open

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, 2021. Chaitin’s Omega and an algorithmic phase transition. Physica A: Statistical Mechanics and its Applications. 1 Oktober 2021. Bd. 586, S. 126458. DOI 10.1016/j.physa.2021.126458

Schmidhuber, Christoph. 2021. “Chaitin’s Omega and an Algorithmic Phase Transition.” Physica A: Statistical Mechanics and Its Applications 586 (October): 126458. https://doi.org/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.