\documentclass[11pt,letterpaper]{article}%
\usepackage{amsmath}
\usepackage{harvard}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=4.10.0.2347}
%TCIDATA{CSTFile=40 LaTeX article.cst}
%TCIDATA{Created=Wednesday, February 20, 2002 10:44:38}
%TCIDATA{LastRevised=Monday, January 13, 2003 11:10:01}
%TCIDATA{}
%TCIDATA{}
%TCIDATA{Language=American English}
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\begin{document}
\title{Objectivity, Information, and Maxwell's Demon\thanks{Thanks to Jos Uffink and
Janneke van Lith--van Dis for helpful discussions.}}
\author{Steven Weinstein}
\date{}
\maketitle
\begin{abstract}
This paper examines some common measures of complexity, structure, and
information, with an eye toward understanding the extent to which complexity
or information-content may be regarded as objective properties of individual
objects. A form of contextual objectivity is proposed which renders the
measures objective, and which largely resolves the puzzle of Maxwell's Demon.
\end{abstract}
\begin{quote}
\emph{An }n\emph{\ number of possible languages use the same vocabulary; in
some of them, the symbol }library\emph{\ allows the correct definition a
}ubiquitous and lasting system of hexagonal galleries\emph{, but
}library\emph{\ is }bread\emph{\ or }pyramid\emph{\ or anything else, and
these seven words which define it have another value. You who read me, are you
sure of understanding my language?} \nocite{Bor64a}(Borges 1964, 57-58)
\end{quote}
\section{Introduction}
In \emph{The Library of Babel}, the Argentinian writer Jorge Luis Borges
portrays a vast library consisting of filled with books having an identical
format of four-hundred ten pages, forty lines per page, and eighty characters
per line.
\begin{quote}
The Library is total and ... its shelves register all the possible
combinations of the twenty-odd orthographical symbols (a number which, though
extremely vast, is not infinite): Everything: the minutely detailed history of
the future, the archangels' autobiographies, the faithful catalogs of the
Library, thousands and thousands of false catalogs, the demonstration of the
fallacy of those catalogs, the demonstration of the fallacy of the true
catalog, the Gnostic gospel of Basilides, the commentary on that gospel, the
commentary on the commentary on that gospel, the true story of your death, the
translation of every book in all languages, the interpolations of every book
in all books. (Borges 1964, 52)
\end{quote}
\noindent The very idea of such a collection is mind-boggling. \ The library
clearly contains great wisdom, but it is hidden amongst sophistry, lies, and
above all, gibberish. \ Indeed, most of the volumes will contain vast
stretches of meaningless prose; meaningless, anyway, in any given language.
\ One might wonder what portion of the $\sim2\times10^{1,800,000}$ books
(assuming 25 orthographic symbols) are \emph{truly random}.\footnote{Note that
there are \textquotedblleft only\textquotedblright\ around $10^{79} $ atoms in
the known universe!} Which begs the question, what does it mean to say that a
sequence of letters is random?
Were Borges's library constructed from an alphabet of numerals, rather than
letters, a typical page from a typical book might well look something like
this:%
%TCIMACRO{\FRAME{dtbpFU}{5.4881in}{2.5322in}{0pt}{\Qcb{Figure 1}}{}%
%{random.eps}{\special{ language "Scientific Word"; type "GRAPHIC";
%maintain-aspect-ratio TRUE; display "USEDEF"; valid_file "F";
%width 5.4881in; height 2.5322in; depth 0pt; original-width 5.431in;
%original-height 2.4915in; cropleft "0"; croptop "1"; cropright "1";
%cropbottom "0"; filename 'random.EPS';file-properties "XNPEU";}}}%
%BeginExpansion
\begin{center}
\includegraphics[
natheight=2.491500in,
natwidth=5.431000in,
height=2.5322in,
width=5.4881in
]%
{random.EPS}%
\\
Figure 1
\end{center}
%EndExpansion
\noindent This is an excerpt from \emph{A Million Random Digits}, by The
Rand\ Corporation \cite{Ran55}. \ Is there really a fact of the matter as to
whether a given sequence is random?\ \ Is randomness objective? More
generally, can we quantify the \emph{complexity} of a string of symbols, or a
physical object?
\section{Shannon information}
The information theory of Claude Shannon (1948)\nocite{Sha48} provides a
method for quantifying the amount of information produced by an information
source. \ For a source emitting strings made up of an alphabet of $n$ discrete
symbols, the associated Shannon information is defined to be%
\begin{equation}
H=-\underset{i=1}{\overset{n}{\sum}}p_{i}\log p_{i}%
\end{equation}
where $p_{i}$ is the probability of occurrence of the $i$'th symbol, and where
the base of the logarithm is regarded as an arbitrary choice of
units.\footnote{Here we are assuming that the probabilities are independent;
that is, the probability of a given symbol does not depend on what symbol or
symbols preceded it.} Sometimes called the entropy (because the expression for
$H$ is formally identical to the expression for the Gibbs entropy of
statistical mechanics), this quantity is rightly said to represent the
'surprisal'\ of the source. \ That is, it tells us how much new information we
obtain when we receive an additional character. \ Thus if our alphabet has two
symbols, $X$ and $Y$, and the source is such that $X$ and $Y$ are equally
probable, we find that the information associated with the source is
$H=-(\frac{1}{2}(\log_{2}\frac{1}{2})+\frac{1}{2}(\log_{2}\frac{1}{2}))$ $=1$.
On the other hand, if the probability of $X$ is $\frac{3}{4}$ and the
probability of $Y$ is $\frac{1}{4}$, then we find that $H=-(\frac{3}{4}%
(\log_{2}\frac{3}{4})+\frac{1}{4}(\log_{2}\frac{1}{4}))$ $\approx0.81$. \ The
fact that the information content of the latter source is lower corresponds to
the fact that there is less uncertainty in the value of the next symbol --- it
is more likely to be $X$ than $Y$. The information is of course minimized if
the probability is maximally concentrated on a single symbol; it is maximized
if all symbols are equally likely. \ To the extent that one is inclined to
regard a source with typical string $XXXXX$ as `more ordered' than a source in
which a typical string has an equal number of $X$s and $Y$s, low information
content can be said to correspond to high disorder or lack of structure. \
As noted, however, the Shannon information $H$ quantifies the information
associated with a \emph{source}, rather than with any particular string
emitted by that source. \ Thus there is no way to assign a distinctive
information content to a particular string, such as $XXXXX$. \ Information
content is a property of sources, or more abstractly, of statistical ensembles
which represent the probabilistically weighted possible outputs of the source.
(The same goes for the statistical-mechanical entropy of Gibbs.) \ Thus we can
assign a Shannon information content to the Library of Babel, but we can't
assign a distinctive information content to each of the individual books.
\section{Algorithmic complexity and objectivity}
The algorithmic complexity theory of Kolmogorov (1965)\nocite{Kol65},
Solomonoff (1964)\nocite{Sol64} and Chaitin (1966)\nocite{Cha66} is an attempt
to characterize the complexity of individual strings. \ In particular, it is
claimed by some of its advocates and adherents to provide an objective
characterization of randomness, where randomness is identified with maximal
complexity. \ For example, Cover and Thomas (1991)\nocite{CT91} enthuse,
\begin{quote}
This definition of complexity turns out to be universal, that is, computer
independent, and is of fundamental importance. (p. 3)
\end{quote}
\noindent and we find Dennett (1991)\nocite{Den91} following suit, claiming that
\begin{quote}
A pattern exists in some data -- is real -- if \emph{there is} a description
of the data that is more efficient than the bit map, whether or not anyone can
concoct it. (p. 34)
\end{quote}
\noindent Dennett's use of \textquotedblleft real\textquotedblright\ here, and
his emphasis on \textquotedblleft there is\textquotedblright, suggests that
he, too, has taken on board the idea that algorithmic complexity
\emph{simpliciter }is an objective property. \ We shall see that this is not
the case.
The idea behind algorithmic complexity is simple: the complexity of a string
of symbols is the length of the shortest program on a universal Turing machine
(essentially a general-purpose computer) that will generate the string. \ Thus
a string of $10^{6}$ ones will generally have a very low algorithmic
complexity insofar as one can generate it by a program which says, in essence,
\textquotedblleft print $10^{6}$ ones and then stop.\textquotedblright\ \ On
the other a hand, a string $X_{1}X_{2}...X_{n}$ is regarded as random
(maximally complex) if the only way to generate it is with a program of the
form \textquotedblleft print `$X_{1}X_{2}...X_{n}$' and
stop.\textquotedblright\ \ In such a case, the length of the program is (for
long strings) roughly the length of the string itself.
But this is all a bit quick, for the minimum length of the program required to
generate a string depends on \emph{which} universal Turing machine is
available. \ In fact, for any finite string at all, one always design a
machine that will generate the string with a program length of $1$! \ This is
of course done by effectively building the description of the string into the
machine table (the hardware). \ Thus the complexity of a particular string is
only unambiguously defined \emph{with respect to }a particular machine.
Now it is often pointed out in discussions of this limitation that the
complexity of a given string $S$ on one machine $U_{1}$ can vary by no more
than a constant from the complexity on another machine $U_{2}$. \ Formally,%
\begin{equation}
C_{U_{2}}(S)\leq C_{U_{1}}+K(U_{1},U_{2})
\end{equation}
where $K(U_{1},U_{2})$ is a constant that encodes the length of the shortest
program that will emulate $U_{1}$ on $U_{2}$ (so that one may run the $U_{1}$
program on $U_{2}$). \ If this were an equality, rather than an inequality, we
would be in business, because this would mean that both machines would rank
all strings of a given length the same in terms of their algorithmic
complexity, differing only by the overall constant $K$. \ Indeed, this is how
the expression above is sometimes (mis)understood. \ For example, Caves
(1990)\nocite{Cav90} writes,
\begin{quote}
Algorithmic information is defined up to an additive constant, which depends
on the choice of universal computer. (p. 92)
\end{quote}
\noindent Were the above inequality an \emph{equality}, this would be correct.
\ But it isn't, and it isn't.
Sometimes one sees a similar but more qualified claim along these lines:
\begin{quote}
The constant [$K$] in the theorem may be very large. \ For example, [$U_{1}$]
may be a large computer with a large number of functions built into the
system. The computer [$U_{2}$] can be a simple microprocessor. \ The
simulation program will contain the details of the implementation of all these
functions, in fact, all the software available on the large computer. \ The
crucial point is that the length of this simulation program is independent of
the length of $x$, the string to be compressed. For sufficiently long $x$, the
length of this simulation program can be neglected, and we can discuss
Kolmogorov complexity without talking about the constants. (Cover \&\ Thomas
1991\nocite{CT91}, 148-149)
\end{quote}
\noindent This is almost, but not quite, correct. \ Given two different
machines, \emph{most} suitably long strings will not differ significantly in
their complexity, though this is only because most strings are maximally
complex.\footnote{See theorem 7.2.4 in Cover \&\ Thomas (1991)\nocite{CT91}.}
But this is not true of \emph{all} suitably long strings, for one might have
an extremely long string which has a complexity of $1$ on machine $U_{1}$ and
a complexity of $1+K$ on $U_{2}$. Furthermore, there will always be an
infinite number of \emph{other} machines which will assign an absolutely
minimal complexity to \emph{any} given string, no matter what the
length.\footnote{To construct such a machine, simply modify an existing
machine by adding an internal subroutine (a consecutively invoked sequence of
internal states) which erases the tape and writes out the desired sequence if
the initial string is a $1$ followed by a blank.}
The purportedly objective characterization of the complexity/randomness of a
single string of symbols given by algorithmic information theory turns out to
be objective only insofar as one specifies a Turing machine. \ Algorithmic
complexity \emph{simpliciter} is no more an objective property of a string
than velocity is an objective property of a physical object. \ But
\textquotedblleft objective\textquotedblright\ has a variety of meanings
(Lloyd 1995\nocite{Llo95}) and so it behooves me to spell out what I\ have in mind.
When I call $C_{U_{1}}$, the algorithmic complexity relative to a particular
machine $U_{1}$, \emph{objective}, I\ mean that it is unambiguous. \ It is
thus objective insofar as two reasonable people could not differ on its value.
\ Without specifying the machine, the context, a Mac user and a PC\ user might
quite reasonably differ! \ What starts out as an ambiguous property, whose
value depends on a certain context (the particular machine) is rendered
objective by explicitly including the context and thereby removing the ambiguity.
The concept of algorithmic complexity is similar to the concept of velocity.
\ Two people may reasonably differ on the velocity of an object, depending on
their state of motion, or on what they presumed to be the appropriate
reference frame. \ Velocity is thus not an objective property of an object,
insofar as its ambiguity (velocity relative to what?) allows reasonable people
to differ over its value. \ But \emph{relative }velocity, the velocity of an
object relative to some specific frame of reference, is of course objective,
because the ambiguity has been removed, the context specified.
\section{Thermodynamic entropy}
The concept of entropy arose in the context of thermodynamics, which is the
study of physical systems having temperatures (no surprise here!), and thus
well-defined equilibrium states. \ The state of a system in thermodynamics is
given by specifying the temperature $T$ and one or more state variables
$X,Y,...$which are understood to be stable in time, and thus \textquotedblleft
in equilibrium.\textquotedblright\ \ These variables typically come in pairs,
and satisfy one or more equations of state (hence the name `state variable').
\ Thus for a so-called `ideal gas', we have the equation of state $PV=NRT$,
where $P$ and $V$ are pressure and volume, $N$ is the number of moles of gas,
$R$ is Boltzmann's constant, and $T$, of course, is the temperature. \ Neither
$N$ nor $R$ are state variables ($R$ is not even a variable), but $P$ and $V$
are, as they correspond to quantities which can be manipulated. \
The change in entropy of a thermodynamic system is defined by $\Delta S:=\int
dQ/T$ (where the integral is taken over a reversible path in the space of
state variables). \ The entropy itself is expressible (up to a constant) as a
function of the state variables. \ For example the entropy $S$ of $N$ moles of
an ideal gas is given by
\begin{equation}
S=N\log(VT^{\frac{3}{2}})-N\log N\text{ .}%
\end{equation}
Thus if one holds the volume of $N$ moles fixed and raises the temperature,
the entropy increases. \ Or, if one maintains the temperature while allowing
the volume to increase, the entropy increases. \
Changes in entropy are subject to the Second Law of thermodynamics. \ One
version of this law reads\footnote{See Uffink (2001)\nocite{Uff01} for an
excellent discussion of the surprisingly wide variety of formulations of the
Second Law.},
\begin{quote}
The entropy $S$ of an isolated system cannot decrease.
\end{quote}
\noindent\textquotedblleft Isolated system\textquotedblright\ here means a
system which receives no energy from the environment. \ According to the
Second Law, the only way to \emph{reduce} the entropy of a thermodynamic
system is to do work on it (for example, by pushing on a piston) or to drain
heat from it (cool it).
Now suppose the system is used to do work. \ For example, suppose our system
is compressed air in a cylinder, which is allowed to push on a piston and
thereby lift a weight. \ The work done corresponds to the increase in
potential energy of the weight. \ \ It follows from the First and Second Laws
that the work done $W$ is related to the change in entropy $\Delta S$ by
\begin{equation}
W=T\Delta S.
\end{equation}
\noindent Thus work done by an isolated system means an increase in entropy.
\ Conversely, an isolated system whose entropy is constant can do no work.
While changes in entropy tell us something about how much work we can extract
from a system, entropy itself is often said to characterize the amount of
disorder in a system. \ Thus a system whose entropy is maximal is often
understood to be maximally disordered or randomized. \ Having reflected on the
objectivity and contextuality of algorithmic complexity, the question
naturally arises as to whether these are features of entropy as well.
Here is a reason to think not. \ Since the possible changes in entropy
quantify our ability to extract work from a system, there should be an
objective fact of the matter as to the difference in entropy between two
states of the system. \ In other words, entropy should be objective, in the
sense of unambiguous, up to an additive constant. \ The idea here is that
whether or not one can extract work from a system by, for example, removing a
partition, must be an objective property of the system.
Consider a system consisting of a box filled with gas with a partition down
the middle.\footnote{In what follows I draw heavily on the exposition of
Jaynes (1992)\nocite{Jay92}.} \ The temperature and pressure are identical on
both sides of the partition, and the entropy should, as far as we know, be a
function $S(T,V)$. \ Now remove the partition. \ Is there a change in the
entropy?\ \ It would seem not, and the equation above for the entropy of an
ideal gas is in line with this. \ Removing the partition makes no \emph{real}
difference, and in particular there is no loss of ability to do work when the
two sides mix. \ There was never any such ability to start with, as the
initial and final states are both states of the same, maximal entropy.
Now suppose someone else is watching, and that this someone else has special
glasses. \ To this person, the initial state is one in which the gas on one
side of the partition looks red, and that on the other side looks green.
\ This person will use a different entropy function $S(T,V,C)$ which includes
\textquotedblleft color\textquotedblright, since this person can clearly see
that there are two different gasses. This person will certainly say that the
entropy \emph{increases} after the partition is removed.
At this point, it seems ambiguous as to whether the system has undergone a
change in entropy following the removal of the partition. \ But one might
think that the individual with more complete knowledge, the one aware of the
red-green distinction, has the \emph{true} entropy. \ Further evidence for
this might be thought to come from the fact that someone who is aware of the
distinction could use this information to do work by inserting a piston made
of material which is transparent to the green gas and opaque to the red gas.
\ Such a piston would be driven by the pressure of the red gas, and this could
be harnessed to lift a weight (for example). \ So it would seem that the true
entropy is the entropy which takes in all of the physical quantities governing
the behavior of the gas.
However compelling this idea may be, it is incorrect. \ There is no
\textquotedblleft true\textquotedblright\ entropy. \ Rather, there are, as
Grad (1961)\nocite{Grad61} and Jaynes (1992)\nocite{Jay92} have argued, many
different entropies. \
Consider $N$ moles of some liquid -- it might be characterized simply by its
temperature, pressure, and volume. \ But suppose that the molecules of the
liquid have an electric dipole moment, as is the case with
nitrobenzene.\footnote{This example derives from Jaynes (1965)\nocite{Jay65}.}
\ In this case, one can change the polarization $M$ of the liquid by
manipulating an electric field $E$ (this is how a Kerr cell works). Whereas
before we had one equation of state $f(T,P,V)=0$, there will now be two
equations of state $f(T,P,V,E)=0$ and $g(T,M,E,P)=0.$ The additional state
variables mean that entropy will now be a function $S(T,V,M)$, rather than
$S(T,V)$, as before. \ Thus a sample of nitrobenzene which appears to be at
maximum entropy with respect to $V$ may or may not be at maximum entropy with
respect to $V$ and $M$. \ For instance, if there is no electric field, then
the electrons will be unpolarized. \ If there is a (uniform) electric field,
then they will tend to line up in the direction of the field. \ This
configuration will have a lower entropy than the unpolarized liquid. \
At this point, one might rightly point out that this is just the red-green
example in a more realistic guise. \ One might further insist that \emph{this}
description, the one which invokes the polarization, is the true entropy.
\ But the problem is that one can introduce further state variables as well,
not only by discovering new sorts of properties, but by \emph{manipulating the
same properties in finer detail} (for example, by applying different electric
fields to different regions of the sample). \ This process is limited only by
the fact that, at extremely small scales, the system ceases to display
equilibrium behavior. \ We do not expect the polarization of a single molecule
to have a stable value, as that molecule is vibrating due to thermal fluctuations.
In conclusion, then, the entropy depends not only on the substance, but on the
description of the substance, and there is no most-fundamental description.
\ Which description is appropriate depends on which variables one is able to
control, or interested in controlling. \ As is the case with algorithmic
complexity and relative velocity, entropy can be contextualized, and entropy
\emph{relative to a description} can be considered an objective property of a
physical system. \ But there is no most-fundamental description, just as there
is no most-fundamental Turing machine or inertial reference frame.
\section{Maxwell's demon and the objectivity of the Second Law}
Let us now return to the Second Law. \ Given that entropy is only objective
when contextualized, it would seem that the Second Law is in danger of losing
its objectivity unless it is formulated in a way that incorporates this
feature. \ This suggest the following reformulation:
\begin{quote}
The entropy $S(T,X,Y,\ldots)$ of an isolated system cannot be reduced by
manipulation of the state variables $(X,Y,\ldots)$.
\end{quote}
\noindent This version of the Second Law (akin to that of Jaynes (1992))
explicitly acknowledges the contextual aspect of entropy, its dependence on
the thermodynamic description, and furthermore gives this physical content by
making the connection between the description and the possible physical
manipulations of the system. \
Perhaps the most important thing to note about this formulation of the Second
Law is that it is a formulation which is \emph{immune} to the threat of
Maxwell's Demon (see figure 2).\ Maxwell's demon is an imaginary creature who
is able to take a box of gas at equilibrium and operate a trap door in a
partition in the box, permitting (in one of the more popular versions) the
fast molecules to go one into one side and the slow ones to go into the other.
\ This results in a decrease in entropy, in the sense that the pressure in one
side goes up, and in fact one can use this entropy difference to do work.
Coupled to a heat bath (an infinite source of heat to maintain the box of gas
at constant temperature), this cycle can go on forever, creating what is
called a `perpetual motion machine of the second kind.'%
%TCIMACRO{\FRAME{dtbpFU}{5.3895in}{3.3849in}{0pt}{\Qcb{Figure 2}}{}%
%{demon.eps}{\special{ language "Scientific Word"; type "GRAPHIC";
%maintain-aspect-ratio TRUE; display "USEDEF"; valid_file "F";
%width 5.3895in; height 3.3849in; depth 0pt; original-width 5.3333in;
%original-height 3.3382in; cropleft "0"; croptop "1"; cropright "1";
%cropbottom "0"; filename 'demon.EPS';file-properties "XNPEU";}}}%
%BeginExpansion
\begin{center}
\includegraphics[
natheight=3.338200in,
natwidth=5.333300in,
height=3.3849in,
width=5.3895in
]%
{demon.EPS}%
\\
Figure 2
\end{center}
%EndExpansion
Much ink has been spilled attempting to \textquotedblleft
exorcise\textquotedblright\ the demon (see \cite{LR90}), as it has seemed to
many (though apparently \emph{not} to Maxwell) to be a threat to the universal
validity of the Second Law.\footnote{The demon seems to have been proposed by
Maxwell (1871)\nocite{Max1871} to make a point closely related to the point I
am making in this paper. \ However, it was subsequently thought by many to
pose a threat to the Second Law.} \ Most exorcisms work on the assumption that
the demon must do work in order to reduce the entropy, thereby ensuring no net
gain of work, and thereby precluding a perpetual motion machine. \ These
exorcisms are quite problematic (Earman \&\ Norton 1998, 1999\nocite{EN98}%
\nocite{EN99}), but from the perspective of this paper, they are completely
beside the point. \ If the Second Law is formulated properly, \emph{the demon
doesn't violate the Second Law}. \ The demon is operating on a scale at which
the Second Law does not apply, for he is manipulating the system on a
microscopic level. \ The Second Law, properly understood, is a law of
\emph{thermodynamics}, and it should come as no surprise that its domain
extends only to thermodynamic variables. The demon interacts with the gas on a
scale at which the properties it is manipulating are constantly fluctuating.
To those who resist this conclusion, I would simply point out that we are not
surprised that manipulations described by quantum mechanics give rise to
phenomena which could not be achieved by classical manipulations. \ In fact,
this is the primary \emph{appeal} of the field of quantum computation:
manipulating systems on a sufficiently small scale may allow us to compute
things in polynomial time that could only be computed in exponential time on a
machine whose behavior is governed by classical mechanics (Nielsen \&\ Chuang,
2000)\nocite{NC00}. \ To be sure, there remains a compelling question at the
end of the day, which is, \textquotedblleft Can one build a perpetual motion
machine of the second kind?"\ \ However, if one could, it would not violate a
properly formulated Second Law.
\section{Conclusion}
We have taken a brief tour through some measures of complexity, structure, and
information. I have shown how two important measures, algorithmic complexity
and thermodynamic entropy, can be thought of as objective properties of,
respectively, strings of symbols and thermodynamic systems, only insofar as
they are regarded as contextual. \ In one case, we contextualize to a Turing
machine, in the other case, to a description. \ Once this is taken into
account, the apparent paradox of Maxwell's demon disappears.
\section{Acknowledgements}
Figure 2 is taken from \emph{Order and Chaos}, by Stanley W. Angrist and Loren
G. Hepler, \copyright \ 1967 by Basic Books, New York. \ Permission pending.
%\bibliographystyle{agsm}
%\bibliography{Aajour_x,harvard,main}
\begin{thebibliography}{xx}
\harvarditem{Borges}{1964}{Bor64a}
Borges, J. \harvardyearleft 1964\harvardyearright , The {L}ibrary of {B}abel,
{\em in} D.~Yates \harvardand\ J.~Irby, eds, `Labyrinths: Selected Stories
and Other Writings', New Directions, New York, pp.~51--58.
\harvarditem{Caves}{1990}{Cav90}
Caves, C. \harvardyearleft 1990\harvardyearright , Entropy and information:
how much information is needed to assign a probability, {\em in} W.~Zurek,
ed., `Complexity, Entropy and the Physics of Information, SFI Studies in the
Science of Complexity, {Vol. VIII}', Addison-Wesley, Reading, pp.~91--113.
\harvarditem{Chaitin}{1966}{Cha66}
Chaitin, G. \harvardyearleft 1966\harvardyearright , `On the length of
programs for computing binary sequences', {\em Journal of the ACM} {\bf
13},~547--569.
\harvarditem{Cover \harvardand\ Thomas}{1991}{CT91}
Cover, T. \harvardand\ Thomas, J. \harvardyearleft 1991\harvardyearright ,
{\em Elements of Information Theory}, John Wiley and Sons, New York.
\harvarditem{Dennett}{1991}{Den91}
Dennett, D. \harvardyearleft 1991\harvardyearright , `Real patterns', {\em
Journal of Philosophy} {\bf 88},~27--51.
\harvarditem{Earman \harvardand\ Norton}{1998}{EN98}
Earman, J. \harvardand\ Norton, J. \harvardyearleft 1998\harvardyearright ,
`Exorcist {X}{I}{V}: The wrath of {M}axwell's demon, part {I} -- from
{M}axwell to {S}zilard', {\em Studies in the History and Philosophy of Modern
Physics} {\bf 29},~435--471.
\harvarditem{Earman \harvardand\ Norton}{1999}{EN99}
Earman, J. \harvardand\ Norton, J. \harvardyearleft 1999\harvardyearright ,
`Exorcist {X}{I}{V}: The wrath of {M}axwell's demon, part {I}{I} -- from
{S}zilard to {L}andauer and beyond', {\em Studies in the History and
Philosophy of Modern Physics} {\bf 30},~1--40.
\harvarditem{Grad}{1961}{Grad61}
Grad, H. \harvardyearleft 1961\harvardyearright , `The many faces of entropy',
{\em Communications on Pure and Applied Mathematics} {\bf 14},~323--354.
\harvarditem{Jaynes}{1965}{Jay65}
Jaynes, E. \harvardyearleft 1965\harvardyearright , {\em Thermodynamics},
unpublished, available at http://bayes.wustl.edu/etj/thermo.html.
\harvarditem{Jaynes}{1992}{Jay92}
Jaynes, E. \harvardyearleft 1992\harvardyearright , The {G}ibbs paradox, {\em
in} `Maximum-Entropy and Bayesian Methods', Kluwer, Dordrecht.
\harvarditem{Kolmogorov}{1965}{Kol65}
Kolmogorov, A. \harvardyearleft 1965\harvardyearright , `Three approaches to
the quantitative definition of information', {\em Problems of Information
Transmission} {\bf 1},~4--7.
\harvarditem{Leff \harvardand\ Rex}{1990}{LR90}
Leff, H. \harvardand\ Rex, A. \harvardyearleft 1990\harvardyearright , {\em
Maxwell's Demon: Entropy, Information, Computing}, Princeton University
Press, Princeton, NJ.
\harvarditem{Lloyd}{1995}{Llo95}
Lloyd, E. \harvardyearleft 1995\harvardyearright , `Objectivity and the double
standard for feminist epistemologies', {\em Synthese} {\bf 194},~351--281.
\harvarditem{Maxwell}{1871}{Max1871}
Maxwell, J. \harvardyearleft 1871\harvardyearright , {\em Theory of Heat},
Longmans, Green, and Co., London.
\harvarditem{Nielsen \harvardand\ Chuang}{2000}{NC00}
Nielsen, M. \harvardand\ Chuang, I. \harvardyearleft 2000\harvardyearright ,
{\em Quantum Computation and Quantum Information}, Cambridge University
Press, Cambridge.
\harvarditem{{Rand Corporation}}{1955}{Ran55}
{Rand Corporation} \harvardyearleft 1955\harvardyearright , {\em A Million
Random Digits with 100,000 Normal Deviates}, The Free Press, Glencoe, IL.
\harvarditem{Shannon}{1958}{Sha48}
Shannon, C. \harvardyearleft 1958\harvardyearright , `A mathematical theory of
communication', {\em Bell System Technical Journal} {\bf 27},~379--423,
623--656.
\harvarditem{Solomonoff}{1964}{Sol64}
Solomonoff, R. \harvardyearleft 1964\harvardyearright , `A formal theory of
inductive inference', {\em Information and Control} {\bf 7},~1--22, 224--254.
\harvarditem{Uffink}{2001}{Uff01}
Uffink, J. \harvardyearleft 2001\harvardyearright , `Bluff your way in the
second law of thermodynamics', {\em Studies in the History and Philosophy of
Modern Physics} {\bf 32},~305--394.
\end{thebibliography}
\end{document}