Chaitin's omega and an algorithmic phase transition

DOI10.1016/j.physa.2021.126458OpenAlexW3204677836MaRDI QIDQ2668248

Christoph Schmidhuber

Publication date: 3 March 2022

Published in: Physica A (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1909.09231

zbMATH Keywords

complexityphase transitionstring theoryTuring machineChaitin's omegaalgorithmic thermodynamics

Mathematics Subject Classification ID

Statistical mechanics, structure of matter (82-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Natural halting probabilities, partial randomness, and zeta functions
• A generalization of Chaitin's halting probability \(\Omega\) and halting self-similar sets
• One complexity theorist's view of quantum computing
• Exactly marginal operators and running coupling constants in two-dimensional gravity.
• Phase Transition between Unidirectionality and Bidirectionality
• Phase Transition and Strong Predictability
• Dependence of dissipation on the initial distribution over states
• Irreversibility and Heat Generation in the Computing Process
• A Theory of Program Size Formally Identical to Information Theory
• A formal theory of inductive inference. Part II