«Found Phys (2013) 43:1384–1410 DOI 10.1007/s10701-013-9753-1 Brownian Computation Is Thermodynamically Irreversible John D. Norton Received: 21 June ...»
Found Phys (2013) 43:1384–1410
Brownian Computation Is Thermodynamically
John D. Norton
Received: 21 June 2013 / Accepted: 28 September 2013 / Published online: 17 October 2013
© Springer Science+Business Media New York 2013
Brownian computers are supposed to illustrate how logically reversible
mathematical operations can be computed by physical processes that are thermodynamically reversible or nearly so. In fact, they are thermodynamically irreversible processes that are the analog of an uncontrolled expansion of a gas into a vacuum.
Keywords Brownian computation · Entropy · Fluctuations · Thermodynamics of computation 1 Introduction The thermodynamics of computation applies ideas from thermal and statistical physics to physical devices implementing computations. Its major focus has been to characterize the principled limits to thermal dissipation in these devices. The best case of no dissipation arises when we use processes that create no thermodynamic entropy. They are thermodynamically reversible processes in which all driving forces are in perfect balance.
Thermal ﬂuctuations, such as arise through random molecular motions, are not normally a major consideration in thermodynamic analyses. However, they become decisive in the thermodynamics of computation. For the thermodynamic dissipation associated with thermodynamically irreversible processes is minimized by reducing the computational devices to the smallest scales possible, that is, to molecular scales.
I thank Laszlo Kish for helpful discussion.
J.D. Norton (B) Department of History and Philosophy of Science, Center for Philosophy of Science, University of Pittsburgh, Pittsburgh PA 15260, USA e-mail: email@example.com url: http://www.pitt.edu~jdnorton Found Phys (2013) 43:1384–1410 1385 Thermal ﬂuctuations now become a major obstacle to reducing thermodynamic dissipation. Consider a thermodynamic process, such as a single step of computation in a physical computer, at these molecular scales. In order to proceed to completion, it must overcome these ﬂuctuations. The problem is serious. It is the essential idea behind a “no go” result described elsewhere (Norton , Sect. 7.4; ; , Part II). If the process is to proceed to completion with reasonable probability, it follows quite generally that it must create thermodynamic entropy in excess of k ln 2 per step.
This quantity of entropy, k ln 2, is the minimum amount associated by Landauer’s principle with the erasure of one bit of information. If each step of a computation must create more thermodynamic entropy that this Landauer limit, then any debate over the cogency of the Landauer principle is rendered superﬂuous. Indeed we have to give up the idea that the minimum thermodynamic dissipation is determined by the logical speciﬁcation of the computation. For the minimum dissipation is ﬁxed by the number of discrete steps in the computational procedure used, which makes this minimum dependent on the implementation.
The no go result wreaks greatest harm when the computer proceeds with what I shall call a “discrete protocol” tacitly presumed above. It is the familiar protocol in which the computation is divided into a series of discrete steps, each of which must be completed before the next is initiated.
There is an escape from the no go result. Bennett [1, 2] and Bennett and Landauer  have described a most ingenious protocol for computation that minimizes its effects. In the protocol, called “Brownian” computation, the many logical steps of a complicated computation are collapsed into a single process thermodynamically. It is done by chaining the logical steps of the computation into a single process such that random thermal motions carry the computational device’s state back and forth over the steps in a way that is analogous to the Brownian motion of a pollen grain in water. No step is assuredly complete until the device happens to enter a ﬁnal, dissipative trap state from which it escapes with very low probability.
The no go result still applies to this new, indiscrete protocol, but now the thermodynamic entropy creation required is merely that required for one step. It can be negligible in the context of a large and complicated computation if that single step really is close to thermodynamic reversibility. That is the hope. However, it is not realized.
For all the mechanical and computational ingenuity of the devices, the thermodynamic analysis Bennett provides is erroneous. The devices are described as implementing thermodynamically reversible computations, or coming close to it, thereby demonstrating the possibility in principle of thermodynamically reversible computation. In fact the devices are thermodynamically irreversible. They implement processes that are the thermodynamic analog of an uncontrolled, irreversible expansion of a one-molecule gas, the popping of a balloon of gas into a vacuum.
Sections 2 and 3 below will describe the operation of a Brownian computer and give a thermodynamic analysis of it. The main result is that an n stage computation creates k ln n of thermodynamic entropy; and that extra thermodynamic entropy is created if a trap state is introduced to assure termination of the computation; or if an energy gradient is introduced to speed up the computation.
1386 Found Phys (2013) 43:1384–1410 Section 4 afﬁrms the main claim of this paper, that, contrary to the view in the literature, Brownian computation is thermodynamically irreversible. Section 5 reviews several ways that one might come to misidentify a thermodynamically irreversible process as reversible. The most important is the practice in the thermodynamics of computation of tracking energy instead of entropy in an effort to gauge which processes are thermodynamically reversible.
Finally, if a Brownian computer implements logically irreversible operations, its accessible phase space may become exponentially branched. This branching has been associated with Landauer’s principle of the necessity of an entropy cost of erasure.
In Sect. 6, it is argued that the connection is spurious and that Brownian computation can provide no support for the supposed minimum to the entropy cost. Brownian computation is powered by a thermodynamically irreversible creation of entropy and it creates thermodynamic entropy whether it is computing a logically reversible or a logically irreversible operation. It cannot tell us what the minimum dissipation must be if we were to try to carry out the same operations with thermodynamically reversible processes.
2 Brownian Computers
All bodies in thermal contact with their environment exhibit ﬂuctuations in their physical properties. They are indiscernible in macroscopic bodies. Fluctuation driven motions are visible through an optical microscope among tiny particles suspended in water. The botanist Robert Brown observed them in 1827 as the jiggling of pollen grains, but he did not explain them. In his year of miracles of 1905, Einstein accounted for the motions as thermal ﬂuctuations. When we proceed to still smaller molecular scales, these thermal motions become more important. In biological cells they can bring reagents into contact and are involved in the complicated chemistry of DNA and RNA. Bennett, sometimes in collaboration with Landauer [1, 2, 4], notes that the molecular structures involved with DNA and RNA are at a level of complexity that they could be used to build computing devices whose function would, in some measure, be dependent on the thermal motions of the reagents. They then develop and idealize the idea as the notion of a mechanical computing device powered by these random thermal motions. These are the Brownian computers.
To see how these thermal motions can have a directed effect, consider the simplest case of a small particle released in the leftmost portion a long channel, shown from overhead in Fig. 1. Random thermal motions will carry the particle back and forth in the familiar random walk. If a low energy trap is located at the rightmost end of the channel, the particle will eventually end up in it. It will remain there with high probability, if the trap is deep enough.
Bennett suggests that this sort of motion can drive forward a vastly more complicated contrivance of many mechanical parts that implements a Turing machine
Fig. 1 Brownian motion ofparticle in a channelFound Phys (2013) 43:1384–1410 1387
and hence carries out computations. It consists of many interlocked parts that can slide over one another. The continuing thermal jiggling of the parts leads the device to meander back and forth between the many states that comprise the steps of the computation.
The reader is urged to consult the works cited above for drawings and a more complete description of the implementation of the Brownian computer.
The computer must be assembled from rigid components that interlock and slide over one another. It consists of various shapes that can slide up and down from their reference position to function as memory storage devices; actuator rods that move them; rotating disks with grooves in them to move the actuators; and so on. No friction is allowed, since that would be thermodynamically dissipative; and no springs are allowed. A spring-loaded locking pin, for example, would fail to function. Once the spring drives the pin home, it would immediately bounce out because of the timereversible, non-dissipative dynamics assumed.
While Bennett’s accounts describe many essential parts of the Brownian computer, many more are not described. No doubt, a complete speciﬁcation of all the parts of the Brownian computer would be lengthy. However, without it, we must assume with Bennett that the device really can be constructed from the very limited repertoire of processes allowed. That is, the possibility of the device and thus the entire analysis remains an unproven conjecture. I will leave the matter open since there are demonstrable failures in the analysis to be elaborated below, even if the conjecture is granted.
For reasons that will be apparent later, Bennett mostly considers Brownian computations in which each computational state has a unique antecedent state. This condition is met if the device computes only logically reversible operations, such as NOT.
For then, if the present state of a memory cell is O, its antecedent state must have been 1; and vice versa. However the condition is not realized if the device computes logically irreversible operations, such as the erase function. For then, if the present state of a memory cell is the erasure value 0, its antecedent state may have been either a 0 or a 1.
That each state has a unique antecedent state requires that the whole device implement a vastly complicated system of interlockings, so that the entire device has only one degree freedom. The computation is carried out by the device meandering along this one degree of freedom. The effect of this requirement, as implemented by Bennett, has an important abstract expression. The position and orientation of each component of the massively complicated Brownian computer can be speciﬁed by their coordinates. The combination of them all produces a conﬁguration space of very high dimension. The limitation to a single degree of freedom results in the accessible portion of the conﬁguration space being a long, labyrinthine, one-dimensional channel with a slight thickness given by the free play of the components.
Figure 2 illustrates how this channel comes about in the simplest case of two components constrained to move together. The components are a bar and a plate with a diagonal slot cut into it. The bar has a pin ﬁxed to its midpoint and the pin engages with the slot in the plate. Without the pin, the two components would be able to slide independently with the two degrees of freedom labeled by x and y.
The conﬁnement of the pin to the slot constrains them to move together, reducing 1388 Found Phys (2013) 43:1384–1410
Fig. 2 Two components with a single common degree of freedom
the possible motions to a single degree of freedom. That single degree of freedom corresponds to the diagonal channel in their conﬁguration space shown at right.
The channel in the conﬁguration space of a Brownian computer would be vastly more complicated. It will end with a low energy trap analogous to the one shown in Fig. 1 so that the computation is completed with high probability.
Here is Bennett’s  brief summary:
In a Brownian computer, such as Bennett’s enzymatic computer, the interactions among the parts create an intricate but unbranched valley on the manybody potential-energy surface, isomorphic to the desired computation, down which the system passively diffuses, with a drift velocity proportional to the driving force.
The summary includes an unneeded complication. Bennett presumes that some slight energy gradient is needed to provide a driving force that will bring the computation towards its end state. In fact, as we shall see shortly, entropic forces are sufﬁcient, if slower.
3 Thermodynamic Analysis of Brownian Computers
Bennett and Landauer [1, 2, 4] report several results concerning the thermodynamic and stochastic properties of Brownian computers. They do not provide the computations needed to arrive at the results. They are, apparently, left as an exercise for the reader. In this section, I will do the exercise. As we shall see in this and the following sections, I am able to recover some of the results concerning probabilities. However the fundamental claim that the Brownian computer operates at or near thermodynamic reversibility will prove unsustainable.
3.1 Uncontrolled Expansion of a Single Molecule Gas
Fig. 3 Irreversible expansion of a one molecule gas tion in the ﬁrst cell of volume V of a long chamber of volume nV, as shown in Fig. 3.
The partition is removed and the gas expands irreversibly into the larger volume nV.
The Hamiltonian of the single molecule is given by
in the region of space accessible to the gas and inﬁnite elsewhere. Here p is a vector representing the momentum degrees of freedom of the molecule and π is some function of them, typically quadratic. The key point to note is that the Hamiltonian H is not a function of the spatial coordinates x = (x, y, z) of the molecule. This independence drives the results that follow. We assume that the x coordinate is aligned with the long axis of the chamber and that it has a cross-sectional area A.
At thermal equilibrium, the molecule’s position is Boltzmann distributed probabilistically over its phase space as
During the expansion, the mean energy of the gas remains constant and, since it does no work, no net heat is exchanged with the environment. Since the environment is unchanged, we have for its thermodynamic entropy change
We recover the same result from (3) and the canonical expression F = −kT ln Z.
The essential point for what follows is that this expansion is driven entirely by entropic forces. There is no energy gradient driving it; the internal energy E of the gas is the same at the start of the expansion, when it is conﬁned to volume V, as at the end, when it occupies a volume nV.
More generally, this sort of process is driven by an imbalance of a generalized thermodynamic force. For isothermal processes whose stages are parameterized by λ, the appropriate generalized force is
If we parameterize the states of the isothermally expanding one molecule gas by the
volume V (λ) = V λ, occupied at stage λ, then F (λ) = −kT ln V (λ) and the generalized force adopts the familiar form of the pressure of a single-molecule ideal gas: