IFISC Colloquium on Thursday Jun 15, 2023 at 14:30 Place: IFISC Seminar Room Title: Stochastic thermodynamics of Boolean circuits, finite automata and Turing machines Speaker: David Wolpert, Santa Fe Institute, International Center for Theoretical Physics, Complexity Science Hub, and Arizona State University Abstract: <p>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.</p> <p>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.</p> <p>Presential in the seminar room, and Zoom stream at https://zoom.us/j/98286706234?pwd=bm1JUFVYcTJkaVl1VU55L0FiWDRIUT09</p>; Url event:https://ifisc.uib-csic.es/en/events/seminars/stochastic-thermodynamics-of-bo...