# What would it take to build a thermodynamically reversible Universal Turing
machine? Computational and thermodynamic constraints in a molecular design

Rory A. Brittain<EMAIL_ADDRESS>Nick S. Jones  Department of
Mathematics, Imperial College London, London, SW7 2AZ, UK  Thomas E. Ouldridge
Centre for Synthetic Biology and Department of Bioengineering, Imperial
College London, London, SW7 2AZ, UK

###### Abstract

We outline the construction of a molecular system that could, in principle,
implement a thermodynamically reversible Universal Turing Machine (UTM). By
proposing a concrete—albeit idealised—design and operational protocol, we
reveal fundamental challenges that arise when attempting to implement
arbitrary computations reversibly. Firstly, the requirements of thermodynamic
reversibility inevitably lead to an intricate design. Secondly,
thermodynamically reversible UTMs, unlike simpler devices, must also be
logically reversible. Finally, implementing multiple distinct computations in
parallel is necessary to take the cost of external control per computation to
zero, but this approach is complicated the distinct halting times of different
computations.

Computational operations use physical substrates, and thus have physical
consequences landauer1996physical . The equivalence of the Shannon and the
non-equilibrium thermodynamic entropies esposito2011second  provides a
concrete link between information-processing and thermodynamics; how the
resultant thermodynamic costs might be minimised is an important open
question. Many analyses have focused on specific tasks, such as erasing and
copying bits landauer1961irreversibility ; szilard1929entropieverminderung ;
recent studies have extended these ideas to the the processing of strings
mandal2012work ; boyd2016identifying ; Stopnitzky2019Physical ;
brittain2019biochemical . Others have focused instead on computation as an
arbitrary process in which an input state is converted into an output. Within
this framework, Bennett argued that thermodynamically reversible computers
must use reversible logic, wherein the input state can be inferred
unambiguously from its output bennett1973logical . However, it has since been
shown that any input-output map—whether logically reversible or not—can be
implemented in a thermodynamically reversible fashion owen2018number ,
provided that the distribution of input states is known
kolchinsky2017dependence .

Turing machines are a model of arbitrary computation turing1937computable .
Traditionally, the machine’s memory is a tape: a sequence of symbols from a
finite alphabet. The tape is processed by a head with a finite state set that
reads the symbol at a position on the tape. Then, based on a machine-dependent
set of transition rules, the head writes a new symbol at that tape site, moves
either left or right to an adjacent site, and the head state changes.
Sufficiently complex machines can be ‘Turing complete’: they can compute any
computable function. These machines are called universal Turing machines
(UTM).

The thermodynamics of abstract UTMs has been explored in the context of
algorithmic information theory kolchinsky2019thermodynamic . However, it is
also illuminating to consider actual physical designs of low thermodynamic-
cost UTMs brittain2019biochemical ; ouldridge2018power ;
kolchinsky2019thermodynamic . By making even an idealised design explicit, one
can avoid hidden violations of the second law, and reveal fundamental
challenges in constructing a device.

Molecular systems are promising substrates for computing
bennett1982thermodynamics ; the similarity of tape-processing ribosomes and
TMs is tantalising. One approach to molecular computation uses macroscopic
quantities of molecules for each computation, and either repeatedly
intervening to direct the computational steps adleman1994molecular ;
beaver1995universal ; rothemund1995dna ; smith1995dna ; currin2017computing
or allowing the solution to relax to equilibrium and perform a computation
chen2013programmable ; cardelli_chemical_2016 . In both cases, the bulk scale
makes the thermodynamic cost per computation large.

An alternative is to use a small number of computational molecules, coupled to
large baths of ancillary fuel. Bennett sketched a UTM of this kind
bennett1973logical , and more recently Qian, Soloveichick and Winfree
qian2010efficient  conceived a specific DNA-based realisation of a stack
machine, a close analogue of a UTM. In both designs, the overall free-energy
change per step in the forward direction, $-\epsilon$, is constant during a
computation. For $\epsilon>0$, the computation proceeds irreversibly forwards
with a finite entropy production (or thermodynamic cost) per step
strasberg2015thermodynamics . For $\epsilon\rightarrow 0$, the computation
undergoes unbiased diffusion, and the output computational state will not
dominate the ensemble even at infinite time. Moreover, the total entropy
production is positive even in this unbiased limit, due to the irreversible
spreading of the system’s probability distribution over its computational
states strasberg2015thermodynamics .

We outline a thermodynamically reversible, sequentially-operated molecular UTM
in which the underlying computational logic is implemented by an explicit
model of a surface-localised chemical reaction network. We first outline the
general design principles, before describing the device in more detail. We
then illustrate key challenges that arise when implementing thermodynamically
reversible UTMs, as opposed to simpler operations. Firstly, even a minimal
design is intricate, emphasising how challenging it would be to actually
construct a thermodynamically reversible, sequentially-operated molecular UTM.
Secondly, thermodynamically reversible, sequentially-operated UTMs—unlike
simpler devices—must be logically reversible. Finally, running distinct
computations in parallel to minimise the costs of control is complicated by
the distinct halting times of different computations.

Control protocols for thermodynamically reversible UTMs. A reversible UTM must
be subject to time-dependent external control, since any free evolution of a
thermodynamic system is necessarily irreversible machta2015dissipation ;
ouldridge2018importance . However, systematic evolution of the control
variable itself implies entropy generation machta2015dissipation . In
traditional thermodynamics, controls are applied to large systems: costs
associated with evolving the control variable itself, and implementing any
logic therein, can be made small relative to changes in the system
machta2015dissipation . The same is not true for controlling a single
computation. The same control must therefore be applied to multiple UTMs in
parallel brittain2019biochemical , so that any thermodynamic costs of applying
a control protocol are negligible when divided by the number of computations.
Controls cannot, therefore, include feedback on the state of individual
computations, since the costs arising cannot be spread over multiple UTMs.

Ideal molecular reactions provide an explicit model system from which to
construct a thermodynamically reversible UTM. We assume that it is possible to
design chemical reaction networks with reactions of the form

$\sum_{\\{i\\}}\text{X}_{i}+\sum_{\\{j\\}}\text{Y}_{j}+\mathrm{F}^{*}\rightleftharpoons\sum_{\\{i\\}}\text{X}^{\prime}_{i}+\sum_{\\{j\\}}\text{Y}_{j}+\mathrm{F}.$
(1)

Here, $\text{X}_{\\{i\\}}$ is a set of substrate species converted into
products $\text{X}^{\prime}_{\\{i\\}}$ by the action of catalysts
$\text{Y}_{\\{j\\}}$. Each reaction is driven by the turnover of a fuel
molecule $\mathrm{F}^{*}\rightleftharpoons\mathrm{F}$. While such reactions
are not elementary, compound catalytic action occurs naturally in, for
example, transcription and translation, and can be engineered using DNA
nanotechnology qian2010efficient ; chen2013programmable ; srinivas2017enzyme .
These reactions need not approximate mass-action kinetics plesa2018stochastic
, but the overall stoichiometry must be tightly observed, with the reactions
only occurring if all catalysts and fuel are present.

