Thermodynamics of stochastic Turing machines

In analogy to Brownian computers we explicitly show how to construct stochastic models which mimic the behavior of a general-purpose computer (a Turing machine). Our models are discrete state systems obeying a Markovian master equation, which are logically reversible and have a well-defined and consistent thermodynamic interpretation. The resulting master equation, which describes a simple one-step process on an enormously large state space, allows us to thoroughly investigate the thermodynamics of computation for this situation. Especially in the stationary regime we can well approximate the master equation by a simple Fokker-Planck equation in one dimension. We then show that the entropy production rate at steady state can be made arbitrarily small, but the total (integrated) entropy production is finite and grows logarithmically with the number of computational steps.

Figure 1

Simple sketch of a TM: The machine, specified by a state $q$, has access to an infinite tape, which is divided into equal squares. The machine scans with its head always only on one square on the tape, on which it finds a symbol $s$ (which might be also the blank symbol $b$) written.

Figure 2

Sketch of the general setup, which allows us to analyze any abstract computational process in terms of thermodynamic quantities. The upper tape corresponds to the output tape, which is initially blank, and the lower tape corresponds to the input tape. Note that we will always assume that blank tapes are for free, i.e., the machine can have as many blank space on which it can write as it requires. Furthermore, the machine itself has access to two additional internal tapes (not sketched), see Sec. 3b.

Figure 3

A computational path is defined by the way the machine proceeds from state to state through a high-dimensional state space (each state of the machine including the tapes is symbolized by a black circle). Here we sketched two different paths (solid red and dashed blue lines). For standard machines (which compute only from left to right) each path is uniquely determined by the input signal string and the initial machine state. For a logically irreversible machine, however, it might happen that two different paths merge at some point (as shown on top), making it impossible to find the inverse of a state in general (that is to say, there is a unique way to go from left to right in the diagram but not from right to left). In contrast, this cannot happen for logically reversible machines (as shown in the middle), but this feature comes at the cost of introducing additional states and tapes making the state space even larger. Finally, whereas the standard logically reversible TM still proceeds deterministically from left to right, a stochastic TM jumps randomly according to some rates [e.g., $W_{n+1,n}$ and $W_{n,n+1}$ as used in Eqs. (6) and (8)] and, hence, it can move both ways (bottom).