# «Found Phys (2013) 43:1384–1410 DOI 10.1007/s10701-013-9753-1 Brownian Computation Is Thermodynamically Irreversible John D. Norton Received: 21 June ...»

3.2 Brownian Motion One of the papers of Einstein’s annus mirabilis of 1905 gives his analysis of Brownian motion [7]. In the paper he noted that the thermal motions of small particles suspended in a liquid would be observable under a microscope and he conjectured that their motions were the same as those observed in pollen grains by the botanist Brown. Einstein’s goal was to give an account of these thermal motions within the molecular-kinetic theory of heat and thereby ﬁnally to establish it as the correct account of thermal processes.1 His starting point was to propose the astonishing idea that, from the perspective of the molecular-kinetic theory, individual molecules and microscopically visible particles can be treated by the same analysis and will give the same results. To reﬂect this

**1 For an account of Einstein analysis, see Norton ([16], Sect. 3).Found Phys (2013) 43:1384–1410 1391**

astonishing idea, the analysis just given above of the statistical physics of a single molecule, has been written in such a way that it can be applied without change to a microscopically visible particle, such as a pollen grain. The controlling fact is that the Hamiltonian for a microscopically visible particle can be written as (1), for the energy of the particle will be independent of its position in the suspending liquid.

The particular expression π (p), which gives the dependence of the Hamiltonian on the momentum degrees of freedom, will be different. For the particle is, to ﬁrst approximation, moving through a resisting, viscous medium. However this difference will not affect the results derived above.

First, we will be able to conclude that a single Brownian particle will exert a pressure conforming to the ideal gas law, as shown in (10). What this means is that the collisions of the Brownian particle with the walls conﬁning it to some volume V will lead to a mean pressure equal to kT /V on the walls. Einstein considered the case of the conﬁning walls as a semi-permeable membrane that allows the liquid but not the particle to pass. Then the pressure is appropriately characterized as an osmotic pressure.

Second, the volume dependence of the thermodynamic entropy of the Brownian particle will conform to (4), so that an n-fold expansion of the volume accessible to the particle will be associated with an increase of thermodynamic entropy of S = k ln n as shown in (5). By the same reasoning as in the case of the one molecule gas, the increase in total entropy is also Stot = k ln n as given by (7).

In direct analogy with the irreversible expansion described above for a single molecule gas, we can form a liquid ﬁlled chamber of volume nV with the Brownian particle trapped by a partition in the leftmost volume V, as shown in Fig. 4. The particle exerts a pressure on the partition of kT /V. When the partition is removed, the unopposed pressure will lead to a thermodynamically irreversible expansion of the one Brownian particle gas into the full chamber. The uncontrolled expansion from volume V to nV is associated with the creation of k ln n of thermodynamic entropy.

Thermodynamically, the expansion of the one molecule gas and the one Brownian particle gas are the same. The two Figs. 3 and 4, however, suggest the great dynamical differences. Ordinary gas molecules at normal temperatures move quickly, typically at many hundreds of meters per second. The motion of the one molecule is unimpeded by any other molecules, so it moves freely between the collisions with Fig. 4 Irreversible expansion of a one Brownian particle gas 1392 Found Phys (2013) 43:1384–1410 the walls. Brownian particles have the same mean thermal energy of kT /2 per degree of freedom. But since they are much more massive than molecules, their motion is correspondingly slower. More importantly, they undergo very many collisions: the jiggling motion of a pollen grain visible under a microscope is the resultant of enormously many collisions with individual water molecules in each second.

This means that the expansion of the one Brownian particle gas is very much slower than that of the one molecule gas. When we observe the Brownian particle under the microscope, we are watching it for the briefest moment of time if we set our time scales according to how long the particle will take to explore the volume accessible to it. If we were to watch it for an extended time, we would see that the particle has adopted a new equilibrium state in which it explores the full volume nV, just as the expanded one molecule gas explores the same volume nV.

These differences of time scales between the one molecule gas and the one Brownian particle gas are irrelevant, however, to the thermal equilibrium states. Both gases start out in an equilibrium state conﬁned to a volume V ; they undergo an uncontrolled, n-fold expansion to a new equilibrium state conﬁned to volume nV ; and their thermodynamic entropies each increase by k ln n.