We consider many UTMs in a single reaction volume (Fig. 1 (a)), all coupled to
the same large baths of fuel (the external control) via a semi-permeable
membrane. By varying the concentration of these baths schmiedl2007stochastic ;
rao2016nonequilibrium ; ouldridge2017fundamental , reactions of the form of
Eq. 1, involving the UTM’s species, can be quasistatically driven in either
direction, or turned on and off brittain2019biochemical . Our design of a
molecular UTM is sequential: it has clocked control cycles involving a single
update of the head, tapes and the head position. All cycles are driven by the
same sequence of baths, which can be arranged in a circle as shown in Fig.
1(a). One turn of the circle corresponds to one step of each UTM.

This setup has several conceptual advantages ouldridge2018power . Firstly,
providing the control is simple; we cycle a series of buffers past a reaction
volume, without adjusting to the system’s response; the control is mechanical
but the computation is chemical. Secondly, the baths both control the reaction
and act as a reservoir of chemical work; there is no ambiguity about how work
is stored and transferred. Thirdly, the reaction in Eq. 1 allows the
$\text{Y}_{\\{j\\}}$ and $\text{X}_{\\{i\\}}$ species to influence the
evolution of the $\text{X}_{\\{i\\}}$ species. However, the reaction only
occurs if the fuel is present; quasistatic re-wiring can be performed by
changing which fuel molecules are present ouldridge2018power ;
brittain2019biochemical .

Reaction
---
volume
Operator
---
turns rail
Stepping
---
phase
Update
---
phase
Rail of
---
buffers
Scaffold
---
A
---
D
---
M
---
T
---
Molecular
---
motor
X3
---
X2
---
X1
---
(a)
---
(b)
---
Stepping phase
---
Update phase
---
M
---
T
---
D
---
A
---
M′
---
T′
---
D′
---
A′
---
G∗
---
G
---
D=R
---
F${}_{1}^{*}$
---
F1
---
Or
---
(c)
---
X3
---
X2
---
X1
---
D=L
---
F${}_{1}^{*}$
---
F1
---
X1
---
X3
---
X2
---
Figure 1: _Overview of a molecular UTM._ (a) A reaction volume containing many
UTMs. A protocol of fuel concentrations is applied by connecting the volume to
a series of large, fuel-containing baths. The baths are arranged in a circle
so the same protocol can be applied repeatedly. Individual UTMs act on two
tape polymers with evenly spaced molecules (M,T) to represent their state. The
state of the UTM head is encoded in the state of molecules (A,D) attached to a
scaffold such as DNA origami. The head is attached to the tapes by molecular
motors that move the head from one symbol to the next. (b) Stepping is powered
by fuel molecules Fi. The directional molecule D on the head catalyses
stepping in the appropriate direction. (c) During the update phase, states of
the head (A), tape molecules (M,T), and the directional molecule (D) are
updated, powered by a fuel molecule $G$. 0
---
1
---
2
---
5
---
3
---
4
---
0
---
1
---
2
---
5
---
3
---
4
---
0
---
5
---
1
---
2
---
3
---
4
---
2
---
4
---
6
---
10
---
12
---
0.0
---
0.5
---
1.0
---
1.5
---
(a)
---
(b)
---

Timestep
---

Timestep
---

Symbol and state
---
Position
---
0.00
---
0.05
---
0.10
---
0.15
---
0.20
---
a
---
b
---
c
---
d
---
a
---
a
---
a
---
a
---
a
---
b
---
b
---
b
---
b
---
b
---
c
---
c
---
c
---
c
---
c
---
d
---
d
---
d
---
d
---
d
---
0
---
1
---
2
---
3
---
4
---
5
---
0
---
1
---
2
---
3
---
4
---
5
---
0
---
1
---
2
---
3
---
4
---
5
---
0
---
1
---
2
---
3
---
4
---
5
---
Figure 2: _UTM operation generates both a complex distribution of head and
tape states at each step, and correlations between states on the tape._ We
consider a 4-state, 6-symbol machine (Appendix C.2) (a) Evolution of the
probability distribution of the head and active tape site at the stare of each
update phase. The head is initially in state A and positioned in the middle of
5 non blank symbols in an infinite tape of blank symbols. The machine is run
for 5 steps with the states of the 5 non-blank symbols randomly chosen for
each of 100,000 iterations. (b) The mutual information between the symbol at
position 6, the initial position of the head, and the symbols at the
neighbouring positions at the start of each update. The head is initially in
state A and at position 6 in the middle of 13 non-blank symbols in an infinite
tape of blank symbols. The machine is run for 5 steps with the states of the
13 symbols randomly chosen for each of 100,000 iterations.

_Design and operation of a molecular UTM._ The head of a UTM in our design
consists of two or more molecular species localised to a scaffold surface
(Fig. 1(a)). The head interacts with two tapes, a main tape and a memory tape,
represented by molecules attached to polymers at regular intervals. The head
is attached to the polymers by molecular motors. At any one time, the head
molecules can interact with each other and at most one pair of sites on the
tapes. Since we are concerned only with the thermodynamics of converting
inputs to outputs, we assume that the machines and tapes are provided in their
starting configurations.

The UTM cycle has distinct stepping and update phases. During the stepping
phase (Fig. 1(b)), The head must step selectively in either direction along
the main tape without relying on the discretion of an operator. This
directionality is implemented through a ‘direction molecule’ D, which
catalyses the transition of the motor between its configurations when the
appropriate fuels are present. The direction molecule can either be in the
left, L, or the right, R, state, specifying the direction of the next step.
The direction molecule also has a halting state $H$ that does not catalyse
stepping on the main tape.

If the stepping of the motor involves at least three different substates,
$\text{X}_{1}$, $\text{X}_{2}$ and $\text{X}_{3}$ (Fig. 1(b)), fuels can be
added that drive $\text{X}_{1}\overset{\text{L}}{\rightarrow}\text{X}_{2}$ and
$\text{X}_{1}\overset{\text{R}}{\rightarrow}\text{X}_{3}$;
$\text{X}_{2}\overset{\text{L}}{\rightarrow}\text{X}_{3}$ and
$\text{X}_{3}\overset{\text{R}}{\rightarrow}\text{X}_{2}$; and
$\text{X}_{3}\overset{\text{L}}{\rightarrow}\text{X}_{1}$ and
$\text{X}_{2}\overset{\text{R}}{\rightarrow}\text{X}_{1}$. If these fuels are
introduced and removed quasistatically and sequentially, stepping will be
deterministic and thermodynamically reversible; one step is shown in Fig. 1(b)
and further details are given in Appendix A. The motor attached to the memory
tape always takes a single step in the same direction during the stepping
phase.

The head state, the symbols on the tapes and direction molecule are updated
during the update phase via reactions of the form of Eq. 1 (Fig. 1(c)). The
details depend on the specific set of rules chosen for the UTM, and how the
states of the head are encoded in the molecular species. In the conceptually
simplest case, a single molecule A represents the head state, along with the
direction molecule. In this case, each update rule of a UTM can be expressed
through reactions of the form

