 |
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