 |
Center for Nonlinear Studies |
Recent advances in nonequilibrium statistical physics have led to great strides in the thermodynamics of computation, allowing the calculation of the minimal thermodynamic work required to implement a computation π when two conditions hold: i) The output of π is independent of its input (e.g., as in bit erasure); ii) We use a physical computer C to implement π that is tailored to the precise distribution over π 's inputs, P0. First I extend these analyses to calculate the minimal work required even if the output of π depends on its input. I then show that stochastic uncertainty about P0 increases the minimal work required to run the computer. Next I show that if C will be re-used, then the minimal work to run it depends only on the logical map π , independent of the physical details of C. This establishes a formal identity between the thermodynamics of (re-usable) computers and theoretical computer science. I use this identity to prove that the minimal work required to compute a bit string π on a universal Turing machine U is Kolmogorov complexityU(π) + log (Bernoulli measure of the set of input strings that compute π) + log(halting probability of U) This can be viewed as a thermodynamic βcorrectionβ to Kolmogorov complexity. I end by using these results to relate the free energy flux incident on an organism / robot / biosphere to the maximal amount of computation that the organism / robot / biosphere can do per unit time.
Host: Sebastian Deffner