$\displaystyle\text{A}+\text{L}+\text{T}+\mathrm{M}_{0}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}^{\prime}+\text{D}^{\prime}+\text{T}^{\prime}+\mathrm{M}_{2i}+\mathrm{G},$
$\displaystyle\text{A}+\text{R}+\text{T}+\mathrm{M}_{0}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}^{\prime}+\text{D}^{\prime}+\text{T}^{\prime}+\mathrm{M}_{2i-1}+\mathrm{G},$
(2)

where $\mathrm{M}_{0}$ is the default initial state of the memory tape and $i$
numbers each transition rule; the memory tape therefore makes a record of the
transition taken. A and A′, T and T′, and L/R and D′ represent the initial and
final states of the head, the main tape and the direction molecule,
respectively. The protocol involves simply modulating fuel concentrations in
the following manner

$\begin{matrix}[\mathrm{G}]:&0&\rightarrow&g&\rightarrow&g&\rightarrow&0&\rightarrow&0\\\
[\mathrm{G}^{*}]:&0&\rightarrow&0&\rightarrow&\gg g&\rightarrow&\gg
g&\rightarrow&0,\end{matrix}$ (3)

where $g$ is a large concentration. This protocol drives the reactions in Eq.
2 reversibly from left to right, then switches them off before stepping.

In this set-up, each transition rule of the UTM needs two reactions. Each rule
also requires two different memory states, in addition to $\mathrm{M}_{0}$.
The directional molecule has three states. The number of head molecule and
tape states follow from the specific UTM. It is possible to use fewer memory
species at the expense of increased conceptual complexity; the reactions and
species required for some example machines are shown in Appendix C. It is
apparent that even the simplest design is sophisticated, with molecular
species involved in several highly specific reactions. The need to perform
precisely the right series of sequential reactions, and couple those reactions
tightly to motion along a polymer, makes this complexity unavoidable. Without
even considering the challenges of applying quasistatic manipulation of the
baths, this complexity far exceeds what is currently implementable in
practice. This complexity is easily overlooked in models that do not represent
every stage explicitly bennett1982thermodynamics .

An ensemble of thermodynamically reversible UTMs requires an ensemble of
distinct input programs. Fig. 1 shows an ensemble of UTMs operating in
parallel. If the task was to erase or extract work from inputs, then it would
be reasonable to act in parallel on identical inputs. For each additional
system, something more is achieved. However, if the goal is to answer a
computational question, then acting in parallel on identical inputs does not
reduce the cost per answer. Spreading the costs of external control over many
computations requires parallel operation on multiple different inputs.

The first consequence of performing distinct computations in parallel is that
a record of each computation must be unambiguously associated with each tape.
If not, there would be no way to match the answers to questions asked. This
record could be physically attached to the tape. Note that the record is a
specification (eg. “divide 135 by 5 and output the answer in a specific way”),
so need not be a copy of the program itself.

Sequentially-operated, thermodynamically-reversible UTMs must have logically-
reversible update rules. The memory tape makes the computation locally
logically reversible: at each stage the input state of head and tape molecules
can be unambiguously inferred from their final values. Without the memory,
multiple inputs would be mapped to the same output by the reactions of Eq. 2.
This mixing defines logical irreversibility.

Consider $\text{A}+\text{L}+\text{T}$ and
$\text{A}^{\prime}+\text{L}+\text{T}$ being converted to the same output. At
some instant, systems that started in $\text{A}+\text{L}+\text{T}$ will
transition to the states occupied by systems that started in
$\text{A}^{\prime}+\text{L}+\text{T}$, and vice versa. At this time, if a net
flow of trajectories occurs in either direction, the process is
thermodynamically irreversible ouldridge2018importance . For logical states to
mix reversibly, they must be offset in free energy to avoid net transitions
from the more populated state to to the less populated one. As a result, a
thermodynamically reversible protocol for a logically irreversible input-
output map must be tuned to the distribution of input states
kolchinsky2017dependence .

Tuning to the input distribution is far more problematic for sequentially-
operated UTMs than for simpler operations like erasing or copying of bits.
Firstly, sequential UTMs implement complex computations through a series of
simpler steps. To be thermodynamically reversible, a protocol would need to be
optimised to the initial distribution of the head and tape at each step
wolpert2015extending . As illustrated in Fig. 2 (a), this initial distribution
has complex behaviour even for a simple UTM; re-applying the same cyclic fuel
protocol, as in Fig. 1 (a), would be impossible. Instead, we’d need to encode
a priori knowledge of how the UTM would process a distribution of input tapes
into a long, non-cyclic array of fuel baths. We’d effectively need to know the
output of the relevant computations already just to build the UTM.

Secondly, although the update rules of UTMs are local, statistical information
will exist between the locally active region of the UTM and other sites in the
tape, as well as the record of the computation. As demonstrated in Fig. 2 (b),
UTMs generate this information even if it does not initially exist. A local
update of a subsystem when information exists between that subsystem and the
rest of the system typically causes “modularity dissipation”
boyd2018thermodynamics ; wolpert2020minimum , wherein the non-equilibrium free
energy stored in this information is wasted irreversibly. To avoid modularity
dissipation, either: (a) no information with the rest of the system must be
lost; or (b) the free energy stored in this information must be extracted. If
the local update is logically reversible, (a) is trivially satisfied since the
update simply permutes the occupancy of states. For logically irreversible
updates, the mixing of distinct inputs will tend to reduce information with
the rest of the system. To compensate, the rest of the system would have to be
involved in the update—not to set the output, but to influence the protocol
experienced by the active subsystem and thereby recover the stored free
energy. For the the design in Fig. 1, the rest of the tape would have to
catalytically couple the head and active site to well-tuned fuel baths for
information to be exploited. Doing so would be even more challenging—both
mechanistically and computationally—than building a logically reversible
device.

The interplay of halting and thermodynamics. To compute, a UTM must halt. In
simpler contexts, when the same operation can be performed in parallel on
multiple identical inputs, all operations will halt simultaneously. For UTMs
performing arbitrary and distinct computations in parallel, however, halting
times may be widely distributed; individual halting times may not be known _a
priori_ , and some computations may not halt at all.

This additional complexity raises three challenges. The first is that halted
UTMs must stay in a valid halted state as the external protocol continues to
be applied. This feature is designed into our molecular UTMs: the head and
main tape do not evolve once the halt state is reached. The stepping is halted
on the main tape but continues on the memory tape. Secondly, the control cycle
must eventually stop, and it cannot simply intuit when all computations are
halted. If an upper limit on the time of the computations in question is
known, or if the operator is prepared to accept that some computations may not
have halted or that unnecessary steps may be taken, the protocol can be
stopped after a fixed number of steps with a cost that scales sub-linearly
with the number of computations machta2015dissipation .

