{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:28:51Z","timestamp":1787509731084,"version":"build-2736575974"},"reference-count":29,"publisher":"Oxford University Press (OUP)","issue":"4","license":[{"start":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T00:00:00Z","timestamp":1776297600000},"content-version":"vor","delay-in-days":15,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Nuclear Security Administration of the United States Department of Energy at Los Alamos National Laboratory","award":["DE-AC52-06NA25396"],"award-info":[{"award-number":["DE-AC52-06NA25396"]}]},{"name":"DOE LDRD","award":["20240245ER"],"award-info":[{"award-number":["20240245ER"]}]},{"DOI":"10.13039\/100000001","name":"US NSF","doi-asserted-by":"publisher","award":["CCF-2221345"],"award-info":[{"award-number":["CCF-2221345"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Santa Fe Institute for support"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026,4,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Mismatch cost (MMC) is a universally applicable lower bound on the entropy production (EP) of any fixed physical process across a given time interval. In the first part of the article, we establish results concerning MMC to prove that it scales at least linearly with the total heat flow in the worst case over initial distributions. We also prove that the MMC lower bound over a given time interval never decreases if the time interval is subdivided into a sequence of subintervals, and that the bound often increases. In the second part of the article, we introduce a general framework for computing the minimal EP (ie the MMC) associated with running a computer program on any physical system that implements a modern digital computer. We apply this general framework to compare MMC of running two canonical sorting algorithms, bubble sort and bucket sort. The framework enables us to investigate how thermodynamic cost depends on features like input size and structure (eg with or without repeated entries). Finally, we extend the framework to programs that call subroutines.<\/jats:p>","DOI":"10.1093\/pnasnexus\/pgag116","type":"journal-article","created":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T05:57:12Z","timestamp":1776319032000},"source":"Crossref","is-referenced-by-count":1,"title":["Entropy production bounds for systems running computer programs"],"prefix":"10.1093","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-0145-2349","authenticated-orcid":false,"given":"Abhishek","family":"Yadav","sequence":"first","affiliation":[{"name":"Santa Fe Institute , 1399 Hyde Park Road, Santa Fe, NM 87501 ,","place":["USA"]},{"name":"Department of Physical Sciences, IISER Kolkata , Mohanpur 741246 ,","place":["India"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7964-3030","authenticated-orcid":false,"given":"Francesco","family":"Caravelli","sequence":"additional","affiliation":[{"name":"Theoretical Division (T-4), Los Alamos National Laboratory , Los Alamos, NM 87545 ,","place":["USA"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3105-2869","authenticated-orcid":false,"given":"David","family":"Wolpert","sequence":"additional","affiliation":[{"name":"Santa Fe Institute , 1399 Hyde Park Road, Santa Fe, NM 87501 ,","place":["USA"]},{"name":"Complexity Science Hub , Vienna 1030 ,","place":["Austria"]},{"name":"Center for Bio-social Complex Systems, Arizona State University , Tempe, AZ 85281 ,","place":["USA"]},{"name":"International Center for Theoretical Physics , Trieste 34151 ,","place":["Italy"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2026,4,16]]},"reference":[{"key":"2026042213091439600_pgag116-B1","first-page":"5","article-title":"On computable numbers, with an application to the entscheidungsproblem","volume":"58","author":"Turing","year":"1936","journal-title":"J Math"},{"key":"2026042213091439600_pgag116-B2","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1002\/bs.3830090402","article-title":"On the decrease of entropy in a thermodynamic system by the intervention of intelligent beings","volume":"9","author":"Szilard","year":"1964","journal-title":"Behav Sci"},{"key":"2026042213091439600_pgag116-B3","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1147\/rd.53.0183","article-title":"Irreversibility and heat generation in the computing process","volume":"5","author":"Landauer","year":"1961","journal-title":"IBM J Res Dev"},{"key":"2026042213091439600_pgag116-B4","doi-asserted-by":"crossref","first-page":"905","DOI":"10.1007\/BF02084158","article-title":"The thermodynamics of computation\u2014a review","volume":"21","author":"Bennett","year":"1982","journal-title":"Int J Theor Phys (Dordr)"},{"key":"2026042213091439600_pgag116-B5","doi-asserted-by":"crossref","first-page":"P03025","DOI":"10.1088\/1742-5468\/2014\/03\/P03025","article-title":"Thermodynamic and logical reversibilities revisited","volume":"2014","author":"Sagawa","year":"2014","journal-title":"J Stat Mech"},{"key":"2026042213091439600_pgag116-B6","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1016\/j.physa.2014.04.035","article-title":"Ensemble and trajectory thermodynamics: a brief introduction","volume":"418","author":"Van den Broeck","year":"2015","journal-title":"Physica A"},{"key":"2026042213091439600_pgag116-B7","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1109\/TC.2011.40","article-title":"Modeling energy-time trade-offs in VLSI computation","volume":"61","author":"Bingham","year":"2011","journal-title":"IEEE Trans Comput"},{"key":"2026042213091439600_pgag116-B8","author":"Tyagi","year":"2016"},{"key":"2026042213091439600_pgag116-B9","doi-asserted-by":"crossref","first-page":"126001","DOI":"10.1088\/0034-4885\/75\/12\/126001","article-title":"Stochastic thermodynamics, fluctuation theorems and molecular machines","volume":"75","author":"Seifert","year":"2012","journal-title":"Rep Prog Phys"},{"key":"2026042213091439600_pgag116-B10","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1038\/nphys3230","article-title":"Thermodynamics of information","volume":"11","author":"Parrondo","year":"2015","journal-title":"Nat Phys"},{"key":"2026042213091439600_pgag116-B11","doi-asserted-by":"crossref","first-page":"193001","DOI":"10.1088\/1751-8121\/ab0850","article-title":"The stochastic thermodynamics of computation","volume":"52","author":"Wolpert","year":"2019","journal-title":"J Phys A Math Theor"},{"key":"2026042213091439600_pgag116-B12","doi-asserted-by":"crossref","first-page":"e2321112121","DOI":"10.1073\/pnas.2321112121","article-title":"Is stochastic thermodynamics the key to understanding the energy costs of computation?","volume":"121","author":"Wolpert","year":"2024","journal-title":"Proc Natl Acad Sci U S A"},{"key":"2026042213091439600_pgag116-B13","doi-asserted-by":"crossref","first-page":"083202","DOI":"10.1088\/1742-5468\/aa7ee1","article-title":"Dependence of dissipation on the initial distribution over states","volume":"2017","author":"Kolchinsky","year":"2017","journal-title":"J Stat Mech"},{"key":"2026042213091439600_pgag116-B14","doi-asserted-by":"crossref","first-page":"054107","DOI":"10.1103\/PhysRevE.104.054107","article-title":"Dependence of integrated, instantaneous, and fluctuating entropy production on the initial state in quantum and classical processes","volume":"104","author":"Kolchinsky","year":"2021","journal-title":"Phys Rev E"},{"key":"2026042213091439600_pgag116-B15","doi-asserted-by":"crossref","first-page":"063047","DOI":"10.1088\/1367-2630\/ab82b8","article-title":"Thermodynamics of computing with circuits","volume":"22","author":"Wolpert","year":"2020","journal-title":"New J Phys"},{"issue":"(4)","key":"2026042213091439600_pgag116-B16","doi-asserted-by":"crossref","first-page":"043324","DOI":"10.1103\/qvc2-32xr","article-title":"Minimal thermodynamic cost of communication","volume":"7","author":"Yadav","year":"2025","journal-title":"Phys Rev Res"},{"key":"2026042213091439600_pgag116-B17","author":"Yadav","year":"2025"},{"key":"2026042213091439600_pgag116-B18","doi-asserted-by":"crossref","first-page":"011143","DOI":"10.1103\/PhysRevE.82.011143","article-title":"Three faces of the second law. I. Master equation formulation","volume":"82","author":"Esposito","year":"2010","journal-title":"Phys Rev E"},{"key":"2026042213091439600_pgag116-B19","doi-asserted-by":"crossref","first-page":"91","DOI":"10.3390\/e27010091","article-title":"Maximizing free energy gain","volume":"27","author":"Kolchinsky","year":"2025","journal-title":"Entropy"},{"key":"2026042213091439600_pgag116-B20","doi-asserted-by":"crossref","first-page":"4580","DOI":"10.1103\/PhysRevE.52.4580","article-title":"Fisher information and bounds to the entropy increase","volume":"52","author":"Plastino","year":"1995","journal-title":"Phys Rev E"},{"key":"2026042213091439600_pgag116-B21","doi-asserted-by":"crossref","first-page":"158101","DOI":"10.1103\/PhysRevLett.114.158101","article-title":"Thermodynamic uncertainty relation for biomolecular processes","volume":"114","author":"Barato","year":"2015","journal-title":"Phys Rev Lett"},{"key":"2026042213091439600_pgag116-B22","doi-asserted-by":"crossref","first-page":"120601","DOI":"10.1103\/PhysRevLett.116.120601","article-title":"Dissipation bounds all steady-state current fluctuations","volume":"116","author":"Gingrich","year":"2016","journal-title":"Phys Rev Lett"},{"key":"2026042213091439600_pgag116-B23","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1038\/s41567-019-0702-6","article-title":"Thermodynamic uncertainty relations constrain non-equilibrium fluctuations","volume":"16","author":"Horowitz","year":"2020","journal-title":"Nat Phys"},{"key":"2026042213091439600_pgag116-B24","doi-asserted-by":"crossref","first-page":"070601","DOI":"10.1103\/PhysRevLett.121.070601","article-title":"Speed limit for classical stochastic processes","volume":"121","author":"Shiraishi","year":"2018","journal-title":"Phys Rev Lett"},{"key":"2026042213091439600_pgag116-B25","doi-asserted-by":"crossref","first-page":"062132","DOI":"10.1103\/PhysRevE.102.062132","article-title":"Unified approach to classical speed limit and thermodynamic uncertainty relation","volume":"102","author":"Tuan Vo","year":"2020","journal-title":"Phys Rev E"},{"key":"2026042213091439600_pgag116-B26","doi-asserted-by":"crossref","first-page":"123013","DOI":"10.1088\/1367-2630\/ad1070","article-title":"Thermodynamics of deterministic finite automata operating locally and periodically","volume":"25","author":"Ouldridge","year":"2023","journal-title":"New J Phys"},{"key":"2026042213091439600_pgag116-B27","doi-asserted-by":"crossref","first-page":"033312","DOI":"10.1103\/PhysRevResearch.2.033312","article-title":"Thermodynamic costs of Turing machines","volume":"2","author":"Kolchinsky","year":"2020","journal-title":"Phys Rev Res"},{"key":"2026042213091439600_pgag116-B28","author":"Polyanskiy","year":"2014"},{"key":"2026042213091439600_pgag116-B29","doi-asserted-by":"crossref","first-page":"073008","DOI":"10.1088\/1367-2630\/11\/7\/073008","article-title":"Entropy production and the arrow of time","volume":"11","author":"Parrondo","year":"2009","journal-title":"New J Phys"}],"container-title":["PNAS Nexus"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/pnasnexus\/advance-article-pdf\/doi\/10.1093\/pnasnexus\/pgag116\/68088976\/pgag116.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/pnasnexus\/article-pdf\/5\/4\/pgag116\/68088976\/pgag116.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/pnasnexus\/article-pdf\/5\/4\/pgag116\/68088976\/pgag116.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T17:09:26Z","timestamp":1776877766000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/pnasnexus\/article\/doi\/10.1093\/pnasnexus\/pgag116\/8654698"}},"subtitle":[],"editor":[{"given":"Derek","family":"Abbott","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2026,4]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2026,4,7]]}},"URL":"https:\/\/doi.org\/10.1093\/pnasnexus\/pgag116","relation":{},"ISSN":["2752-6542"],"issn-type":[{"value":"2752-6542","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2026,4]]},"published":{"date-parts":[[2026,4]]},"article-number":"pgag116"}}