[1] city=Vancouver, country=Canada

# The algorithmic second law of thermodynamics111This research did not receive
any specific grant from funding agencies in the public, commercial, or not-
for-profit sectors.

Aram Ebtekar<EMAIL_ADDRESS>
###### Abstract

Gács’ coarse-grained algorithmic entropy leverages universal computation to
quantify the information content of any given state. Unlike the Boltzmann and
Shannon-Gibbs entropies, it requires no prior commitment to a partition of
phase space or to probabilistic ensembles. Whereas earlier work had made loose
connections between the entropy of thermodynamic systems and information-
processing systems, the algorithmic entropy formally unifies them both. For a
close variant of Gács’ definition, we prove a very general second law of
thermodynamics, and discuss its advantages over previous formulations. Our law
is a general property of Markov processes, which can be derived as coarse-
grainings of certain time-reversible dynamical systems. Finally, taking
inspiration from Maxwell’s demon, we model an information engine powered by
compressible data.

###### keywords:

algorithmic entropy , information , nonequilibrium thermodynamics , Markov
processes

##  1 Introduction

The second law of thermodynamics is one of the most profound facts of nature,
and yet one of the most difficult to state in precise terms.

It concerns the entropy, which roughly speaking is a measure of disorder, of a
closed system, meaning a physical system that is not in contact with any other
system. A system is considered to be at a high entropy if there are a large
number of microscopic configurations that “look the same” as it. For example,
a messy room has higher entropy than a tidy room, because most possible
arrangements of a room’s contents would be considered messy, while only a few
are tidy. The difficulty of making this intuition precise lies in the need to
unambiguously classify arrangements as “messy” or “tidy”.

The second law of thermodynamics then states that the entropy can either
increase or stay the same, but never decrease. We know from experience that
rooms tend toward becoming messy, unless there is a concerted effort to clean
them. Whether or not we make such a concerted effort, our interactions with a
room involve heat-generating metabolic processes, which increase the ambient
air’s entropy by far more than any decrease due to cleaning.

We might ask whether, at least in principle, an idealized cleaner acting on an
idealized room could violate the second law. According to modern analyses of
such “Maxwell’s demon” scenarios, the minimum entropy production required to
tidy a room comes from information-processing considerations, and exactly
equals the decrease in the arrangement’s entropy [1]. In addition to rescuing
the second law, this finding hints at its fundamentally information-theoretic
nature.

Historically, such arguments have been fairly ad hoc. It’s hard to rigorously
prove a statement of the second law that’s both precise and general. We
propose that a satisfactory formulation should meet the following criteria:

  1. 1.

The law should forbid entropy from decreasing appreciably, except perhaps
extremely rarely.

  2. 2.

The law should permit entropy to increase at an appreciable rate. While it
need not increase in all situations, it should be easy to construct examples
where it does.

  3. 3.

The entropy should be well-defined up to a tiny margin of error, independent
of choice parameters such as a partition, ensemble, or macrovariables.

  4. 4.

The entropy should continue to be well-defined in nonequilibrium and
information-processing settings, without ad hoc extensions.

  5. 5.

The law should not merely predict a long-term maximum-entropy outcome; rather,
it should predict monotonic increases throughout a closed system’s evolution.

Criterion 1 is just a mild relaxation of the second law’s usual informal
statement.

Criterion 2 is violated by most fine-grained notions of entropy that take into
account the full microscopic configuration. For example, in classical
mechanics, a consequence of Liouville’s theorem is that the differential
Shannon-Gibbs entropy is exactly conserved under Hamiltonian evolutions [2].
Likewise in quantum mechanics, the von Neumann entropy is conserved under
unitary evolutions.

Later, we will discuss algorithmic entropy; however, it too is unsuitable in
its fine-grained version. The algorithmic second law suggested in Appendix C
of Zurek [3] and rigorously proved by Janzing et al. [4] fails this criterion,
as the resulting entropy increases are incredibly slow. Gács [5] explains that
since the fine-grained evolution is deterministic, the only new entropy that
can appear is that of the time variable, which is tiny. Only by coarse-
graining the state, so that the effective dynamics become stochastic, does it
become possible to generate entropy at up to the system’s Kolmogorov-Sinai
entropy rate [6, 7, 8].

Unfortunately, even in their coarse-grained forms, the classic entropies of
Boltzmann, Shannon, and Gibbs violate Criteria 3 and 4. The Boltzmann entropy
depends on a partition of the state space; in our room example, this amounts
to classifying rooms as either messy or tidy. Meanwhile, the Shannon-Gibbs
entropy is a function not of a particular physical state, but rather, of a
probability distribution, i.e., an _ensemble_ of possible states. A choice of
partition or ensemble may be motivated by considerations of equilibrium or
subjective uncertainty, neither of which is very appealing: the Universe as a
whole is certainly not in equilibrium, and subjectivity raises serious
questions regarding the source of inductive prior.

In stochastic thermodynamics [9, 10, 11] and information thermodynamics [12],
equilibrium systems (typically heat baths) are coupled to other systems,
taking the latter along Markovian trajectories to nonequilibrium probability
distributions. With enough care, the Shannon-Gibbs entropy can thus be made to
work in a variety of practical settings, including some mesoscopic and
information-processing systems. However, this approach requires a lot of
physical intuition and is hard to put on a simple foundation.

One difficulty is that there exist realistic ensembles for which the Shannon-
Gibbs entropy loses its physical meaning. Consider a device that flips a coin
to decide whether to immediately discharge a battery. The battery being full
or empty corresponds to two equilibrium distributions with distinct Shannon-
Gibbs entropies. After the coin flip, our uncertainty is modeled by a half-
half mixture of both distributions; its entropy roughly matches that of a
battery at half capacity. From this value, we would calculate that we have
half a charge worth of free energy at our disposal. Unless we have many such
batteries to average over, this result makes no practical sense: in reality,
either the battery can be consumed in full or not at all, even if we don’t yet
know which.

From a thought experiment in which compressible data is used to do physical
work, Bennett [13] argues that a fully general definition of entropy should
leverage universal computation to _infer_ the best description for any given
state. He defines the algorithmic entropy to be the length of a state’s
shortest programmatic description. Zurek [3] further develops this idea, but
retains a dependence on measurements and ensembles. Gács [5] refines the
definition to remove this dependence. While his algorithmic entropy still
depends on a choice of universal computer, the dependence is bounded by the
length of a compiler or interpreter from the code of one computer to the
other; for realistic microprocessors, this length appears to be small.

To quantify “small” in physical units, keep in mind that one bit corresponds
to $\ln 2$ times Boltzmann’s constant, or about
$9.57\text{\times}{10}^{-24}\text{\,}\mathrm{J}\text{\,}{\mathrm{K}}^{-1}$.
Thus, two languages that differ by a $12\text{\,}\mathrm{GiB}$ (i.e.,
$12\times 2^{33}$ bits) interpreter in each direction would agree to within a
picojoule per degree Kelvin; for macroscopic systems, this is a negligible
difference. Of course, our notion of a “realistic microprocessor” should
include physical size and resource constraints, to prevent directly embedding
a large interpreter program.

Regarding Criterion 4, most analyses of information-processing settings, such
as Maxwell’s demon, need to distinguish between the “physical” entropy of
thermodynamic systems and the “computational” entropy of information-
processing systems. We will rely on the insights of Gács [5], who unified the
two with his coarse-grained algorithmic entropy.

Finally, Criterion 5 distinguishes the second law from many ergodic-like
theorems. These are long-term entropy maximization laws; see Gács [5] for a
version that applies to algorithmic entropy. Attempts to interpret an ergodic-
like theorem as a second law give rise to Loschmidt’s paradox: since they
imply maximum entropy in both the infinite past and the infinite future, they
cannot imply a true time-asymmetry such as the second law. In particular, they
say nothing about how the entropy of yesterday should compare to the entropy
of tomorrow.