Alternatively, although measurement and feedback on individual UTMs would
violate the parallel nature of the protocol, the minimal thermodynamic cost of
answering and acting upon the binary question of whether all machines have
halted scales sub-linearly with the number of UTMs. However, the mechanistic
challenges are high. For example, a single molecule E that can undergo fuel-
powered conversion catalysed by L or R,
$\text{E}\overset{\text{L}}{\rightarrow}\text{E}^{\prime}$ or
$\text{E}\overset{\text{R}}{\rightarrow}\text{E}^{\prime}$, would reach the
state $\text{E}^{\prime}$ via a single reaction if and only if at least one of
the UTMs had not halted. However, the operator would have to wait for a single
probe to interact with all UTMs.

Thirdly, and most deeply, as the faster computations halt, the protocol is
applied to fewer active UTMs. The strategy of spreading the control cost over
many computations is then questionable. In our case, control cost is the cost
of ensuring that the baths move systematically past the reaction volume for
the desired number of cycles; it is separate from the efficiency of the
chemical computation. Machta argued that each unidirectional cycle of a
control parameter has a minimal entropy generation associated with it
machta2015dissipation ; we therefore assume that the cost of external control
$C$ is linear in the number of protocol cycles $t$ implemented,
$C(M,t)=\alpha(M)t+C_{0}(M)$, with $C_{0}$ representing initiation and
termination costs and $M$ the number of distinct computations under control, a
proxy for the system size. We allow for a dependence of $C$ on $M$: Machta
found $\alpha(M)\sim M^{0.5}$ machta2015dissipation .

If all $M$ computations in a set $\mathcal{S}_{M}$ halt in a time $t_{M}$, the
minimal control cost per computation is
$C(\mathcal{S}_{M})/M=\alpha(M)t_{M}/M+C_{0}(M)/M$. If the $M$ computations
are drawn from a set $\mathcal{S}\supset\mathcal{S}_{M}$ of interest, we can
ask whether it is always possible to reduce $C(\mathcal{S}_{M})/M$ by using a
subset with a larger $M=|\mathcal{S}_{M}|$. Assuming $C_{0}(M)$ scales sub-
linearly with $M$ machta2015dissipation , $C_{0}(M)/M\rightarrow 0$ as
$M\rightarrow\infty$. However, as we increase $M,$ newly-chosen inputs may
have a longer halting time and hence $t_{M}$ will grow. If the halting times
of computational problems of interest are sparsely distributed,
$\alpha(M)t_{M}/M$ may grow with $M$, implying that $C(\mathcal{S}_{M})/M$
cannot be made negligible.

For $\alpha(M)\sim M^{0.5}$, we require that subsets $\mathcal{S}_{M}$ can be
found such that $t_{M}$ grows more slowly than $M^{0.5}$. Consider an
algorithm with a halting time that is linear in the length $N$ of the input.
If there are $N!$ problems of interest of length $\leq N$, sets
$\mathcal{S}_{M}$ can be found satisfying $t_{M}\sim M/{M}!$ and
$C(\mathcal{S}_{M})/M$ can easily be made negligible. If, by contrast, there
is only one problem of interest at each length, $t_{M}\sim M$ and
$C(\mathcal{S}_{M})/M$ grows with $M$.

Requiring that $C(\mathcal{S}_{m})/M\rightarrow 0$ implies that all
computations, regardless of their underlying difficulty, are equally valuable.
An alternative would be to divide the cost per computation by a measure of the
time complexity of the computations performed. As outlined in Appendix D, the
resulting constraint is easier to satisfy but sets of computations
$\mathcal{S}$ still exist for which the normalised cost of control grows with
$M$ for $\mathcal{S}_{M}\subset\mathcal{S}$.

We have shown that the construction of a sequentially-operated,
thermodynamically reversible molecular UTM has challenges that arise from the
very purpose of a UTM: to perform complex computations. To circumvent some of
these challenges, one could consider a machine that operates in a single
control step. For example, the stack machine of Qian _et al._
qian2010efficient  could migrate from the input to the output state if the
driving from ancillary fuel molecules was slowly increased over time, avoiding
the issue of choosing when to stop. However, doing so would raise a new
problem: the later states would rapidly transition from being exponentially
suppressed to exponentially favoured relative to the early states as the
driving force was varied. For calculations of unknown (and arbitrary) length,
it would be extremely challenging to implement a protocol that manages this
change reversibly. In fact, in cases where the halting state is never reached,
the computation would undergo an uncontrolled and irreversible growth as the
driving force passed through zero.

## References

  * (1) R. Landauer.  Phys. lett. A, 217(4-5):188–193, 1996.
  * (2) M. Esposito and C. Van den Broeck.  EPL, 95(4):40004, 2011.
  * (3) R. Landauer.  IBM J. Res. Dev., 5(3):183–191, 1961.
  * (4) L. Szilard.  Z. Phys., 53(11-12):840–856, 1929.
  * (5) D. Mandal and C. Jarzynski.  Proc. Natl. Acad. Sci. U.S.A., 109(29):11641–11645, 2012.
  * (6) A. B. Boyd, D. Mandal, and J. P. Crutchfield.  New J. Phys., 18(2):023049, 2016.
  * (7) E. Stopnitzky, S. Still, T. E. Ouldridge, and L. Altenberg.  Phys. Rev. E, 99:042115, 2019.
  * (8) R. A. Brittain, N. S. Jones, and T. E. Ouldridge.  New Journal of Physics, 21(6):063022, 2019.
  * (9) C. H. Bennett.  IBM J. Res. Dev., 17(6):525–532, 1973.
  * (10) J. A. Owen, A. Kolchinsky, and D. H. Wolpert.  New J. Phys., 2018.
  * (11) A. Kolchinsky and D. H. Wolpert.  J. Stat. Mech. Theory Exp., 2017:083202, 2017.
  * (12) A. M. Turing.  Proc. London Math. Soc., 2(1):230–265, 1937.
  * (13) A. Kolchinsky and D. H. Wolpert.  arXiv preprint arXiv:1912.04685, 2019.
  * (14) T. E. Ouldridge, R. A. Brittain, and P. R. ten Wolde.  In D. H. Wolpert, C. P. Kempes, P. Stadler, and J. Grochow, editors, The Interplay of Thermodynamics and Computation in Natural and Artificial Systems. SFI Press, 2018.
  * (15) C. H. Bennett.  Int. J. Theor. Phys., 21(12):905–940, 1982.
  * (16) L. M. Adleman.  Science, 266(5187):1021–1024, 1994.
  * (17) D. Beaver.  In L. F. Landweber and E. B. Baum, editors, DNA Based Computers, pages 29–36. American Mathematical Society, 1995.
  * (18) P. W. K. Rothemund.  In L. F. Landweber and E. B. Baum, editors, DNA Based Computers, pages 75–119. American Mathematical Society, 1995.
  * (19) W. D. Smith.  DNA based computers, 27:121–186, 1995.
  * (20) A. Currin, K. Korovin, M. Ababi, K. Roper, D. B. Kell, P. J. Day, and R. D. King.  J. R. Soc. Interface, 14(128):20160990, 2017.
  * (21) Y.-J. Chen, N. Dalchau, N. Srinivas, A. Phillips, L. Cardelli, D. Soloveichik, and G. Seelig.  Nat. Nanotechnol., 8(10):755, 2013.
  * (22) L. Cardelli, M. Kwiatkowska, and M. Whitby.  In International Conference on DNA-Based Computers, pages 67–81. Springer, 2016.
  * (23) L. Qian, D. Soloveichik, and E. Winfree.  In International Workshop on DNA-Based Computers, pages 123–140. Springer, 2010.
  * (24) P. Strasberg, J. Cerrillo, G. Schaller, and T. Brandes.  Phys. Rev E, 92(4):042104, 2015.
  * (25) B. B. Machta.  Phys. Rev. Lett., 115:260603, 2015.
  * (26) T. E. Ouldridge.  Nat. Comput., 17(1):3–29, 2018.
  * (27) N. Srinivas, J. Parkin, G. Seelig, E. Winfree, and D. Soloveichik.  Science, 358(6369):eaal2052, 2017.
  * (28) T. Plesa.  arXiv preprint arXiv:1811.02766, 2018.
  * (29) T. Schmiedl and U. Seifert.  J. Chem. Phys., 126(4):044101, 2007.
  * (30) R. Rao and M. Esposito.  Phys. Rev. X, 6(4):041064, 2016.
  * (31) T. E. Ouldridge and P. R. ten Wolde.  Phys. Rev. Lett., 118(15):158103, 2017.
  * (32) D. H. Wolpert.  arXiv preprint arXiv:1508.05319, 2015.
  * (33) A. B. Boyd, D. Mandal, and J. P. Crutchfield.  Phys. Rev. X, 8(3):031036, 2018.
  * (34) D. H. Wolpert.  arXiv preprint arXiv:2001.02205, 2020.
  * (35) A. Smith.  Complex Syst., 2007.
  * (36) D. Woods and T. Neary.  Theor. Comput. Sci., 410(4-5):443–450, 2009.
  * (37) Y. Rogozhin.  Theor. Comput. Sci., 168(2):215–240, 1996.