These remarks draw on the analysis of the earlier parts of Einstein’s [7] paper. In Sect. 3 and later, he took up another aspect of Brownian motion that will not arise in the otherwise analogous physics of Brownian computers. Einstein modeled the Brownian particles as spheres and the surrounding water as a viscous ﬂuid. (There is no analog of the ﬂuid in the Brownian computer.) Einstein then modeled the diffusion of Brownian particles through the liquid as governed by the balance of two forces: the driving force of osmotic pressure in a gradient of particles and the opposing viscous forces as the particles move. What matters for our purposes is that Einstein eventually arrived at a result in the new theory of stochastic processes being created by his paper that is more general that the particular case he analyzed.

It is a result concerning particles, such as Brownian particles, that are animated in a random walk. Their positions spread through space according to a Gaussian distribution whose spatial variance is proportional to time. It follows√ the average that (absolute) distance d(t) covered in some time t is proportional to t. This means that we cannot speak meaningfully of the average speed over time of the Brownian particle, for that average speed √ d(t)/t is proportional to 1/ t → 0 as t → ∞ (11) That is, if one tries to estimate average speed by forming the familiar ratio “distance/time,” that ratio can be made arbitrarily small by allowing time to become arbitrarily large. Einstein ([8], p. 42) remarks that the “... speed thus provided corresponds to no objective property of the motion investigated... ”

**3.3 The Undriven Brownian Computer Without Trap**

A Brownian computer behaves thermodynamically like a one molecule gas or a one Brownian particle gas expanding irreversibly into its conﬁguration space. Here I will develop the simplest case of the undriven Brownian computer without a trap. This is the case that is closest to the irreversible expansion of a one molecule/Brownian Found Phys (2013) 43:1384–1410 1393 particle gas. While it does not terminate the computation usefully, it sets the minimum thermodynamic entropy creation for all Brownian computers. Later we will add extra processes, such as a slight energy gradient to drive the computation faster, or an energy trap to terminate it. Each of these additions will create further thermodynamic entropy.

In this simplest case, the Brownian computer explores a one-dimensional labyrinthine channel in its phase space. All spatial conﬁgurations in the channel are assumed to have the same energy; there is no energy gradient pressing the system in one or other direction. As a result, the Hamiltonian of the Brownian computer is of the form (1), where we have the controlling fact that it depends only on the momentum degrees of freedom. The analysis proceeds as before.

We divide the very high dimensional conﬁguration space of the computer into n stages. Precisely how the division is effected will depend upon the details of the implementation. One stage may correspond to all conﬁgurations in which the Turing machine reader head is interacting directly with one particular tape cell. For simplicity, we will assume that each stage occupies the same volume V in conﬁguration space. Progress through the channel is parametrized by λ, which counts off the stages passed.

To operate the computer, its state is localized initially in the volume of phase space corresponding to the ﬁrst stage, λ = 0 to λ = 1. The device is then unlocked— the thermodynamic equivalent of removing the partition in the gas case—and the computer undertakes a random walk through the accessible channel in its phase space.

As with the one molecule gas, changes in the momentum degrees of freedom play no role in the expansion. The computer settles down into a new equilibrium state in which it explores the full volume nV of the channel of its conﬁguration space. The expansion is driven by an unopposed generalized force X given by (9), and with a volume dependence in conﬁguration space of the single-molecule ideal gas law (10).

The expansion is illustrated in Fig. 5, which also shows the constant energy dependence of the computer on the conﬁguration space.

We arrive at two results. First, since the Hamiltonian is independent of the spatial conﬁguration in the accessible channel, it follows from the Boltzmann distribution (2) that the computer’s state is distributed uniformly over the n stages of λ. That is, its probability density is p(λ) = 1/n (12a)

This is the minimum thermodynamic entropy creation associated with the operation of the Brownian computer. Embellished versions below add processes that create more thermodynamic entropy.

As before, the free energy change is

3.4 The Undriven Brownian Computer with Trap This last Brownian computer is not useful for computation since its ﬁnal, equilibrium state is uniformly distributed over all stages of the computation. The remedy is to add an extra stage, λ = n to λ = n + 1, in which the computer’s energy is dependent on the spatial positions of its parts, that is, on its position in conﬁguration space. In the ﬁnal trap stage, the energy of the system will be Etrap less than the position independent energy of the other stages, which are set by convention to 0. This trapping energy is set so that occupation of the ﬁnal trap stage is probabilistically preferred to whichever extent we choose. When the computer moves into this ﬁnal trap state, the computer state corresponds to that of completion of the computation. This is illustrated in Fig. 6.

The addition of the energy trap introduces a conﬁguration space dependence of the Hamiltonian. Within the accessible channel, it is now

