Irreversibility and dissipation in finite-state automata |
| |
Authors: | Natesh Ganesh Neal G Anderson |
| |
Institution: | Department of Electrical and Computer Engineering, University of Massachusetts Amherst, Amherst, MA 01003-9292, USA |
| |
Abstract: | Irreversibility and dissipation in finite-state automata (FSA) are considered from a physical-information-theoretic perspective. A quantitative measure for the computational irreversibility of finite automata is introduced, and a fundamental lower bound on the average energy dissipated per state transition is obtained and expressed in terms of FSA irreversibility. The irreversibility measure and energy bound are germane to any realization of a deterministic automaton that faithfully registers abstract FSA states in distinguishable states of a physical system coupled to a thermal environment, and that evolves via a sequence of interactions with an external system holding a physical instantiation of a random input string. The central result, which is shown to follow from quantum dynamics and entropic inequalities alone, can be regarded as a generalization of Landauer?s Principle applicable to FSAs and tailorable to specified automata. Application to a simple FSA is illustrated. |
| |
Keywords: | Automata Dissipation Landauer?s Principle Logical irreversibility Physical information Thermodynamics of computation |
本文献已被 ScienceDirect 等数据库收录! |