A thermodynamically consistent model of finite-state machines

被引：4

作者：

Chu, Dominique ^{[1
]}

Spinney, Richard E. ^{[2
]}

机构：

[1] Univ Kent, Sch Comp, Canterbury CT2 7NF, Kent, England

[2] Univ Sydney, Ctr Complex Syst, Sydney, NSW 2006, Australia

来源：

INTERFACE FOCUS | 2018年 / 8卷 / 06期

关键词：

stochastic thermodynamics; models of computation; entropy; information processing; COMPUTATION; SYSTEMS;

D O I：

10.1098/rsfs.2018.0037

中图分类号：

Q [生物科学];

学科分类号：

07 ; 0710 ; 09 ;

摘要：

Finite-state machines (FSMs) are a theoretically and practically important model of computation. We propose a general, thermodynamically consistent model of FSMs and characterize the resource requirements of these machines. We model FSMs as time-inhomogeneous Markov chains. The computation is driven by instantaneous manipulations of the energy levels of the states. We calculate the entropy production of the machine, its error probability, and the time required to complete one update step. We find that a sequence of generalized bit-setting operations is sufficient to implement any FSM.

引用

页数：9

共 50 条

[1] Model matching for finite-state machines
Di Benedetto, MD
Sangiovanni-Vincentelli, A
Villa, T
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2001, 46 (11) : 1726 - 1743
[2] Model reduction of finite-state machines by contraction
Giua, A
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2001, 46 (05) : 797 - 801
[3] IN FINITE-STATE MACHINES, LIVING MACHINES
KRUGER, T
ARCHITECTURAL DESIGN, 1994, (111) : R14 - R15
[4] Periodic finite-state machines
Kopetz, H.
El-Salloum, C.
Huber, B.
Obermaisser, R.
10TH IEEE INTERNATIONAL SYMPOSIUM ON OBJECT AND COMPONENT-ORIENTED REAL-TIME DISTRIBUTED COMPUTING, PROCEEDINGS, 2007, : 10 - +
[5] ON COMMUNICATING FINITE-STATE MACHINES
BRAND, D
ZAFIROPULO, P
JOURNAL OF THE ACM, 1983, 30 (02) : 323 - 342
[6] State assignment of finite-state machines
Ahmad, I
Dhodhi, MK
IEE PROCEEDINGS-COMPUTERS AND DIGITAL TECHNIQUES, 2000, 147 (01): : 15 - 22
[7] Robots and finite-state machines
Carter, EF
DR DOBBS JOURNAL, 1997, 22 (02): : 50 - +
[8] Refinement of finite-state machines
Li, HW
Min, YH
Li, ZC
CAD/GRAPHICS '2001: PROCEEDINGS OF THE SEVENTH INTERNATIONAL CONFERENCE ON COMPUTER AIDED DESIGN AND COMPUTER GRAPHICS, VOLS 1 AND 2, 2001, : 624 - 629
[9] The state reduction of nondeterministic finite-state machines
Damiani, M
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1997, 16 (11) : 1278 - 1291
[10] Model Checking of Transition-Labeled Finite-State Machines
Estivill-Castro, Vladimir
Rosenblueth, David A.
SOFTWARE ENGINEERING, BUSINESS CONTINUITY, AND EDUCATION, 2011, 257 : 61 - +

← 1 2 3 4 5 →