Uncomputability, Intractability and the Efficiency of Heat Engines

Summary

Abstract

We consider heat engines that take both energy and information from their environment. To operate in the most efficient fashion, such engines must compress the information that they take in to its most concise form. But the most concise form to which a piece of information can be compressed is an uncomputable function of that information. Hence there is no way for such an engine systematically to achieve its maximum efficiency.

Heat engines take heat from their environment and turn it into work. We consider here engines that gather both heat and information and turn them into work. An example of such an engine is the Szilard engine, a one-molecule heat engine that turns information into work. Practical examples include engines that run off of fluctuations, and car engines that use microprocessors to achieve greater efficiency.

For an ordinary heat engine a Carnot cycle can in principle be carried out reversibly. Following a suggestion of Zurek, we show that engines that process both heat and information cannot attain the Carnot efficiency even in principle. We prove that to operate at the maximum efficiency over a cycle, such an engine must reversibly compress the information that it has acquired to its most compact form. But Gödel's theorem implies that the most compact form to which a given piece of information can be compressed is an uncomputable function of that information. Accordingly, there is no systematic way for an engine to achieve its maximum efficiency.