where OP = P /(1 − P ) is the odds of the computer being in the ﬁnal trap state.

Inverting this last expression enables us to determine how large the trapping energy

**Etrap should be for any nominated P or OP :**

The thermodynamic entropy of the initial state is S(1) = Sp (T ) + k ln V as before.

Therefore, the increase in thermodynamic entropy in the course of the thermodynamically irreversible expansion and trapping of the computer state is

In the course of the thermodynamically irreversible expansion, when the system falls into the ﬁnal energy trap, it will release energy Etrap as heat to the environment. More carefully, on average it will release energy P. Etrap since the computer state will only be in the trap with high probability P. This will increase the thermodynamic entropy of the environment by2 Senv = P.Etrap /T (6b) Thus the total thermodynamic entropy change is Stot = Scomp + Senv = k ln n + exp(Etrap /kT ) = k ln n + k ln(1 + OP ) (7b) Hence the effect of adding the trap is to increase the net creation of thermodynamic entropy over that of the untrapped system (7a) by the second term k ln(1 + OP ) = k ln(1/(1 − P )). The added term will be larger according to how much we would like the trap state to be favored, that is, how large we set the odds OP.

Rearranging (5b), we ﬁnd that change in free energy F = E − T S is

We recover the same result from (3b) and the canonical expression F = −kT ln Z.

3.5 The Energy Driven Brownian Computer Without Trap This last case of the undriven but trapped Brownian computer is sufﬁcient to operate a Brownian computer. Bennett ([1], p. 531; [2], p. 921), however, includes the complication of a slight energy gradient in the course of the computation, in order to speed up the computation. We can understand the thermodynamic import of this augmentation by considering the simpler case of an energy gradient driven computer, without the energy trap.

The energy gradient is included by assuming that there is linear spatial dependence of the energy of the system on the parameter λ that tracks progress through the accessible channel in the phase space. That is, we assume an energy ramp of ε per

**stage. The Hamiltonian becomes:**

This is illustrated in Fig. 7.

2 While the process is not thermodynamically reversible, we recover the same thermodynamic entropy change for the environment by imagining another thermodynamically reversible process in which heat energy P. Etrap is passed to the environment.

Found Phys (2013) 43:1384–1410 1397 Fig. 7 Energy driven Brownian computer without trap The effect of the energy ramp will be to accelerate progress towards the completion of the computation as well as skewing the equilibrium probability distribution towards the ﬁnal stage. It will, however, prove to be a thermodynamically inefﬁcient way of assuring completion. That assurance is achieved more efﬁciently with an energy trap, as I believe is Bennett’s intent.

As before, the probability density over the n stages of the computation is

where the approximation is that εn/kT 1. Inverting, we ﬁnd that the energy gradient ε per stage to achieve a ﬁnal stage probability P is

As before, Sp (T ) represents the contribution of the momentum degrees of freedom and is independent of stage of computation achieved. Setting n = 1, we ﬁnd the initial state thermodynamic entropy to be

While the computer moves down the energy ramp, it will on average pass heat −(E(n) − E(1)) to the environment. As before this corresponds to a thermodynamic entropy increase in the environment of

which grows with n much faster than the logarithm in k ln n. Since large values of ε would be needed to drive the system into its ﬁnal stage with high probability, this method of assuring termination of the computation is thermodynamically costly.

3.6 The Energy Driven Brownian Computer with Trap

It is illustrated in Fig. 8.

Since this case incorporates both dissipative processes added in the last two cases, in operation it will create more thermodynamic entropy than any case seen so far, that is, in excess of k ln n, so I will not compute the thermodynamic entropy created.

If P is the probability that the fully expanded system is in the trap, we can compute the odds ratio OP = P /(1 − P ) by taking the ratio of the partition functions for the two regions of phase space: Z(n) for the ﬁrst n stages and Z(trap) for the ﬁnal trap state n λ n + 1. From (3c) and (3b) we have

1, so that exp(−εn/kT ) ≈ 0, If instead we assume more realistically that εn/kT we recover Etrap = kT ln(kT /ε) + kT ln OP = kT ln(OP kT /ε)

**This seems to be the result to which Bennett ([2], p. 921) refers when he writes:**

However the ﬁnal state occupation probability can be made arbitrarily large, independent of the number of steps in the computation, by dissipating a little extra energy during the ﬁnal step, a “latching energy” of kT ln(kT /ε) + kT ln(1/η) sufﬁcing to raise the equilibrium ﬁnal state occupation probability to 1 − η.