Stochastic thermodynamics of Boolean circuits, finite automata and Turing machines

  • IFISC Colloquium

  • David Wolpert
  • Santa Fe Institute, International Center for Theoretical Physics, Complexity Science Hub, and Arizona State University
  • June 15, 2023, 2:30 p.m.
  • IFISC Seminar Room
  • Sync with iCal
  • Announcement file

David Wolpert is a professor at the Santa Fe Institute and adjunct professor at Arizona State University. He is also affiliated with the ICTP in Trieste as a Research Staff Associate as well as the IAS in Princeton as an External Affiliate. His degrees in physics are from Princeton and the University of California.

Before his current position he was the Ulam scholar at the Center for Nonlinear Studies, and before that at NASA Ames Research Center and a consulting professor at Stanford University, where he formed the Collective Intelligence group. He has worked at IBM and a data mining start-up, and is external faculty at numerous international institutions.

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:


Contact details:

Tobias Galla

Contact form

This web uses cookies for data collection with a statistical purpose. If you continue browsing, it means acceptance of the installation of the same.

More info I agree