The fundamental laws of physics are widely believed to obey CPT symmetry: if
one reverses time, the dynamics are unchanged (aside from a reversal of charge
and parity) [14]. This can be seen, for example, in the parabolic trajectories
of objects in free fall, which look equally plausible backwards as forwards.
It’s possible for irreversibility to emerge at the macroscopic level, but only
if an initial condition breaks the symmetry. Albert [15] argued that the Big
Bang might provide the starting point, from which entropy began to increase
for all subsequent closed systems.

While this idea seems plausible, it’s extremely difficult to prove. Perhaps we
need a different kind of ergodicity, one that operates at a much faster time
scale than that required for general equilibrium. Given a suitable initial
condition, one wishes to show that the evolution forward in time has “typical”
statistics forever after. That is, the coarse-grained description should
evolve in a time-homogeneous and Markovian manner.

Gaspard [16], Nicolis and Nicolis [17], and Werndl [18] present some
deterministic time-reversible continuous-state dynamical systems, whose
coarse-grainings are shown to emulate time-homogeneous discrete-state Markov
chains, provided that their initial condition includes microscopic
randomization. The network multibaker maps of Altaner and Vollmer [19] also
have this property, but can be customized to emulate a wide variety of Markov
chains. To demonstrate the idea, we present a simplified version in A. It
remains an open question to characterize precisely which dynamical systems
exhibit Markovian coarse-grained evolutions. The present article takes
Markovian evolution for granted, substituting physical systems with their
Markov process counterparts.

_Paper outline._ To start, Section 2 reviews some notation and definitions.
Then, Section 3 presents our main contribution: the second law of
thermodynamics, for an algorithmic entropy very similar to that of Gács. Since
Gács himself did not prove a second law, this is to our knowledge the first
rigorous second law that meets all five of our criteria. We explore its
implications for doubly stochastic processes, as well as for processes coupled
to a heat bath. The latter yields an algorithmic version of the Helmholtz free
energy. The discussion in Section 4 extracts useful modeling principles from
the doubly stochastic version of the second law. We use them first to analyze
Maxwell’s demon and Landauer’s principle, and then to model an information
engine powered by compressible data. The resulting analyses are surprisingly
simple. Finally, Section 5 concludes with some possible future directions.

##  2 Preliminaries

We start with some notation. $\mathbb{R}^{+}$ denotes the non-negative real
numbers, $\mathbb{Z}^{+}$ the non-negative integers, and
$\mathbb{Z}_{m}:=\\{0,1,\ldots,m-1\\}$ the first $m$ elements of
$\mathbb{Z}^{+}$. Let $\mathcal{B}:=\\{0,1\\}$, so that $\mathcal{B}^{*}$ is
the set of binary strings. For a string $x\in\mathcal{B}^{*}$, $|x|$ denotes
its length in bits. For a set $A$, $|A|$ denotes its cardinality.
Probabilities of events are noted by $\Pr(\cdot)$. Expectations of random
variables are denoted by angled brackets $\left\langle\cdot\right\rangle$.

###  2.1 Markov processes

Fix a finite or countably infinite set of possible states $\mathcal{X}$. A
(time-homogeneous, $\mathcal{X}$-valued) Markov process is a collection of
$\mathcal{X}$-valued random variables indexed by continuous time
$(X_{t})_{t\in\mathbb{R}^{+}}$, or discrete time
$(X_{t})_{t\in\mathbb{Z}^{+}}$, satisfying the Markov property:

$s\leq t\implies\Pr(X_{t}\mid X_{\leq s})=\Pr(X_{t}\mid
X_{s})=P_{t-s}(X_{s},\,X_{t}),$

where $P_{\Delta t}:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}^{+}$ is
the transition matrix for time steps of length $\Delta t$.

A discrete-time Markov process is also called a Markov chain. Note that a
Markov chain’s joint probability distribution is uniquely determined by
$P_{1}$, along with the distribution of $X_{0}$. These two pieces are often
called the dynamics and initial condition, respectively.

A function $\pi:\mathcal{X}\rightarrow\mathbb{R}^{+}$ can be interpreted as a
discrete measure on $\mathcal{X}$. It is a semimeasure if

$\sum_{x\in\mathcal{X}}\pi(x)\leq 1,$

and a probability measure if equality holds. A transition matrix $P$ is called
$\pi$-stochastic if

$\displaystyle\forall x\in\mathcal{X},\;\sum_{y\in\mathcal{X}}P(x,\,y)$
$\displaystyle=1,$ $\displaystyle\forall
y\in\mathcal{X},\;\sum_{x\in\mathcal{X}}\pi(x)P(x,\,y)$
$\displaystyle=\pi(y).$

In this case, we also say that $\pi$ is stationary for $P$. Doubly stochastic
is a common synonym for $\sharp$-stochastic, where $\sharp$ denotes the
counting measure, i.e., $\sharp(x):=1$.

###  2.2 Description complexity

Fix a universal computer $U$ that takes self-delimiting strings as programs.
We can regard $U$ as a partial function, by letting $U(p)$ denote the output
of $U$ on a halting program $p$. Universality means that for every other such
computer $T$, there exists $x\in\mathcal{B}^{*}$ such that

$U(y,x,p)=T(y,p).$

We omit some details covered by standard references [20, 21], such as how a
tuple of strings is unambiguously encoded as a single input to $T$ or $U$.
Kolmogorov’s description complexity of a string $x\in\mathcal{B}^{*}$, given
side information $y\in\mathcal{B}^{*}$, is

$K(x\mid y):=\min_{p}\\{|p|:\,U(y,p)=x\\}.$

When $y$ is the empty string, $K(x\mid y)$ becomes the unconditional
description complexity $K(x)$. Complexities and entropies in this article are
measured in units of bits, and logarithms are assumed to have base $2$.

(In)equalities that hold up to constant additive or multiplicative factors are
expressed by writing a $+$ or $\times$ on top of the (in)equality sign. For
example, $f(x)\stackrel{{\scriptstyle+}}{{<}}g(x)$ and
$f(x)\stackrel{{\scriptstyle\times}}{{<}}g(x)$ mean $f(x)<c+g(x)$ and
$f(x)<c\cdot g(x)$, respectively, for some constant $c$. By “constant”, we
mean that $c$ is only a function of parameters that we’ve explicitly declared
as fixed, such as the universal computer $U$. We also assume a fixed string
encoding for the states in $\mathcal{X}$, so that $K(x)$ is well-defined for
$x\in\mathcal{X}$.

Properties of the description complexity are discussed in depth by Li and
Vitányi [20, §3]. Here we list just a few:

$\displaystyle\sum_{x}2^{-K(x\mid y)}<1,\qquad
K(x)\stackrel{{\scriptstyle+}}{{<}}|x|+K(|x|)\stackrel{{\scriptstyle+}}{{<}}|x|+2\log|x|,$
$\displaystyle K(x\mid
y)\stackrel{{\scriptstyle+}}{{<}}K(x)\stackrel{{\scriptstyle+}}{{<}}K(x,y)\stackrel{{\scriptstyle+}}{{=}}K(y,x)\stackrel{{\scriptstyle+}}{{=}}K(y)+K(x\mid
y,K(y))\stackrel{{\scriptstyle+}}{{<}}K(y)+K(x\mid y),$ $\displaystyle K(x\mid
A)\stackrel{{\scriptstyle+}}{{=}}\log|A|\text{ for ``most'' }x\text{ in any
computable finite set }A\subset\mathcal{B}^{*}.$

The algorithmic mutual information between $x$ and $y$ is defined by

