Algorithmic thermodynamics

Posted in Uncategorized by Mike Stay on 2010 February 22

John Baez and I just wrote a paper entitled “Algorithmic Thermodynamics.” Li and Vitányi coined this phrase for their study of the Kolmogorov complexity of physical microstates; in their model, given an encoding $x$ of a macrostate (a measurement of a set of observables of the system to some accuracy), the entropy $S(x)$ of the system is a sum of two parts, the algorithmic entropy $K(x)$ and the uncertainty entropy $H(x)$ . The algorithmic entropy is roughly the length of the shortest program producing $x$ , while the uncertainy is a measure of how many microstates there are that satisfy the description $x$ . So roughly the microstates in their model are outputs of Turing machines.

In our model, microstates are inputs to Turing machines, specifically inputs that cause the machine to halt and give an output. Then we specify a macrostate using some observables of the program (computable functions from bit strings to real numbers, like the length, or runtime, or output of the program). Once we’ve specified the macrostate by giving the average values $\overline{C_i}$ of some observables $C_i,$ we can ask what distribution on microstates (halting programs) maximizes the entropy; this will be a Gibbs distribution

$\displaystyle p(x) = \frac{1}{Z} \exp\left(-\sum_i \beta_i C_i(x)\right),$

where

$\displaystyle Z = \sum_{x \in X} \exp\left(-\sum_i \beta_i C_i(x)\right)$

and

$\displaystyle -\frac{\partial}{\partial \beta_i} \ln Z = \overline{C_i}.$

The entropy of this system is

$\displaystyle S(p) = -\sum_{x \in X} p(x) \ln p(x);$

from this formula we can derive definitions of the conjugates of the observables, just like in statistical mechanics.

If we pick some observable $C_j$ —say, the runtime of the program—to play the role of the energy $E,$ then its conjugate $\beta_j$ plays the role of inverse temperature $1/T:$

$\displaystyle \frac{1}{T} = \left.\frac{\partial S}{\partial E}\right|_{C_{i \ne j}}.$

Given observables to play the roles of volume and number of particles—say, the length and output, respectively—we can similarly define analogs of pressure and chemical potential. Given these, we can think about thermodynamic cycles like those that power heat engines, or study the analogs to Maxwell’s relations, or study chemical reactions–all referring to programs instead of pistons.

And since the observables are arbitrary computable functions of the program bit string, we can actually recover Li and Vitányi’s meaning for ‘algorithmic thermodynamics’ by interpreting the output as a description of a physical macrostate; so our use of the term includes theirs as a special case.

reperiendi