Algorithmic thermodynamics
From MaRDI portal
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.
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)
