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&nbsp;minimal &quot;resource costs&quot; needed to perform a given computation&nbsp;on a given type of computer. In the real world, some of the most important resource costs of performing a computation are&nbsp;thermodynamic, e.g., the amount of heat it produces. In this&nbsp;talk I will summarize recent results on how thermodynamic resource costs depend on the computation being performed and the computer&nbsp;being used to perform them.</p> <p>I will start&nbsp;with&nbsp;some&nbsp;new&nbsp;results&nbsp;concerning&nbsp;the&nbsp;thermodynamic&nbsp;costs&nbsp;of&nbsp;performing&nbsp;a&nbsp;given&nbsp;computation in a (loop-free and branch-free) digital circuit.&nbsp;Next I will summarize some results concerning deterministic finite automata (DFA). After that I will review results on how considering the&nbsp;minimal entropy&nbsp;production (EP) of computing a desired output on a TM,&nbsp;rather than the minimal size of an input string that causes the&nbsp;TM&nbsp;to produce that output (i.e., the output&#39;s Kolmogorov complexity), results&nbsp;in a correction term to Kolmogorov complexity. I will end by&nbsp;describing the vast new set of research issues at the intersection of&nbsp;stochastic thermodynamics and computer science theory, issues that&nbsp;expand both fields.</p> <p>Presential in the seminar room, and Zoom stream at&nbsp;https:</p> <p>//zoom.us/j/98286706234?pwd=bm1JUFVYcTJkaVl1VU55L0FiWDRIUT09</p> Url event:https://ifisc.uib-csic.es/en/events/seminars/stochastic-thermodynamics-of-bo...