The central concern of computational complexity theory is the minimal "resource costs" needed to perform a given computation on a given type of computer. In the real world, some of the most important resource costs of performing a computation are thermodynamic, e.g., the amount of heat it produces. In this talk I will summarize recent results on how thermodynamic resource costs depend on the computation being performed and the computer being used to perform them.
I will start with some new results concerning the thermodynamic costs of performing a given computation in a (loop-free and branch-free) digital circuit. Next I will summarize some results concerning deterministic finite automata (DFA). After that I will review results on how considering the minimal entropy production (EP) of computing a desired output on a TM, rather than the minimal size of an input string that causes the TM to produce that output (i.e., the output's Kolmogorov complexity), results in a correction term to Kolmogorov complexity. I will end by describing the vast new set of research issues at the intersection of stochastic thermodynamics and computer science theory, issues that expand both fields.
Presential in the seminar room, and Zoom stream at https://zoom.us/j/98286706234?pwd=bm1JUFVYcTJkaVl1VU55L0FiWDRIUT09
