Events Calendar
Extending Landauer's Bound from Bit Erasure to Arbitrary Computation
Thursday November 10, 2016
3:30 pm
Tweet |
Presenter: | David Wolpert, Santa Fe Institute, MIT, ASU |
---|---|---|
Series: | CQuIC Seminars | |
Abstract: |
Recent revolutionary advances in nonequilibrium statistical physics have shown how to calculate the minimal free energy needed to implement a computation π when:
i) The output of π is independent of its input (e.g., as in bit erasure); ii) The physical computer C that implements π is tailored to the precise distribution over π's inputs, P0. I extend these analyses to calculate the free energy needed where the output of π depends on its input. I then show that stochastic uncertainty about P0 increases the minimal free energy required to run any computer. This is a completely new kind of law of thermodynamics, concerning changes to the input distribution to a process rather than changes to that process. I discuss the ramifications of these results for evolutionary biology, by quantifying the tradeoff between the free energy needed by a biological organism to perform a computation and the fitness benefits of that computation. I end by proving 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. |
|
Host: | Carlton Caves | |
Location: | PAIS-2540, PAIS | |