##  Appendix A Stepping

We assume that the head changing position is an elementary transition that can
happen in a chemical reaction: we assume that the molecular motor can rotate a
third of a step while simultaneously switching which segment of the motor is
bound to the polymer in a single step without the polymer and motor becoming
unbound at any point. This is a strong simplifying assumption so a version of
stepping without this assumption is given in Appendix B.

The tape has a repeating structure of sites where the molecular motor can
bind. There are three different types of site: X, Y and Z that can,
respectively, bind to the X, Y and Z regions of the molecular motor. This is
shown in figure 3. The X sites are the positions on the tape where the symbol
molecule on the tape lines up with the tethered head molecules (these are the
only positions that correspond to positions in the abstract view of the
machine) and the Y and Z are intermediate positions to which the head can
attach.

To move right the reactions

Figure 3: The stepping of the molecular motor.

$\displaystyle\mathrm{F}^{*}_{1}+\text{R}+\text{X}_{i}$
$\displaystyle\rightleftharpoons\text{R}+\text{Y}_{i}+\mathrm{F}_{1},$
$\displaystyle\mathrm{F}^{*}_{2}+\text{R}+\text{Y}_{i}$
$\displaystyle\rightleftharpoons\text{R}+\text{Z}_{i}+\mathrm{F}_{2},$
$\displaystyle\mathrm{F}^{*}_{3}+\text{R}+\text{Z}_{i}$
$\displaystyle\rightleftharpoons\text{R}+\text{X}_{i+1}+\mathrm{F}_{3},$ (4)

are used and to move left the reactions

$\displaystyle\mathrm{F}^{*}_{1}+\text{L}+\text{X}_{i}$
$\displaystyle\rightleftharpoons\text{L}+\text{Z}_{i-1}+\mathrm{F}_{1},$
$\displaystyle\mathrm{F}^{*}_{2}+\text{L}+\text{Z}_{i-1}$
$\displaystyle\rightleftharpoons\text{L}+\text{Y}_{i-1}+\mathrm{F}_{2},$
$\displaystyle\mathrm{F}^{*}_{3}+\text{L}+\text{Y}_{i-1}$
$\displaystyle\rightleftharpoons\text{L}+\text{X}_{i-1}+\mathrm{F}_{3},$ (5)

are used. If the head contains the direction molecule in the R state then the
head can be quasistatically moved from $\text{X}_{i}$ to $\text{Y}_{i}$ to
$\text{Z}_{i}$ to $\text{X}_{i+1}$ and if the direction molecule is in the L
state then the head can be quasistatically moved from $\text{X}_{i}$ to
$\text{Z}_{i-1}$ to $\text{Y}_{i}$ to $\text{X}_{i-1}$. This is done using the
protocol for three separate bit flips starting from a definite state.

For the left motion we could, alternatively, use three different pairs of fuel
molecules, $\mathrm{F}_{4}$, $\mathrm{F}_{5}$ and $\mathrm{F}_{6}$, from the
right motion. This could make the mechanism easier to understand because the
mechanisms for the two directions are independent. We adopt the approach in
equations 5 and 4 as reusing the same species reduces the total number of fuel
molecule required.

Figure 4: The protocol of concentrations of the fuel molecules to implement
one step, which is left or right depending on the state of the direction
molecule. While apparently complicated in fact the same approach is repeated
three times. f1, f2 and f3 need only be a large concentration and in fact the
same label could have been used in all cases.

The protocol of concentrations for the fuel molecules is shown in figure 4.
The work extracted from the buffers is the change in free energy of the head
when it is attached to the different positions. We assume that the free energy
is the same when the head is attached to any of the $\text{X}_{i}$. The free
energy when attached to either of the intermediate states could be different
but that is unimportant since the work done to move from $\text{X}_{i}$ to
$\text{X}_{i+1}$ or $\text{X}_{i-1}$ is zero.

##  Appendix B Alternative Molecular motor

It is more realistic if the motor can detach from the tape. Consider an
actin/myosin style set-up where the motor has two feet. An overview is shown
in figure 5.

Figure 5: Overview of more realistic molecular motor. The arrows represent the
direction of the quasistatic change when taking a rightwards step. Of course,
each step is microscopically reversible and when moving left the arrows are
all in the opposite directions. The X′ is meant to show that that is a place
where the X foot can bind.

This is more complicated than the previous set-up because the motor has more
possible states but there are only 5 different reactions required. To move
right there are the reactions

$\displaystyle\mathrm{F}^{*}_{1}+\text{R}+\text{X}_{\text{attached}}$
$\displaystyle\rightleftharpoons\text{R}+\text{X}_{\text{unattched}}+\mathrm{F}_{1}$
$\displaystyle\mathrm{F}^{*}_{2}+\text{R}+\text{Y}_{\text{attached}}$
$\displaystyle\rightleftharpoons\text{R}+\text{Y}_{\text{unattached}}+\mathrm{F}_{2}$
$\displaystyle\mathrm{F}^{*}_{3}+\text{R}+\text{X}\text{Y}$
$\displaystyle\rightleftharpoons\text{R}+\text{Y}\text{X}+\mathrm{F}_{3}$ (6)

