Thermodynamics of quasideterministic digital computers

A central result of stochastic thermodynamics is that irreversible state transitions of Markovian systems entail a cost in terms of an infinite entropy production. A corollary of this is that strictly deterministic computation is not possible. Using a thermodynamically consistent model, we show that quasideterministic computation can be achieved at finite, and indeed modest cost with accuracies that are indistinguishable from deterministic behavior for all practical purposes. Concretely, we consider the entropy production of stochastic (Markovian) systems that behave like and and a not gates. Combinations of these gates can implement any logical function. We require that these gates return the correct result with a probability that is very close to 1, and additionally, that they do so within finite time. The central component of the model is a machine that can read and write binary tapes. We find that the error probability of the computation of these gates falls with the power of the system size, whereas the cost only increases linearly with the system size.

Figure 1

The reading machine. The input to the machine is a tape of length $L$ consisting of $m$ symbols “1”. The machine has $N+1$ internal states and a display that represents the output tape of length 1.

Figure 2

The steady-state probability to find the machine $R$ in state $T_2=1$ as a function of $\epsilon$, the proportion of 1s on the input tape of length $L=100$. The sigmoidal shape of the graph means that for reasonably low or high values of $\epsilon$ the machine outputs 0 and 1 with a probability of almost 1, respectively.

Figure 3

Accuracy of the and gate. The graph shows the $max(p_{\wedge }^{11}\left(i\right),p_{\wedge }^{01}\left(i\right))$ for various values of $\epsilon$ and $N=80$. The threshold $\mathrm{\Theta }$ ideally coincides with a minimum. The probability associated with the minimum also defines the accuracy that can be achieved for the computation.