Starts 6 Jun 2023 14:00
Ends 6 Jun 2023 15:00
Central European Time
Joint ICTP-SISSA Seminar: Stochastic thermodynamics of Boolean circuits, finite automata and Turing machines
SISSA
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.