$I(x;\,y):=K(x)+K(y)-K(x,y)\stackrel{{\scriptstyle+}}{{=}}K(x)-K(x\mid
y,K(y)).$

Since we can identify $\mathcal{B}^{*}$ with other countably infinite sets,
such as $\mathbb{Z}^{+}$, $\mathbb{Z}\times\mathbb{Z}$, $\mathbb{Q}$, and
$\mathcal{X}$, computable functions between these sets are simply functions
whose output is computed by some program supplied with the input. The
description complexity $K$ is not computable, but it’s possible to compute a
sequence that approaches it from above, so we say it is upper semicomputable.

We can extend these concepts to real-valued functions.
$f:\mathbb{Z}^{+}\rightarrow\mathbb{R}$ is said to be lower (upper)
semicomputable if there exists a computable function
$g:\mathbb{Z}^{+}\times\mathbb{Z}^{+}\rightarrow\mathbb{Q}$, such that
$g(n,\cdot)$ is monotonically increasing (decreasing), and

$\lim_{m\rightarrow\infty}g(n,m)=f(n).$

Finally, the real-valued function $f$ is computable if it is both lower and
upper semicomputable.

##  3 Theoretical results

In the analogy to classical mechanics, we think of each discrete state
$x\in\mathcal{X}$ as a coarse-grained cell in some underlying Hamiltonian
system’s phase space. If $\pi(x)$ is the Liouville volume of the corresponding
cell, then $\pi$ is a stationary measure of the coarse-grained process. With
this intuition in mind, we now adapt Gács’s coarse-grained entropy to Markov
processes. Define the algorithmic entropy $S_{\pi,P}$, relative to the
computable measure $\pi$ and the computable $\pi$-stochastic matrix $P$, by

$S_{\pi,P}(x):=K(x\mid\pi,P)+\log\pi(x).$

Here, $K(\cdot\mid\pi,P)$ refers to a conditional complexity whose side
information consists of programs that compute $\pi$ and $P$. When the
subscripts are clear from context, we may omit them and write simply $S(x)$.
The algorithmic entropy satisfies a very general second law of thermodynamics.

######  Theorem 1 (General second law of thermodynamics).

Let $X,Y$ be random variables satisfying

$\forall x,y\in\mathcal{X},\quad\Pr(Y=y\mid X=x)=P(x,\,y),$

for some computable $\pi$-stochastic matrix $P$, with $\pi$ computable and
strictly positive. Then,

$\left\langle
2^{S_{\pi,P}(X)-S_{\pi,P}(Y)}\right\rangle\stackrel{{\scriptstyle\times}}{{<}}1.$
(1)

Therefore, for $\delta>0$, with probability at least $1-\delta$,

$S_{\pi,P}(X)\stackrel{{\scriptstyle+}}{{<}}S_{\pi,P}(Y)+\log\frac{1}{\delta}.$
(2)

###### Proof.

Define the computable matrix

$Q(y,\,x):=\frac{\pi(x)}{\pi(y)}P(x,\,y),$

and the lower semicomputable function

$\mu(x):=\sum_{y}Q(y,\,x)2^{-K(y\mid\pi,P)}.$

Since $P$ is $\pi$-stochastic, substituting directly into the definition
reveals that $Q$ is as well. Consequently, we verify that $\mu$ is a discrete
semimeasure as follows:

$\sum_{x}\mu(x)=\sum_{x,y}Q(y,\,x)2^{-K(y\mid\pi,P)}=\sum_{y}2^{-K(y\mid\pi,P)}<1.$

Given descriptions of $\pi$ and $P$, a program of constant size can computably
approximate $\mu$ from below. While doing so, it can also produce an encoding
of states optimized for $\mu$; for technical details, see the proof of Theorem
4.3.3 in Li and Vitányi [20]. Hence, for all $x\in\mathcal{X}$,

$\displaystyle
K(x\mid\pi,P)\stackrel{{\scriptstyle+}}{{<}}\log\frac{1}{\mu(x)}.$

This implies $S(x)\stackrel{{\scriptstyle+}}{{<}}\log\frac{\pi(x)}{\mu(x)}$,
so that

$2^{-S(x)}\stackrel{{\scriptstyle\times}}{{>}}\frac{\mu(x)}{\pi(x)}=\sum_{y}\frac{P(x,\,y)}{\pi(y)}2^{-K(y\mid\pi,P)}=\sum_{y}P(x,y)2^{-S(y)}.$

Therefore,

$\displaystyle\left\langle 2^{S(X)-S(Y)}\right\rangle$
$\displaystyle=\sum_{x,y}\Pr(X=x)\cdot P(x,\,y)\cdot 2^{S(x)-S(y)}$
$\displaystyle=\sum_{x}\Pr(X=x)\cdot\frac{\sum_{y}P(x,y)2^{-S(y)}}{2^{-S(x)}}$
$\displaystyle\stackrel{{\scriptstyle\times}}{{<}}\sum_{x}\Pr(X=x)$
$\displaystyle=1.$

Finally, let $\delta>0$. Markov’s inequality implies that with probability at
least $1-\delta$,

$2^{S(X)-S(Y)}\stackrel{{\scriptstyle\times}}{{<}}\frac{1}{\delta},$

which can be rewritten in the desired form

$S(X)\stackrel{{\scriptstyle+}}{{<}}S(Y)+\log\frac{1}{\delta}.$

∎

If Equation 1 had an equals sign, it would be an integral fluctuation theorem
[9]. To see that this inequality must be strict, consider the case where
$\mathcal{X}$ is large but finite, $\pi=\sharp$, and the transition
probabilities are uniform. Then, even if $X$ is fixed to the state with the
lowest entropy, $Y$ would distribute uniformly over $\mathcal{X}$, making its
entropy never less, and typically much greater, than that of $X$. This example
also confirms that Theorem 1 meets our Criterion 2.

In fact, we argue that it meets all five of our criteria for a second law of
thermodynamics. To verify Criterion 1, note that the entropy increase in
Equation 2 is bounded by a constant plus $\log(1/\delta)$. The constant in the
proof, which came from the code for $\mu$, can be made small by choosing the
universal computer $U$ to be well-suited to this type of code. Moreover, even
for exponentially small $\delta$, $\log(1/\delta)$ amounts to a modest number
of bits, negligible in terms of physical units.

Criterion 3 relies on the existence of short interpreters between all
“reasonable” choices of universal computer and state encodings. While we do
not prove it rigorously, Appendix B of Zurek [3] provides arguments for its
plausibility. Criterion 4 is met as well: while Gács [5] does not prove a
proper second law, he demonstrates how algorithmic entropy simplifies the
analyses of Maxwell’s demon and Landauer’s principle. Now that we have a
second law, Section 4 revisits these thought experiments. Finally, Criterion 5
is met because our law applies to a finite transition, without resorting to
long-term asymptotics.

To apply Theorem 1 on a real system, we must choose a coarse-graining. Suppose
we choose the elements of $\mathcal{X}$ to correspond to the Boltzmann
macrostates. In other words, we measure a few macrovariables (e.g.,
temperature and pressure) to a reasonable number of significant figures, and
divide the phase space into cells corresponding to every possible measurement.
In this case, the term $K(x\mid\pi,P)$ measures the macrovariables’
description length, which is negligible. The algorithmic entropy is dominated
by the remaining term $\log\pi(x)$, which is precisely the Boltzmann entropy
of the macrostate $x$.

On the other hand, if we want to remove the dependence on macrovariables, then
we should choose a much finer coarse-graining. This time, let $\mathcal{X}$
consist of tiny cells in phase space, each of which corresponds to a truncated
specification of all the microvariables (e.g., individual particle positions
and momenta). If we choose cells of equal Liouville volume, then $\pi$ is
constant. By normalizing, we can assume $\pi=\sharp$. In this case, the term
$\log\pi(x)$ vanishes, so the algorithmic entropy is precisely the conditional
description complexity $K(x\mid\sharp,P)$.

