Algorithmic thermodynamics (Q2919939)

The analogy between algorithmic entropy and entropy in statistical mechanicsNEWLINEare discussed by several authors [\textit{C. H. Bennett} et al., IEEE Trans. Inf. Theory 44, No. 4, 1407--1423 (1998; Zbl 0964.94010); \textit{G. J. Chaitin}, J. Assoc. Comput. Mach. 22, 329--340 (1975; Zbl 0309.68045); \textit{E. Fredkin} and \textit{T. Toffoli}, Int. J. Theor. Phys. 21, 219--253 (1982; Zbl 0496.94015); \textit{A. N. Kolmogorov}, Select. Transl. Math. Stat. Probab. 7, 293--302 (1968; Zbl 0214.46902); \textit{A. K. Zvonkin} and \textit{L. A. Levin}, Russ. Math. Surv. 25, No. 6, 83--124 (1970); translation from Usp. Mat. Nauk 25, No. 6(156), 85--127 (1970; Zbl 0222.02027); \textit{R. J. Solomonoff}, Inform. and Control 7, 1--22 (1964; Zbl 0258.68045); ibid. 7, 224--254 (1964; Zbl 0259.68038); \textit{L. Szilard}, Z. f. Physik 53, 840--856 (1929; JFM 55.0488.06); \textit{K. Tadaki}, Math. Struct. Comput. Sci. 22, No. 5, 752--770 (2012; Zbl 1250.68136)]. The authors propose boldlyNEWLINEthat the former is a special case of the latter, which enables them to importNEWLINEthe basic techniques of thermodynamics into algorithmic information theory. InNEWLINEparticular, they claim that not only the length of the program (analogous toNEWLINEthe volume of the container) but also its output (analogous to the number ofNEWLINEmolecules in the gas) and the logarithm of its runtime (analogous to theNEWLINEenergy of a container of gas) should be regarded as important observables. AnNEWLINEanalogue of the basic thermodynamic relationNEWLINENEWLINE\[NEWLINEdE=TdS-PdV+\mu dNNEWLINE\]NEWLINENEWLINEis derived. The randomness described by Chaitin and Tadaki [loc. cit.]NEWLINEarises as the infinite-temperature limit.