where XY and YX represent the configurations where either the X foot is on the
left of the motor or the Y foot is on the left of the motor. To move left the
L state catalyses the same equations but the fuels that cause the attaching
and detaching of the X and Y are swapped and the same reaction to change the
conformation of the walker is used

$\displaystyle\mathrm{F}^{*}_{2}+\text{L}+\text{X}_{\text{attached}}$
$\displaystyle\rightleftharpoons\text{L}+\text{X}_{\text{unattched}}+\mathrm{F}_{2}$
$\displaystyle\mathrm{F}^{*}_{1}+\text{L}+\text{Y}_{\text{attached}}$
$\displaystyle\rightleftharpoons\text{L}+\text{Y}_{\text{unattached}}+\mathrm{F}_{1}$
(7)

However, a more complicated protocol of fuel concentrations is required. This
protocol is shown in figure 6. This protocol requires twice as many steps as
the previous one.

Figure 6: The protocol of fuel concentrations for the molecular motor that is
inspired by actin myosin.

##  Appendix C Examples

###  C.1 2-state 3-symbol Machine

This machine is claimed to be the smallest possible Turing machine
smith2007universality  but it is only Turing complete if the tape initially
has a complex encoding of an infinite string. The usual definition of a Turing
machine requires that the tape is initialised with an infinitely repeating
symbol containing only a finite string of different symbols
neary2012complexity .

The molecules on the tape can be in three states: 0, 1 and 2. The ‘state
molecule’ of the head (like the ‘memory molecule’) has two states: A and B.
The transitions for this machine are shown in table 1.

| A | B
---|---|---
0 | B1R | A2L
1 | A2L | B2R
2 | A1L | A0R
Table 1: The rules for Wolfram’s 2 state 3 symbol machine.

As mentioned in the main text, the most straightforward way to convert this
list of rules to an invertible map is for the memory molecule to be initially
in the state $\mathrm{M}_{0}$ and to convert it to a state labelled by the
number of the rule that is used as below:

$\displaystyle\text{A}+\text{L}+0+\mathrm{M}_{0}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+\text{R}+1+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{A}+\text{R}+0+\mathrm{M}_{0}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+\text{R}+1+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{A}+\text{L}+1+\mathrm{M}_{0}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{L}+2+\mathrm{M}_{3}+\mathrm{G}$
$\displaystyle\text{A}+\text{R}+1+\mathrm{M}_{0}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{L}+2+\mathrm{M}_{4}+\mathrm{G}$
$\displaystyle\text{A}+\text{L}+2+\mathrm{M}_{0}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{L}+1+\mathrm{M}_{5}+\mathrm{G}$
$\displaystyle\text{A}+\text{R}+2+\mathrm{M}_{0}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{L}+1+\mathrm{M}_{6}+\mathrm{G}$
$\displaystyle\text{B}+\text{L}+0+\mathrm{M}_{0}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{L}+2+\mathrm{M}_{7}+\mathrm{G}$
$\displaystyle\text{B}+\text{R}+0+\mathrm{M}_{0}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{L}+2+\mathrm{M}_{8}+\mathrm{G}$
$\displaystyle\text{B}+\text{L}+1+\mathrm{M}_{0}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+\text{R}+2+\mathrm{M}_{9}+\mathrm{G}$
$\displaystyle\text{B}+\text{R}+1+\mathrm{M}_{0}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+\text{R}+2+\mathrm{M}_{10}+\mathrm{G}$
$\displaystyle\text{B}+\text{L}+2+\mathrm{M}_{0}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{R}+0+\mathrm{M}_{11}+\mathrm{G}$
$\displaystyle\text{B}+\text{R}+2+\mathrm{M}_{0}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{R}+0+\mathrm{M}_{12}+\mathrm{G}.$
(8)

We only need one pair of fuel molecules because each reaction is otherwise
unique. The protocol is to start with $[\mathrm{G}]=[\mathrm{G}^{*}]=0$, then
increase $[\mathrm{G}]$ up to some value then increase $[\mathrm{G}^{*}]$ up
to a value much greater than $[\mathrm{G}]$ then decrease $[\mathrm{G}]$ to
zero, then decrease $[\mathrm{G}^{*}]$ to zero.

There are no reactions that convert the directional molecule to the H state in
equation 8 because this machine does not have a halting state. This lack of a
halting state is another way in which this machine differs from the standard
definition of a Turing machine.

This scheme uses a state molecule with two states, a directional molecule with
two states, a symbol molecule for each position on the main tape with three
states, and a memory molecule at each position on the memory tape with 13
states. One pair of fuel molecule species is also needed (not including the
stepping).

Figure 7: The transitions in a single step of the 2-state 3-symbol machine.
The largest in degree is four.

This naive scheme uses more memory states than necessary. Figure 7 shows that
the maximal in degree of any state is four so only $\mathrm{M}_{1}$ to
$\mathrm{M}_{4}$ are needed to distinguish the previous state of the machine.

Therefore, we only need five states for the memory molecule and we can use the
reactions:

$\displaystyle\text{A}+\text{L}+0+\mathrm{M}_{0}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+\text{R}+1+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{A}+\text{R}+0+\mathrm{M}_{0}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+\text{R}+1+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{A}+\text{L}+1+\mathrm{M}_{0}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{L}+2+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{A}+\text{R}+1+\mathrm{M}_{0}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{L}+2+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{A}+\text{L}+2+\mathrm{M}_{0}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{L}+1+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{A}+\text{R}+2+\mathrm{M}_{0}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{L}+1+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{B}+\text{L}+0+\mathrm{M}_{0}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{L}+2+\mathrm{M}_{3}+\mathrm{G}$
$\displaystyle\text{B}+\text{R}+0+\mathrm{M}_{0}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{L}+2+\mathrm{M}_{4}+\mathrm{G}$
$\displaystyle\text{B}+\text{L}+1+\mathrm{M}_{0}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+\text{R}+2+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{B}+\text{R}+1+\mathrm{M}_{0}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+\text{R}+2+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{B}+\text{L}+2+\mathrm{M}_{0}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{R}+0+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{B}+\text{R}+2+\mathrm{M}_{0}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{R}+0+\mathrm{M}_{2}+\mathrm{G}.$
(9)

This scheme uses a state molecule with two states, a directional molecule with
two states, a symbol molecule for each position on the main tape with three
states, a memory molecule at each position on the memory tape with five
states, and one pair of fuel molecule species.