In fact, we don’t need to condition on $\sharp$, since
$K(\sharp)\stackrel{{\scriptstyle+}}{{=}}0$. Treating the laws of physics as
fixed, we might be tempted to say $K(P)\stackrel{{\scriptstyle+}}{{=}}0$ as
well. There are two caveats: first, to keep the implied constant small, $U$
should be chosen such that it can compactly describe the laws of physics.
Second, when the laws of physics are allowed to run for arbitrary lengths of
time, $P$’s description consists not only of the laws of physics, but also the
elapsed time. With that in mind, we now specialize our second law of
thermodynamics to the doubly stochastic setting.

######  Theorem 2 (Second law for doubly stochastic Markov processes).

Fix a uniformly computable collection of doubly stochastic matrices
$(P_{\Delta t})_{t\in\mathcal{T}}$, with either $\mathcal{T}=\mathbb{R}^{+}$
or $\mathcal{T}=\mathbb{Z}^{+}$. Let $s,t\in\mathcal{T}$ be a pair of times
with $s\leq t$, and $(X_{t})_{t\in\mathcal{T}}$ be a Markov process satisfying

$\forall x,y\in\mathcal{X},\quad\Pr(X_{t}=y\mid X_{s}=x)=P_{t-s}(x,\,y).$

Then, for $\delta>0$, with probability at least $1-\delta$,

$K(X_{s})\stackrel{{\scriptstyle+}}{{<}}K(X_{t})+K(t-s)+\log\frac{1}{\delta}.$
(3)

###### Proof.

The first premise means that some fixed program computes the matrix $P_{t-s}$
as a function of the subscript $t-s$. Hence,

$K(P_{t-s})\stackrel{{\scriptstyle+}}{{<}}K(t-s).$

Meanwhile, $\log\sharp(x)=0$ and $K(\sharp)\stackrel{{\scriptstyle+}}{{=}}0$
yield

$S_{\sharp,P_{t-s}}(x)=K(x\mid\sharp,P_{t-s})\stackrel{{\scriptstyle+}}{{=}}K(x\mid
P_{t-s}).$

Theorem 1 says that with probability at least $1-\delta$,

$S(X_{s})\stackrel{{\scriptstyle+}}{{<}}S(X_{t})+\log\frac{1}{\delta},$

where we’ve omitted the subscripts for $S$. Putting it all together,

$\displaystyle K(X_{s})$
$\displaystyle\stackrel{{\scriptstyle+}}{{<}}K(X_{s}\mid P_{t-s})+K(P_{t-s})$
$\displaystyle\stackrel{{\scriptstyle+}}{{=}}S(X_{s})+K(P_{t-s})$
$\displaystyle\stackrel{{\scriptstyle+}}{{<}}S(X_{t})+K(t-s)+\log\frac{1}{\delta}$
$\displaystyle\stackrel{{\scriptstyle+}}{{=}}K(X_{t}\mid
P_{t-s})+K(t-s)+\log\frac{1}{\delta}$
$\displaystyle\stackrel{{\scriptstyle+}}{{<}}K(X_{t})+K(t-s)+\log\frac{1}{\delta}.$

∎

The term $K(t-s)$ is negligible in practice: even at the granularity of Planck
times, the age of the Universe is only about $2^{202}$. All integers in the
range $1<n<2^{202}$ have

$K(n)\stackrel{{\scriptstyle+}}{{<}}\log n+2\log\log n<202+2\cdot 8=218\text{
bits}<$2.1\text{\times}{10}^{-21}\text{\,}\mathrm{J}\text{\,}{\mathrm{K}}^{-1}$.$

Thus, for doubly stochastic processes, up to microscopic fudge terms, the
description complexity $K$ is non-decreasing. Note that the fudge terms apply
only once, so even microscopic entropy production is meaningful if repeated
sufficiently many times in a larger system, or over a longer time span.

Recall that we arrived at double stochasticity by coarse-graining a physical
system into equal-sized cells, based directly on microvariable values (see A
for an explicit construction). Each Boltzmann macrostate is then represented
not by a single cell, but by a finite set of them $B\subset\mathcal{X}$. The
Boltzmann entropy is $\log|B|$. Meanwhile, by standard properties of $K$, most
cells $x\in B$ have

$K(x)\stackrel{{\scriptstyle+}}{{=}}K(x\mid
B)\stackrel{{\scriptstyle+}}{{=}}\log|B|,$

where the first equality is due to $B$ having a short description in terms of
a few macrovariables.

More generally, $B$ need not be a classical Boltzmann macrostate; any simply
describable finite set $B\subset\mathcal{X}$ containing $x$ will do. Indeed,
for any fixed $c$ and all $x\in\mathcal{X}$,

$\displaystyle K(x)\stackrel{{\scriptstyle+}}{{<}}\min_{B\ni
x}\\{\log|B|:\,K(B)<c\\},$

since $x$ can be identified by a short description of $B$, along with a
numerical index of size $\log|B|$.

In nonprobabilistic statistics [20, §5.5] [22], the latter expression is seen
as a way to _infer_ which set $B$ best describes $x$. This flexibility extends
the applicability of entropy, to settings that are not adequately
characterized by the usual thermodynamic macrovariables. For example, to
compare the entropy between a room in a messy vs tidy state, we no longer need
to design ad hoc partitions of $\mathcal{X}$. Instead, $K$ automatically takes
into account every computable manner in which the room may be organized. Thus,
from this point onward, let’s assume an equal-size coarse-graining and take
$K$ as the definition of entropy.

We close this section with the derivation of another thermodynamic potential.
Suppose our system, with coarse-grained state space $\mathcal{X}$, is coupled
to a large heat bath at a constant temperature $T$. Then, although the
elements $x\in\mathcal{X}$ represent equal Liouville volumes, the volume
corresponding to $x$ in the _joint_ system’s phase space is no longer
constant. Instead, it’s proportional to the amount of heat bath configurations
compatible with $x$. At energy level $E(x)$, this is given by

$\pi(x)=e^{-E(x)/kT},$

up to a normalization factor. The joint system’s algorithmic entropy is

$S(x)\stackrel{{\scriptstyle+}}{{=}}K(x)+\log\pi(x)=K(x)-\frac{E(x)}{kT\ln
2}.$ (4)

To express it in units of energy, we multiply by $-kT\ln 2$. The result is an
algorithmic version of the Helmholtz free energy:

$F(x):=E(x)-K(x)\cdot kT\ln 2.$ (5)

By Theorem 1, it’s non-increasing. The free energy serves as a convenient
accounting mechanism to track changes in the total entropy, as a function of
only the state $x$ of our system. Other thermodynamic potentials are derived
in a similar manner, by a suitable coupling with an equilibrium system.

##  4 Discussion

###  4.1 Markovian dynamics

Previously, we motivated the premise of Theorem 2 in terms of coarse-
grainings. Now, we develop the same premise into a set of modeling principles
that will make our analyses much easier. Recall that we’ve fixed a binary
string encoding of the states in $\mathcal{X}$. By identifying $\mathcal{X}$
with its image in $\mathcal{B}^{*}$, and examining the state at periodic time
intervals, we may view any system as a large array of bits that evolves
according to some simply computable doubly stochastic transition matrix $P$.
By the Birkhoff-von Neumann theorem and its generalization by Révész [23],
transitioning by a doubly stochastic matrix is precisely the same as by a
probabilistic mixture of bijective mappings.

