Jump To Date
View By Semester
View By Series
Add An Event


Center for Astrophysics Research and Technologies Seminar Series Information

 

Events Calendar

Extending Landauer's Bound from Bit Erasure to Arbitrary Computation

Thursday November 10, 2016
3:30 pm


 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

Disability Notice If you need an auxiliary aid or service to attend any Department of Physics and Astronomy event, please contact the department (phone: 505 277-2616; email: physics@unm.edu) as far in advance as possible to ensure you are accommodated.