Instead of a single molecule with five states we can use three molecules each
with two states. Of course, this leaves multiple unused states. Use one
molecule for direction of previous step
($\mathrm{M}_{\text{L}}$/$\mathrm{M}_{\text{R}}$), one to distinguish the
2-to-1 rules ($\mathrm{M}_{1}$/$\mathrm{M}_{2}$) and one to give reaction
direction/take place of hidden states ($\mathrm{M}_{i}$/$\mathrm{M}_{f}$). We
are free to choose the initial state of the
($\mathrm{M}_{\text{L}}$/$\mathrm{M}_{\text{R}}$) and
($\mathrm{M}_{1}$/$\mathrm{M}_{2}$) molecules so we arbitrarily choose
$\mathrm{M}_{\text{L}}$ and $\mathrm{M}_{1}$.

Therefore, reactions become:

$\displaystyle\text{A}+\text{L}+0+\mathrm{M}_{i}+\mathrm{M}_{\text{L}}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+\text{R}+1+\mathrm{M}_{f}+\mathrm{M}_{\text{L}}+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{A}+\text{R}+0+\mathrm{M}_{i}+\mathrm{M}_{\text{L}}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+\text{R}+1+\mathrm{M}_{f}+\mathrm{M}_{\text{R}}+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{A}+\text{L}+1+\mathrm{M}_{i}+\mathrm{M}_{\text{L}}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{L}+2+\mathrm{M}_{f}+\mathrm{M}_{\text{L}}+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{A}+\text{R}+1+\mathrm{M}_{i}+\mathrm{M}_{\text{L}}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{L}+2+\mathrm{M}_{f}+\mathrm{M}_{\text{R}}+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{A}+\text{L}+2+\mathrm{M}_{i}+\mathrm{M}_{\text{L}}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{L}+1+\mathrm{M}_{f}+\mathrm{M}_{\text{L}}+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{A}+\text{R}+2+\mathrm{M}_{i}+\mathrm{M}_{\text{L}}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{L}+1+\mathrm{M}_{f}+\mathrm{M}_{\text{R}}+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{B}+\text{L}+0+\mathrm{M}_{i}+\mathrm{M}_{\text{L}}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{L}+2+\mathrm{M}_{f}+\mathrm{M}_{\text{L}}+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{B}+\text{R}+0+\mathrm{M}_{i}+\mathrm{M}_{\text{L}}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{L}+2+\mathrm{M}_{f}+\mathrm{M}_{\text{R}}+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{B}+\text{L}+1+\mathrm{M}_{i}+\mathrm{M}_{\text{L}}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+\text{R}+2+\mathrm{M}_{f}+\mathrm{M}_{\text{L}}+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{B}+\text{R}+1+\mathrm{M}_{i}+\mathrm{M}_{\text{L}}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+\text{R}+2+\mathrm{M}_{f}+\mathrm{M}_{\text{R}}+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{B}+\text{L}+2+\mathrm{M}_{i}+\mathrm{M}_{\text{L}}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{R}+0+\mathrm{M}_{f}+\mathrm{M}_{\text{L}}+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{B}+\text{R}+2+\mathrm{M}_{i}+\mathrm{M}_{\text{L}}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{R}+0+\mathrm{M}_{f}+\mathrm{M}_{\text{R}}+\mathrm{M}_{1}+\mathrm{G}$
(10)

Clearly, our trade-off for reducing the number of states is to have reactions
of six molecules.

The situation can be improved because we do not need all of the molecules in
all of the reactions. We only need the $\mathrm{M}_{1}$/$\mathrm{M}_{2}$
reaction in the rule that needs it. Therefore, the reactions are:

$\displaystyle\text{A}+\text{L}+0+\mathrm{M}_{i}+\mathrm{M}_{\text{L}}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+\text{R}+1+\mathrm{M}_{f}+\mathrm{M}_{\text{L}}+\mathrm{G}$
$\displaystyle\text{A}+\text{R}+0+\mathrm{M}_{i}+\mathrm{M}_{\text{L}}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+\text{R}+1+\mathrm{M}_{f}+\mathrm{M}_{\text{R}}+\mathrm{G}$
$\displaystyle\text{A}+\text{L}+1+\mathrm{M}_{i}+\mathrm{M}_{\text{L}}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{L}+2+\mathrm{M}_{f}+\mathrm{M}_{\text{L}}+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{A}+\text{R}+1+\mathrm{M}_{i}+\mathrm{M}_{\text{L}}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{L}+2+\mathrm{M}_{f}+\mathrm{M}_{\text{R}}+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{A}+\text{L}+2+\mathrm{M}_{i}+\mathrm{M}_{\text{L}}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{L}+1+\mathrm{M}_{f}+\mathrm{M}_{\text{L}}+\mathrm{G}$
$\displaystyle\text{A}+\text{R}+2+\mathrm{M}_{i}+\mathrm{M}_{\text{L}}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{L}+1+\mathrm{M}_{f}+\mathrm{M}_{\text{R}}+\mathrm{G}$
$\displaystyle\text{B}+\text{L}+0+\mathrm{M}_{i}+\mathrm{M}_{\text{L}}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{L}+2+\mathrm{M}_{f}+\mathrm{M}_{\text{L}}+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{B}+\text{R}+0+\mathrm{M}_{i}+\mathrm{M}_{\text{L}}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{L}+2+\mathrm{M}_{f}+\mathrm{M}_{\text{R}}+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{B}+\text{L}+1+\mathrm{M}_{i}+\mathrm{M}_{\text{L}}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+\text{R}+2+\mathrm{M}_{f}+\mathrm{M}_{\text{L}}+\mathrm{G}$
$\displaystyle\text{B}+\text{R}+1+\mathrm{M}_{i}+\mathrm{M}_{\text{L}}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+\text{R}+2+\mathrm{M}_{f}+\mathrm{M}_{\text{R}}+\mathrm{G}$
$\displaystyle\text{B}+\text{L}+2+\mathrm{M}_{i}+\mathrm{M}_{\text{L}}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{R}+0+\mathrm{M}_{f}+\mathrm{M}_{\text{L}}+\mathrm{G}$
$\displaystyle\text{B}+\text{R}+2+\mathrm{M}_{i}+\mathrm{M}_{\text{L}}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+\text{R}+0+\mathrm{M}_{f}+\mathrm{M}_{\text{R}}+\mathrm{G}.$
(11)

###  C.2 4-state 6-symbol Machine

There is a trade-off between the number of head states and the number of tape
symbols neary2012complexity . The machine with the smallest number of
different transition rules, which correspond to chemical reactions, is the
four state six symbol machine from Rogozhin rogozhin1996small . The
transitions for this machine are shown in table 2. A is the initial head state
and 4 is the blank symbol.

| A | B | C | D
---|---|---|---|---
0 | A3L | B4R | C0R | D4R
1 | A2R | C2L | D3R | B5L
2 | A1L | B3R | C1R | D3R
3 | A4R | B2L | H | H
4 | A3L | B0L | A5R | B5L
5 | D4R | B1R | A0R | D1R
Table 2: The rules for Rogozhin’s universal 4 state 6 symbol machine (with
relabelled states and symbols).The letters are the states and the numbers are
the symbols. Figure 8: Graph showing one step of Rogozhin’s 4-state 6-symbol
machine. There are 5 nodes with an in degree of 4.