This offers an alternative to writing an explicit transition matrix: we can
instead describe the dynamics as replacing $x$ with $F(x)$, where
$F:\mathcal{X}\rightarrow\mathcal{X}$ is a _random bijection_. If we only care
to specify $F$ on a subset of $\mathcal{X}$, then it need only be a _random
injection_ whose domain and range have complements of equal cardinality, since
these can be extended to bijections on all of $\mathcal{X}$. Just as we did
for $P$, we require that the distribution of $F$ have low description
complexity.

For example, on the set $\mathcal{X}:=\mathcal{B}=\\{0,1\\}$, there are
exactly two bijections: identity and negation. Therefore, these are the only
permitted deterministic transitions. The full set of allowed transitions are
the mixtures of identity and negation, parametrized by a parameter $\alpha$:
with probability $\alpha$, the state is negated. One-to-one mappings on
subsets of $\mathcal{X}$ are also allowed: for example, we can specify that
$0$ maps to $1$ without caring what $1$ maps to (though in this case, the only
option is negation).

It may seem odd to allow so much flexibility in the distribution of $F$; after
all, the laws of physics should uniquely determine the dynamics of a closed
system. On the other hand, when systems interact, a fixed global dynamics may
emulate a variety of local dynamics. To demonstrate, consider a composite
system with state space $\mathcal{P}\times\mathcal{X}$, whose first component
is static. In other words, the system evolves according to

$(p,\,x)\mapsto(p,\,F_{p}(x)),$

where $F_{p}:\mathcal{X}\rightarrow\mathcal{X}$ is a random mapping whose
distribution depends on the control $p\in\mathcal{P}$.

It’s easy to see that the composite system’s evolution is doubly stochastic
(i.e., a mixture of bijections) if, and only if, all of the possible local
evolutions $\\{F_{p}:\,p\in\mathcal{P}\\}$ are. If an engineer sets $p$ at
initialization, then she effectively decides which dynamics $F_{p}$ apply to
the second subsystem. Since the information content of $p$ does not change,
it’s natural to omit it and consider only the subsystem that evolves according
to the chosen dynamics

$x\mapsto F_{p}(x).$

While we assumed that the composite mapping is simply distributed, each
individual $F_{p}$ might not be, since it depends on $p$. Hence, the proof of
Theorem 2 no longer applies directly to $K(\cdot)$; instead, it applies to the
conditional complexity $K(\cdot\mid p)$. We can omit all mention of $p$ only
when $K(p)$ is small. If $K(p)$ is large, then we must either use the
conditional complexity, or include $p$ as part of the state. One way that
$K(p)$ might become large is if the engineer’s choice $p$ depends on $x$. In
this case, it’s worthwhile to explicitly model the computation responsible for
setting $p$.

In addition to a fixed control, we can use a reversible program counter (i.e.,
a clock) $c\in\mathbb{Z}_{m}$:

$(c,\,x)\mapsto(c+1,\,F_{c}(x)),$

where the addition is modulo $m$. If $m$ is small, then the entropy of $c$ is
small enough to omit.

In summary, the basic model is as follows: we allow ourselves the freedom to
choose a small number of random bijections
$F_{c}:\mathcal{X}\rightarrow\mathcal{X}$ (or random injections on subsets of
$\mathcal{X}$), with simply computable distributions, to apply in cyclic
order.

###  4.2 Maxwell’s demon

Let’s apply our modeling principles to a classic thought experiment made to
test the second law [1]. Maxwell’s demon has a memory that starts in a low-
entropy “clear” state $0\in\mathcal{X}$. It interacts with a system that
starts in some high-entropy state $x\in\mathcal{X}$. In our stylized version,
let’s allow the demon to reversibly perform a complete measurement, copying
the system’s state into memory:

$(0,\,x)\mapsto(x,\,x).$

Using its measurement as a control, the demon proceeds to reversibly erase the
system’s entropy:

$(x,\,x)\mapsto(x,\,0).$

Both of these mappings are one-to-one on their respective domains,
$\\{(0,x):\,x\in\mathcal{X}\\}$ and $\\{(x,x):\,x\in\mathcal{X}\\}$.
Therefore, they can be extended to bijections on
$\mathcal{X}\times\mathcal{X}$. For deterministic bijections, Theorem 2
applies both forward and backward in time, so the pair’s entropy cannot change
substantially. Throughout the demon’s operation, it stays at about

$K(0,x)\stackrel{{\scriptstyle+}}{{=}}K(x,x)\stackrel{{\scriptstyle+}}{{=}}K(x,0)\stackrel{{\scriptstyle+}}{{=}}K(x).$

The erasure stage’s control $x$ has high entropy, so we must not omit it. If
we do, there would appear to be a violation of the second law, as the system
undergoes the erasure

$x\mapsto 0.$

We can generalize our thought experiment to a demon who performs only a
partial measurement $m(x)$, where $m$ is a (possibly random, not necessarily
bijective) function, whose distribution has low description complexity. The
demon first takes the measurement, and then uses it as a control to transition
the system from $x$ to some new (possibly random) state $y$:

$(0,\,x)\mapsto(m(x),\,x)\mapsto(m(x),\,y).$

Theorem 2 says that with high probability,
$K(m(x),\,x)\stackrel{{\scriptstyle+}}{{<}}K(m(x),\,y)$. Therefore,

$K(y)\stackrel{{\scriptstyle+}}{{>}}K(m(x),\,y)-K(m(x))\stackrel{{\scriptstyle+}}{{>}}K(m(x),\,x)-K(m(x))=K(x)-I(m(x);\,x).$

In other words, although the second law forbids a decrease in _total_ entropy,
it permits the measured system to lose as much entropy as was measured from
it! That said, the demon cannot then proceed to clear its measurement using

$(m(x),\,y)\mapsto(0,\,y),$

nor overwrite it with a new measurement

$(m(x),\,y)\mapsto(m(y),\,y),$

as these mappings are generally not one-to-one if we need them to work for all
$x$. Nor can we tailor the mappings for a specific $x$, as the resulting maps
may have high description complexity.

In summary, when $K$ is taken as the definition of entropy, we see that
Maxwell’s demon is entirely straightforward. There is no violation of the
second law, nor any need to distinguish the entropy in the memory as being of
a different type than usual.

###  4.3 Landauer’s principle

Landauer [24] discovered, as Bennett [13] later elaborated, that a computer
memory cannot be cleared without dissipating an equivalent amount of heat. The
importance of Landauer’s principle is that it puts a fundamental physical
limit on the energy-efficiency of irreversible computers. For a modern
treatment, see Frank [25].

The analysis of Landauer’s principle depends on subtle details of the setup,
so care is needed to ensure we arrive at the right conclusions. We’ve seen
that entropy inside a memory is not fundamentally different from physical
entropy. Since the total entropy cannot decrease, clearing a memory requires
that its entropy be moved to its environment.

When the entropy moves, it typically takes the form of heat energy, because
most environments have the property that the number and complexity of
available configurations increase with the amount of energy. In particular,
Equation 4 and Theorem 1 imply an energy cost of $kT\ln 2$ per bit of entropy
dumped into a heat bath. See also Neyman [26] for a larger cost that applies
when a memory is cleared by irreversible thermal equilibration.

On the other hand, there are ways to destroy data without clearing it. For
example, if the state set $\mathcal{X}$ is finite, then sampling one of the
$|\mathcal{X}|!$ bijections uniformly at random would replace the current data
$x$ with new random data $y$, leaving no hint of what $x$ was. Although $x$ is
destroyed, its entropy is replaced by that of $y$, satisfying the second law
without any heat dissipation.

The analysis changes if $x$ has a distant copy somewhere. This might occur,
for instance, if $x$ represents a measurement. Then, although it’s possible to
destroy $x$ without any immediate dissipation, doing so would necessarily
increase the joint entropy of the two systems taken together. For example, we
can replace our copy of $x$ with a random string $y$:

$(x,\,x)\mapsto(y,\,x).$

