Algorithmic thermodynamics

DOI10.1017/S0960129511000521MaRDI QIDQ2919939zbMATH OpenOpenAlexDBLPWikidataFDO

Authors John Baez, Mike Stay

Publication date 23 October 2012

Published in MSCS. Mathematical Structures in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

algorithmic entropyalgorithmic information theoryGibbs ensemblethermodynamic cyclesTuring machine

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Statistical thermodynamics (82B30)

Abstract: Algorithmic entropy can be seen as a special case of entropy as studied in statistical mechanics. This viewpoint allows us to apply many techniques developed for use in thermodynamics to the subject of algorithmic information theory. In particular, suppose we fix a universal prefix-free Turing machine and let X be the set of programs that halt for this machine. Then we can regard X as a set of 'microstates', and treat any function on X as an 'observable'. For any collection of observables, we can study the Gibbs ensemble that maximizes entropy subject to constraints on expected values of these observables. We illustrate this by taking the log runtime, length, and output of a program as observables analogous to the energy E, volume V and number of molecules N in a container of gas. The conjugate variables of these observables allow us to define quantities which we call the 'algorithmic temperature' T, 'algorithmic pressure' P and algorithmic potential' mu, since they are analogous to the temperature, pressure and chemical potential. We derive an analogue of the fundamental thermodynamic relation dE = T dS - P d V + mu dN, and use it to study thermodynamic cycles analogous to those for heat engines. We also investigate the values of T, P and mu for which the partition function converges. At some points on the boundary of this domain of convergence, the partition function becomes uncomputable. Indeed, at these points the partition function itself has nontrivial algorithmic entropy.

Review text

The analogy between algorithmic entropy and entropy in statistical mechanicsNEWLINEare discussed by several authors [\textit{C. H. Bennett} et al., IEEE Trans. Inf. Theory 44, No. 4, 1407--1423 (1998; Zbl 0964.94010); \textit{G. J. Chaitin}, J. Assoc. Comput. Mach. 22, 329--340 (1975; Zbl 0309.68045); \textit{E. Fredkin} and \textit{T. Toffoli}, Int. J. Theor. Phys. 21, 219--253 (1982; Zbl 0496.94015); \textit{A. N. Kolmogorov}, Select. Transl. Math. Stat. Probab. 7, 293--302 (1968; Zbl 0214.46902); \textit{A. K. Zvonkin} and \textit{L. A. Levin}, Russ. Math. Surv. 25, No. 6, 83--124 (1970); translation from Usp. Mat. Nauk 25, No. 6(156), 85--127 (1970; Zbl 0222.02027); \textit{R. J. Solomonoff}, Inform. and Control 7, 1--22 (1964; Zbl 0258.68045); ibid. 7, 224--254 (1964; Zbl 0259.68038); \textit{L. Szilard}, Z. f. Physik 53, 840--856 (1929; JFM 55.0488.06); \textit{K. Tadaki}, Math. Struct. Comput. Sci. 22, No. 5, 752--770 (2012; Zbl 1250.68136)]. The authors propose boldlyNEWLINEthat the former is a special case of the latter, which enables them to importNEWLINEthe basic techniques of thermodynamics into algorithmic information theory. InNEWLINEparticular, they claim that not only the length of the program (analogous toNEWLINEthe volume of the container) but also its output (analogous to the number ofNEWLINEmolecules in the gas) and the logarithm of its runtime (analogous to theNEWLINEenergy of a container of gas) should be regarded as important observables. AnNEWLINEanalogue of the basic thermodynamic relationNEWLINENEWLINE\[NEWLINEdE=TdS-PdV+\mu dNNEWLINE\]NEWLINENEWLINEis derived. The randomness described by Chaitin and Tadaki [loc. cit.]NEWLINEarises as the infinite-temperature limit.

Recommendations

• Algorithmic complexity and statistical mechanics
• The stochastic thermodynamics of computation
• Thermodynamics of computing: Entropy of nonergodic systems
• The statistical mechanics of constructive algorithms
• Computational proof as experiment: probabilistic algorithms from a thermodynamic perspective
• TOWARDS POSSIBLE NON-EXTENSIVE THERMODYNAMICS OF ALGORITHMIC PROCESSING — STATISTICAL MECHANICS OF INSERTION SORT ALGORITHM
• Algorithmic information theory and its statistical mechanical interpretation
• Maxwell's demon and the thermodynamics of computation
• Algorithmic information and simplicity in statistical physics

Cites work

• A formal theory of inductive inference. Part I
• A generalization of Chaitin's halting probability \(\Omega\) and halting self-similar sets
• A Theory of Program Size Formally Identical to Information Theory
• Algorithmic entropy of sets
• An introduction to Kolmogorov complexity and its applications
• Conservative logic
• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 1911266 (Why is no real title available?)
• Information distance
• Information Theory and Statistical Mechanics
• Most programs stop quickly or never halt
• Natural halting probabilities, partial randomness, and zeta functions
• On Information and Sufficiency
• On partial randomness
• Probability Theory

Cited in

(15)

• Phase transition and strong predictability
• On the statistical thermodynamics of reversible communicating processes
• Algorithmic information theory and its statistical mechanical interpretation
• Algorithmic complexity and statistical mechanics
• Fixed Point Theorems on Partial Randomness
• Algorithmic Complexity and Thermodynamics of Fractal Growth Processes
• The universal algorithm
• The stochastic thermodynamics of computation
• The entropy of a thermodynamic graph
• A statistical mechanical interpretation of algorithmic information theory
• Physical Limits of Heat‐Bath Algorithmic Cooling
• Automated symbolic calculations in nonequilibrium thermodynamics
• TOWARDS POSSIBLE NON-EXTENSIVE THERMODYNAMICS OF ALGORITHMIC PROCESSING — STATISTICAL MECHANICS OF INSERTION SORT ALGORITHM
• Understanding the thermodynamics of computation: a pedagogical overview
• The insights of algorithmic entropy

This page was built for publication: Algorithmic thermodynamics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2919939)