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
Authors: Schmidhuber, Christoph
et. al: No
DOI: 10.1016/j.physa.2021.126458
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
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.
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 SizeFormat 
2021_Schmidhuber_Chaitins-Omega.pdf1.24 MBAdobe PDFThumbnail

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.