The resulting increase in entropy represents the loss of an opportunity to
clear one of the copies for free. Indeed, if the two copies are ever brought
together to interact, it would become possible to apply the joint bijection

$(x,\,x)\mapsto(0,\,x),$

leaving only one copy in need of heat dissipation to clear.

In all cases, the descriptive complexity $K$ acts as an anti-resource: once
produced, it can never be destroyed. On the other hand, we may be able to
prevent its production. A string $x$ computed by a small deterministic program
will always have low $K(x)$, no matter how random or complex it may appear.
Only when we ignore the origins of $x$ and toss it into a stochastic
environment, is entropy produced [25]. A reversible computer could in
principle avoid dissipation, clearing $x$ by running its computation in
reverse [27, 28, 29].

###  4.4 A data compression engine

In applied thermodynamics, we are often interested in transferring energy
between different systems or different forms. The rate of change of a system’s
entropy, with respect to its energy, depends on the form of energy under
consideration: it’s high for heat energy in a cold body, moderate for heat
energy in a hot body, and nearly zero for mechanical (kinetic plus potential)
energy in a macroscopic rigid body. Defining the temperature of a system’s
energy-bearing degrees of freedom by the inverse of this derivative, we may
think of mechanical energy as an especially “hot” form of energy.

The second law of thermodynamics permits energy transfers that result in a net
entropy increase, such as a mechanical source heating a hot body (via friction
or compression), or a hot body diffusing heat into a cold body. Thus,
mechanical energy is a very versatile _source_ to transfer from, while a cold
body is a very versatile energy _sink_ to transfer to. It’s more difficult to
do the opposite, e.g., to further cool an already cold body. To compensate for
the decrease in entropy when heat transfers from a cold body to a warmer
environment, a refrigeration cycle typically supplies additional heat from a
mechanical source.

From these examples, we see that energy is more useful in its “hot”, i.e.,
low-entropy, forms. This is because it’s possible to reallocate the energy in
such a way that entropy goes from low to high, but not from high to low. To be
more general, we need not speak of energy at all: the primary resource of
thermodynamics is absence of entropy. In algorithmic terms, this amounts to
the compressibility of a state $x$, which we define by $J(x):=|x|-K(x)$.

To illustrate, we model a generic “information engine” powered by compressible
strings. It has an $m$-bit memory with state space $\mathcal{B}^{m}$. Using a
computable self-delimiting encoding $n^{\prime}\in\mathcal{B}^{*}$ of the non-
negative integers $n\in\mathbb{Z}^{+}$, any string $x\in\mathcal{B}^{*}$ with
$||x|^{\prime}|+|x|\leq m$ can be encoded in memory as the concatenation of
$|x|^{\prime}$, $x$, and a padding of zeros:

$e(x):=|x|^{\prime}x0^{m-||x|^{\prime}|-|x|}\in\mathcal{B}^{m}.$

The self-delimiting prefix allows $e(x)$ to be uniquely parsed into its three
parts.

The engine is based on a lossless compression algorithm: a computable one-to-
one function $f:\mathcal{B}^{*}\rightarrow\mathcal{B}^{*}$, whose worst-case
blowup

$c:=\max_{x\in\mathcal{B}^{*}}\left\\{||f(x)|^{\prime}|+|f(x)|-||x|^{\prime}|-|x|\right\\}$

is much less than $m$. Since $f$ is one-to-one, the mapping $e(x)\mapsto
e(f(x))$, defined on the range of $e$, is also one-to-one.

If $f$ is complex, we can take it to be programmed onto a read-only section of
memory, so that the joint mapping $g:(f,\,x)\mapsto(f,\,f(x))$ is simple.
Thus, no generality is lost in assuming
$K(f)\stackrel{{\scriptstyle+}}{{=}}0$. Since $|f(x)|^{\prime}f(x)$ serves as
a self-delimiting encoding of $f(x)$,

$||f(x)|^{\prime}|+|f(x)|\stackrel{{\scriptstyle+}}{{>}}K(f(x))\stackrel{{\scriptstyle+}}{{=}}K(x).$

Therefore, $K(x)$ sets an optimistic bound on how well $f$ may compress $x$.
When the compression succeeds, the padding of zeros lengthens, serving as a
store of refined fuel for later use.

We are now ready to describe the engine’s operation. It cycles between three
modes:

  1. 1.

Consume (“burn”) refined fuel to perform some task, producing waste.

  2. 2.

Expel waste, and gather (“eat”) raw fuel in its place.

  3. 3.

Refine (“digest”) fuel, producing waste as a byproduct.

The corresponding transitions to the memory state are summarized as follows:

$e(x)\xrightarrow{\mathrm{burn}}e(xy)\xrightarrow{\mathrm{eat}}e(z)\xrightarrow{\mathrm{digest}}e(f(z))$

Here, $x$ is a small string, perhaps compressed from the previous cycle. Thus,
$e(x)$ has a large zero padding to serve as refined fuel. We’ll see shortly
how that’s used to perform useful tasks. In doing so, a portion of the padding
is replaced with some string $y$. If we expect $x$ and $y$ to be
incompressible, we treat them as waste. At the second stage, we identify a
location in the environment where we hope to find compressible strings; these
act as raw fuel. With one reversible swap, we expel $xy$, and gather the
(hopefully) compressible string $z$ in its place, with $|z|=|x|+|y|$. Finally,
the third stage refines the fuel $z$ by compressing it, yielding additional
zeros alongside the byproduct $f(z)$, which takes the role of $x$ when the
cycle resets.

If we are calling strings of zeros a “refined fuel”, then they better have
some uses; what are they? One is that they pay for the processing of bad fuel:
if the string $z$ turns out not to be compressible after all, then $f(z)$ may
actually be longer than $z$, overwriting up to $c$ of the zeros. If this
happens so often as to deplete the supply of zeros, the engine’s behavior
becomes ill-defined; in that event, we might as well consider it to have
“starved to death”.

Otherwise, zero padding is primarily used to convert irreversible (many-to-
one) operations into reversible (one-to-one) operations, which we can then
apply. Some relevant operations include irreversible computation, error-
correction, healing, and repair. Each of these maps a larger number of “bad”
states into a smaller number of “good” states. In Section 4.2, Maxwell’s demon
demonstrates the use of a cleared memory to go from $(0,\,x)$ to $(m(x),\,y)$,
when the second law would forbid directly mapping $x$ to $y$. Bennett [13]
offers the more concrete example of adiabatic demagnetization, consuming zeros
to perform energy conversions that would ordinarily violate the second law.

If the engine is part of a living organism, then it can support the organism’s
growth and reproduction. These are normally irreversible, because they
overwrite pieces of the environment with copies of the organism’s data. To
make an overwrite reversible, we first swap a chunk of zero padding from the
engine onto a desired target location. With the target location now cleared,
we can reversibly copy onto it.

###  4.5 When to use probability?

The reader might be disappointed to see that, for all the trouble we went
through to remove probabilities from the definition of entropy, we nonetheless
retained probabilities in the Markovian dynamics. The fine-grained view in A
restores determinism in the dynamics, only to reintroduce randomness in the
initial condition. The giant of probability and information theory, Andrey N
Kolmogorov [30], declared that: “Information theory must precede probability
theory, and not be based on it. By the very essence of this discipline, the
foundations of information theory have a finite combinatorial character.”

Indeed, algorithmic information theory enables us to describe nature without
granting probability a fundamental role. Instead of describing a
_distribution_ over state trajectories, we can speak of an _individual_
trajectory that appears random in the sense of Martin-Löf [31]. Roughly
speaking, this means it passes all simply computable statistical tests of
randomness.

