Joint ICTP-SISSA Seminar: Stochastic thermodynamics of Boolean circuits, finite automata and Turing machines
Starts 6 Jun 2023 14:00
Ends 6 Jun 2023 15:00
Central European Time
SISSA via Bonomea 265, Room 131
Via Bonomea, 265
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 ofstochastic thermodynamics and computer science theory, issues that expand both fields.