We see in figure 8 that the largest in degree is 4 so only 5 memory states are
required. The reactions are:

$\displaystyle\text{A}+0+\text{L}+\mathrm{M}_{0}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+3+L+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{A}+0+\text{R}+\mathrm{M}_{0}+\mathrm{M}_{2}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+3+L+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{B}+0+\text{L}+\mathrm{M}_{0}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+4+R+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{B}+0+\text{R}+\mathrm{M}_{0}+\mathrm{M}_{2}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+4+R+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{C}+0+\text{L}+\mathrm{M}_{0}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{C}+0+R+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{C}+0+\text{R}+\mathrm{M}_{0}+\mathrm{M}_{2}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{C}+0+R+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{D}+0+\text{L}+\mathrm{M}_{0}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{D}+4+R+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{D}+0+\text{R}+\mathrm{M}_{0}+\mathrm{M}_{2}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{D}+4+R+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{A}+1+\text{L}+\mathrm{M}_{0}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+2+R+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{A}+1+\text{R}+\mathrm{M}_{0}+\mathrm{M}_{2}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+2+R+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{B}+1+\text{L}+\mathrm{M}_{0}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{C}+2+L+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{B}+1+\text{R}+\mathrm{M}_{0}+\mathrm{M}_{2}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{C}+2+L+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{C}+1+\text{L}+\mathrm{M}_{0}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{D}+3+R+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{C}+1+\text{R}+\mathrm{M}_{0}+\mathrm{M}_{2}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{D}+3+R+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{D}+1+\text{L}+\mathrm{M}_{0}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+5+L+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{D}+1+\text{R}+\mathrm{M}_{0}+\mathrm{M}_{2}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+5+L+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{A}+2+\text{L}+\mathrm{M}_{0}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+1+L+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{A}+2+\text{R}+\mathrm{M}_{0}+\mathrm{M}_{2}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+1+L+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{B}+2+\text{L}+\mathrm{M}_{0}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+3+R+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{B}+2+\text{R}+\mathrm{M}_{0}+\mathrm{M}_{2}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+3+R+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{C}+2+\text{L}+\mathrm{M}_{0}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{C}+1+R+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{C}+2+\text{R}+\mathrm{M}_{0}+\mathrm{M}_{2}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{C}+1+R+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{D}+2+\text{L}+\mathrm{M}_{0}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{D}+3+R+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{D}+2+\text{R}+\mathrm{M}_{0}+\mathrm{M}_{2}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{D}+3+R+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{A}+3+\text{L}+\mathrm{M}_{0}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+4+R+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{A}+3+\text{R}+\mathrm{M}_{0}+\mathrm{M}_{2}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+4+R+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{B}+3+\text{L}+\mathrm{M}_{0}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+2+L+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{B}+3+\text{R}+\mathrm{M}_{0}+\mathrm{M}_{2}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+2+L+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{C}+3+\text{L}+\mathrm{M}_{0}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{C}+3+H+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{C}+3+\text{R}+\mathrm{M}_{0}+\mathrm{M}_{2}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{C}+3+H+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{D}+3+\text{L}+\mathrm{M}_{0}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{D}+3+H+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{D}+3+\text{R}+\mathrm{M}_{0}+\mathrm{M}_{2}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{D}+3+H+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{A}+4+\text{L}+\mathrm{M}_{0}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+3+L+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{A}+4+\text{R}+\mathrm{M}_{0}+\mathrm{M}_{2}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+3+L+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{B}+4+\text{L}+\mathrm{M}_{0}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+0+L+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{B}+4+\text{R}+\mathrm{M}_{0}+\mathrm{M}_{2}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+0+L+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{C}+4+\text{L}+\mathrm{M}_{0}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+5+R+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{C}+4+\text{R}+\mathrm{M}_{0}+\mathrm{M}_{2}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+5+R+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{D}+4+\text{L}+\mathrm{M}_{0}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+5+L+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{D}+4+\text{R}+\mathrm{M}_{0}+\mathrm{M}_{2}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+5+L+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{A}+5+\text{L}+\mathrm{M}_{0}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{D}+4+R+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{A}+5+\text{R}+\mathrm{M}_{0}+\mathrm{M}_{2}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{D}+4+R+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{B}+5+\text{L}+\mathrm{M}_{0}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+1+R+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{B}+5+\text{R}+\mathrm{M}_{0}+\mathrm{M}_{2}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{B}+1+R+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{C}+5+\text{L}+\mathrm{M}_{0}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+0+R+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{C}+5+\text{R}+\mathrm{M}_{0}+\mathrm{M}_{2}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{A}+0+R+\mathrm{M}_{2}+\mathrm{G}$
$\displaystyle\text{D}+5+\text{L}+\mathrm{M}_{0}+\mathrm{M}_{1}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{D}+1+R+\mathrm{M}_{1}+\mathrm{G}$
$\displaystyle\text{D}+5+\text{R}+\mathrm{M}_{0}+\mathrm{M}_{2}+\mathrm{G}^{*}$
$\displaystyle\rightleftharpoons\text{D}+1+R+\mathrm{M}_{2}+\mathrm{G}$

##  Appendix D Cost per time complexity

Instead of counting the number of different computations done we could instead
measure the total amount of time spent doing the computations. This is how
long all of the computations would take if run in series on a single machine.
By ‘time’ we mean not the physical time but the number of steps the Turing
machines take.

In the set of computations of interest $\mathcal{S}$ each computation $i$ has
a time to halt of $t_{i}$. As in the main text all $M$ computations in set
$\mathcal{S}$ halt within a time of $t_{M}$ so $t_{i}<t_{M}$ for the $i$ in
this set.

As in the main text the cost is $C(M,t)=\alpha(M)t+C_{0}(M)$, with $C_{0}$
representing initiation and termination costs.

The amount of time spent doing the computations in the set $\mathcal{S}_{M}$
is simply the sum of the times to halt of each of the computations

$A(M)=\sum_{\mathcal{S}_{M}}t_{i}.$ (13)

i.e. this the time multiplied by the number of machines but not counting the
time each machine spends in the halt state.

So now the quantity to be considered is the cost per amount of time spent
doing the computations $C(M,t)/A(M)$. This is the cost per useful step of a
machine. We want to know if this quantity can be made arbitrarily small by
increasing the number of computations.

The computations take at least one step of the Turing machine so the total
amount of time spent computing is lower bounded by the number of machines,
$A(M)\geq M$, so the upper bound on the cost per amount of time spend doing
the computation is the cost per computation, $C(M,t)/A(M)\leq C(M,t)/M$.
Therefore, the constraint on the set of computations is easier to satisfy than
he constraint in the main text that $\mathcal{S}_{M}$ must be such that
$t_{M}$ grows more slowly than $M^{0.5}$.

The constraint in this case is that
$\frac{\sum_{\mathcal{S}_{M}}t_{i}}{t_{M}}$ must grow more slowly than
$M^{0.5}$.