For well-behaved distributions, Martin-Löf randomness may imply membership in
a typical set: an event accounting for the overwhelming majority of the
distribution’s probability, over which the characteristics of interest are
confined to a very narrow range. When a given sequence is a member of a
typical set, it’s convenient to describe it in terms of the corresponding
probabilistic ensemble.

Time-homogeneous dynamics are described fairly well by their typical
statistics. Physical systems whose _states_ belong to a typical set are good
candidates for an ensemble description. For example, consider the canonical
ensemble for a mechanically isolated system at thermodynamic equilibrium. On
its typical set, the algorithmic entropy is almost identical to the ensemble’s
Shannon-Gibbs entropy [3, 32]. And, unlike the algorithmic entropy, the
Shannon-Gibbs entropy is straightforward to compute. On the other hand, the
algorithmic entropy is far more general. We need it in circumstances that are
not so nicely described by simple ensembles.

##  5 Conclusions

In summary, we stated and proved a second law of thermodynamics for the
algorithmic entropy. Unlike non-algorithmic entropies, it takes into account
arbitrary computable structure in the state, thus removing any dependence on a
choice of partition or ensemble. Algorithmic entropy handles information-
processing systems on an equal footing with thermodynamic systems, without any
ad hoc adjustments. Moreover, our law applies to real incremental changes in
entropy, rather than a loose long-term tendency toward maximum entropy. To our
knowledge, our formulation is the first to satisfy our entire wishlist of
criteria for a second law. Furthermore, its premise is satisfied by the
deterministic and time-reversible systems in A.

Perhaps, the premise of Theorem 2 is even more fundamental than its
conclusion. It supposes a coarse-grained evolution that is doubly stochastic
and Markovian, forming the basis for all of our modeling throughout Section 4.
The predictions of these models agree with modern analyses of standard thought
experiments, offering both generality and precision for considerably less
effort. Their simplicity and flexibility should make them amenable to both
theory and simulation, which may yield further insights in reversible
computing and nonequilibrium thermodynamics.

We’ve shown that the Markovian premise implies the second law’s entropy non-
decrease, but we ignored its other important implications. For example, as an
alternative measure of complexity that seems more attuned to the intricate
structures of living organisms, Bennett [33] defined the logical depth of $x$
to be, roughly speaking, the minimum runtime of a shortest program that
outputs $x$. He proved that logical depth, if it increases, can only do so
slowly. Thus, logically deep objects, such as genomes, are only created by
very long computations. A third result to consider is the data processing
inequality: if two closed Markovian systems evolve independently, then their
mutual information cannot increase. In an unpublished manuscript, Ebtekar [34]
argues this inequality plays an essential role in the causal, perceptual, and
psychological arrow of time.

In future work, it would be interesting to study the interactions between
entropy non-decrease, logical depth slow-increase, and mutual information non-
decrease. Together, they seem to define the _arrow of time_ , mediating the
role of information in physics, computation, and intelligent life. Since
intelligence evolved by natural selection, a reductionist view of its purpose
might be that of optimizing compression engines of the kind in Section 4.4. In
light of the studied links between compression and inductive learning [21], it
would be interesting to see whether this drastic oversimplification predicts
nontrivial properties of intelligent agents.

## Acknowledgements

This article benefited significantly from proofreading by Xianda Sun.

##  Appendix A Markovian coarse-grainings

No discussion of the second law would be complete without addressing the
fundamental modeling assumptions responsible for the asymmetry between past
and future. The premise of Theorem 2 is a doubly stochastic time-homogeneous
Markov process. Doubly stochastic matrices that are deterministic are also
reversible, satisfying the reverse of Theorem 2. It follows that determinism
would keep the entropy approximately constant for all time.

Randomness is therefore necessary to increase entropy; however, it’s not
sufficient. Since the Markov property can be phrased in a time-symmetric
manner, negating the time index on a Markov process would yield another Markov
process [35]. The difference is that the reversed process is generally not
doubly stochastic, nor time-homogeneous [34].

This seems to match our real-life macroscopic experience, where forward
evolutions follow localized statistical laws, but backward evolutions do not.
For example, a glass in free fall will shatter at a predictable time; and
while the final arrangement of its pieces is chaotic and hard to predict, we
can expect it to follow a certain statistical distribution. Moreover, our
statistical prediction would not depend on any concurrent happenings at the
neighbor’s house.

In contrast, consider the reverse situation, where we see a broken glass and
want to retrodict its time of impact. It’s hard to make even a meaningful
statistical prediction: if we try, it will be based on principles beyond the
localized physics. For example, we might take into account the conversation at
the neighbor’s house, telling of the accident.

This example supports the claim that time-homogeneous Markov processes are
good models of the macroscopic world. On the other hand, the fundamental
microscopic laws of nature are widely believed to be deterministic and CPT
symmetric [14]. How, then, can their coarse-grained descriptions violate this
symmetry?

We demonstrate by constructing an example. Gaspard [16] defines the multibaker
map: a time-reversible dynamical system that, when suitably coarse-grained,
emulates a random walk. Altaner and Vollmer [19] generalize the multibaker map
to emulate almost arbitrary Markov chains. To convey the idea in an easy
fashion, we present multibaker maps at an intermediate level of generality.

Fix an integer $m>1$. We augment the coarse-grained state space $\mathcal{X}$
with a bi-infinite sequence of $\mathbb{Z}_{m}$-valued microvariables, so that
the complete fine-grained state space is
$\mathcal{X}\times(\mathbb{Z}_{m})^{\mathbb{Z}}$. Every individual fine-
grained state can be written in the form

$(x,\;(\ldots,\,r_{-2},\,r_{-1},\,r_{0},\,r_{1},\,r_{2},\,\ldots)),$

where $x\in\mathcal{X}$ is the coarse-grained part, and the
$r_{i}\in\mathbb{Z}_{m}$ collect the remaining hidden information.
Alternatively, we can rearrange the variables and punctuation as follows:

$(x.r_{-1}r_{-2}r_{-3}\ldots,\;0.r_{0}r_{1}r_{2}\ldots).$

The “0.” here is symbolic. If we were to identify $\mathcal{X}$ with
$\mathbb{Z}$, the latter notation is suggestive of the base $m$ representation
of a point in the two-dimensional “phase space” $\mathbb{R}\times[0,1]$. Thus,
we follow a long tradition of studying symbolic representations as a proxy for
continuous chaotic dynamical systems; see Lind and Marcus [36].

At each discrete time step, the system evolves deterministically by a
reversible shift of all the $r_{i}$, followed by a fixed bijection of
$\mathcal{X}\times\mathbb{Z}_{m}$ applied only to the pair $(x,\,r_{0})$:

$\displaystyle(x.r_{-1}r_{-2}r_{-3}\ldots,\;0.r_{0}r_{1}r_{2}\ldots)$
$\displaystyle\xrightarrow{\mathrm{shift}}\;$
$\displaystyle(x.r_{0}r_{-1}r_{-2}\ldots,\;0.r_{1}r_{2}r_{3}\ldots)$
$\displaystyle\xrightarrow{\mathrm{permute}}\;$
$\displaystyle(x^{\prime}.y^{\prime}_{0}r_{-1}r_{-2}\ldots,\;0.r_{1}r_{2}r_{3}\ldots).$

The system’s only source of randomness is its initial condition. At the start
time $t=0$, $x$ can have any distribution we choose, but the $r_{i}$ are
uniformly distributed, and all of the variables are independent. We can think
of $r_{i}$ as an $m$-sided die used to emulate a stochastic transition of $x$
at the $i$’th time step. In the coarse-grained view, where we ignore all of
the $r_{i}$, it’s easy to see that $x$’s trajectory is a doubly stochastic
time-homogeneous Markov chain, whose transition matrix entries are all
multiples of $1/m$.

