Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
https://doi.org/10.21256/zhaw-23835
Publikationstyp: | Beitrag in wissenschaftlicher Zeitschrift |
Art der Begutachtung: | Peer review (Publikation) |
Titel: | Chaitin’s Omega and an algorithmic phase transition |
Autor/-in: | Schmidhuber, Christoph |
et. al: | No |
DOI: | 10.1016/j.physa.2021.126458 10.21256/zhaw-23835 |
Erschienen in: | Physica A: Statistical Mechanics and its Applications |
Band(Heft): | 586 |
Seite(n): | 126458 |
Erscheinungsdatum: | 1-Okt-2021 |
Verlag / Hrsg. Institution: | Elsevier |
ISSN: | 0378-4371 1873-2119 |
Sprache: | Englisch |
Schlagwörter: | Chaitin's Omega; Turing machine; Complexity; Algorithmic thermodynamics |
Fachgebiet (DDC): | 510: Mathematik |
Zusammenfassung: | 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 |
Volltext Version: | Publizierte Version |
Lizenz (gemäss Verlagsvertrag): | CC BY 4.0: Namensnennung 4.0 International |
Departement: | School of Engineering |
Organisationseinheit: | Institut für Datenanalyse und Prozessdesign (IDP) |
Enthalten in den Sammlungen: | Publikationen School of Engineering |
Dateien zu dieser Ressource:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
2021_Schmidhuber_Chaitins-Omega.pdf | 1.24 MB | Adobe PDF | Öffnen/Anzeigen |
Zur Langanzeige
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.
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt, soweit nicht anderweitig angezeigt.