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
  • 15 de juny de 2023 a les 14:30
  • 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:


Detalls de contacte:

Tobias Galla

Contact form

Aquesta web utilitza cookies per a la recollida de dades amb un propòsit estadístic. Si continues navegant, vol dir que acceptes la instal·lació de la cookie.

Més informació D'accord