In fact, our system can emulate _all_ such Markov chains, simply by choosing a
suitable bijection $T:(x,\,r_{0})\mapsto(x^{\prime},\,r_{0}^{\prime})$.
Indeed, recall that a Markov chain’s distribution is uniquely determined by
its initial condition and transition matrix. We already allow the initial
distribution of $x$ to be arbitrary, so let’s focus on the doubly stochastic
matrix $P$ that we want to emulate. Since its entries are multiples of $1/m$,
we only need to assign each pair $x,y\in\mathcal{X}$ to each other with
multiplicity $m\cdot P(x,y)$. One way to accomplish this is to fix any total
order on $\mathcal{X}$, and let

$\displaystyle
T\left(x,\;i+m\sum_{z<y}P(x,\,z)\right):=\left(y,\;i+m\sum_{z<x}P(z,\,y)\right)\quad\forall
x,y\in\mathcal{X},\,i\in\mathbb{Z}_{m\cdot P(x,y)}.$

The full construction by Altaner and Vollmer [19] relaxes the requirement that
$P$ be doubly stochastic, or that its entries have a common denominator $m$.
The unpublished manuscript by Ebtekar [34] does this in a different manner,
and provides further extensions. In particular, we can somewhat relax the
requirement that the $r_{i}$ be uniform and independent. As long as the fine-
grained state starts with a continuous distribution, it’s shown that the
dynamics eventually stabilize to become time-homogeneous and Markovian. Thus,
a continuous initial distribution may serve as Albert [15]’s _Past
Hypothesis_.

While these conclusions are only proven for our symbolic systems, they are
highly suggestive of techniques that we might hope to extend to realistic
systems. In particular, it appears that we should seek a short-term ergodic
property of the state’s microscopic part, which occurs on a much faster time
scale than macroscopic ergodicity. The goal would be to obtain fast
convergence to Markovian behavior, long before the slower but better-
understood convergence to maximum entropy. In this manner, we hope to apply
our second law of thermodynamics to real, CPT-symmetric systems.

## References

  * Maruyama et al. [2009] K. Maruyama, F. Nori, V. Vedral,  Colloquium: The physics of maxwell’s demon and information,  Reviews of Modern Physics 81 (2009) 1.
  * Carcassi and Aidala [2020] G. Carcassi, C. A. Aidala,  Hamiltonian mechanics is conservation of information entropy,  Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics 71 (2020) 60–71.
  * Zurek [1989] W. H. Zurek,  Algorithmic randomness and physical entropy,  Physical Review A 40 (1989) 4731.
  * Janzing et al. [2016] D. Janzing, R. Chaves, B. Schölkopf,  Algorithmic independence of initial condition and dynamical law in thermodynamics and causal inference,  New Journal of Physics 18 (2016) 093052.
  * Gács [1994] P. Gács,  The boltzmann entropy and randomness tests,  in: Proceedings Workshop on Physics and Computation. PhysComp’94, IEEE, 1994, pp. 209–216.
  * Latora and Baranger [1999] V. Latora, M. Baranger,  Kolmogorov-sinai entropy rate versus physical entropy,  Physical Review Letters 82 (1999) 520.
  * Einsiedler et al. [2021] M. Einsiedler, E. Lindenstrauss, T. Ward, Entropy in ergodic theory and topological dynamics, 2021. URL: https://tbward0.wixsite.com/books/entropy.
  * Gaspard [2022] P. Gaspard, The Statistical Mechanics of Irreversible Phenomena, Cambridge University Press, 2022\.
  * Seifert [2012] U. Seifert,  Stochastic thermodynamics, fluctuation theorems and molecular machines,  Reports on progress in physics 75 (2012) 126001.
  * Peliti and Pigolotti [2021] L. Peliti, S. Pigolotti, Stochastic Thermodynamics: An Introduction, Princeton University Press, 2021.
  * Shiraishi [2023] N. Shiraishi, An Introduction to Stochastic Thermodynamics: From Basic to Advanced, volume 212, Springer Nature, 2023.
  * Parrondo et al. [2015] J. M. R. Parrondo, J. M. Horowitz, T. Sagawa,  Thermodynamics of information,  Nature Physics 11 (2015) 131–139.
  * Bennett [1982] C. H. Bennett,  The thermodynamics of computation—a review,  International Journal of Theoretical Physics 21 (1982) 905–940.
  * Lehnert [2016] R. Lehnert,  Cpt symmetry and its violation,  Symmetry 8 (2016) 114.
  * Albert [2001] D. Z. Albert, Time and Chance, American Association of Physics Teachers, 2001\.
  * Gaspard [1992] P. Gaspard,  Diffusion, effusion, and chaotic scattering: An exactly solvable liouvillian dynamics,  Journal of Statistical Physics 68 (1992) 673–747.
  * Nicolis and Nicolis [1988] G. Nicolis, C. Nicolis,  Master-equation approach to deterministic chaos,  Physical review. A, General physics 38 (1988) 427–433.
  * Werndl [2009] C. Werndl,  Are deterministic descriptions and indeterministic descriptions observationally equivalent?,  Studies in history and philosophy of science part B: studies in history and philosophy of modern physics 40 (2009) 232–242.
  * Altaner and Vollmer [2012] B. Altaner, J. Vollmer,  A microscopic perspective on stochastic thermodynamics,  arXiv preprint arXiv:1212.4728 (2012).
  * Li and Vitányi [2019] M. Li, P. Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, 4 ed., 2019.
  * Hutter [2004] M. Hutter, Universal artificial intelligence: Sequential decisions based on algorithmic probability, Springer Science & Business Media, 2004\.
  * Wallace [2005] C. S. Wallace, Statistical and inductive inference by minimum message length, Springer, 2005\.
  * Révész [1962] P. Révész,  A probabilistic solution of problem 111. of g. birkhoff,  Acta Mathematica Academiae Scientiarum Hungarica 13 (1962) 187–198.
  * Landauer [1961] R. Landauer,  Irreversibility and heat generation in the computing process,  IBM journal of research and development 5 (1961) 183–191.
  * Frank [2018] M. P. Frank,  Physical foundations of landauer’s principle,  in: International Conference on Reversible Computation, Springer, 2018, pp. 3–33.
  * Neyman [1966] M. S. Neyman,  Negentropy principle in information-processing systems,  Telecommunications and Radio Engineering-USSR (1966) 68.
  * Vitányi [2005] P. Vitányi,  Time, space, and energy in reversible computing,  in: Proceedings of the 2nd conference on Computing frontiers, 2005, pp. 435–444.
  * Demaine et al. [2016] E. D. Demaine, J. Lynch, G. J. Mirano, N. Tyagi,  Energy-efficient algorithms,  in: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016, pp. 321–332.
  * Morita [2017] K. Morita, Theory of Reversible Computing, Monographs in Theoretical Computer Science. An EATCS Series, 2017\.
  * Andrey N Kolmogorov [1983] Andrey N Kolmogorov,  Combinatorial foundations of information theory and the calculus of probabilities,  Russian mathematical surveys 38 (1983) 29.
  * Martin-Löf [1966] P. Martin-Löf,  The definition of random sequences,  Information and control 9 (1966) 602–619.
  * Austern and Maleki [2019] M. Austern, A. Maleki,  On the gaussianity of kolmogorov complexity of mixing sequences,  IEEE Transactions on Information Theory 66 (2019) 1232–1247.
  * Bennett [1988] C. H. Bennett,  Logical depth and physical complexity,  1988\.
  * Ebtekar [2021] A. Ebtekar,  Information dynamics and the arrow of time (2021). arXiv:2109.09709.
  * Pearl [2009] J. Pearl, Causality, 2 ed., Cambridge university press, 2009.
  * Lind and Marcus [2021] D. Lind, B. Marcus, An Introduction to Symbolic Dynamics and Coding, 2 ed., Cambridge university press, 2021.