Take the 2-minute tour ×
Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. It's 100% free, no registration required.

I really can't understand what Leonard Susskind means when he says that information is indestructible.

Is that information that is lost, through the increase of entropy really recoverable?

He himself said that entropy is hidden information. Then, although the information hidden has measurable effects, I think information lost in an irreversible process cannot be retrieved. However Susskind's claim is quite the opposite. How does one understand the loss of information by an entropy increasing process, and its connection to the statement "information is indestructible".

Black hole physics can be used in answers, but, as he proposes a general law of physics, I would prefer an answer not involving black holes.

share|improve this question
4  
The information is lost to our perception, but it's still there in the universe. –  Jeremy May 29 '12 at 16:54
14  
This is tied to the unitarity of QM evolutions. –  Raskolnikov May 29 '12 at 16:57
1  
This is very vague and impossible to answer. Is it based on a popularization? –  Ben Crowell Apr 19 '13 at 23:25
1  
@BenCrowell HDE posts a link wherein I 'm guessing Susskind makes the statement or at least one the OP renders as the post. –  WetSavannaAnimal aka Rod Vance Jul 26 '13 at 3:10
1  
The microscopic laws of physics are reversible, irreversibility appears only due to coarse graining to a larger effective scale, but the microscopic information does not get lost. The only context the question if information could get destroyed left therefore is therefore in the context of black holes which the OP does not want to hear about. But even in this case, the issue has been solved as can be read for example on [many](site:motls.blogspot.com black-hole information) TRF articles. –  Dilaton Aug 1 '13 at 12:12
show 2 more comments

5 Answers

My understanding was always that this was a result of time evolution preserving measure in state space. So we have a space of states $\mathcal{P}$ with measure $\mu$ and there is an ensemble of states in $\mathcal{P}$ distributed according to some other measure $\nu$. We also have a dynamical system discribing time evolution $f:\mathcal{P} \times \mathbb{R} \to \mathcal{P}$ where $f(p,t)$ is the state where a particle initially in state $p$ ends up after a time $t$. The crucial property of $f$ is that it preserves measure in the sense that if a small region of phase space has some phase-space volume $V$, then any time later it will have the same phase space volume $V$.

$\DeclareMathOperator{\Tr}{Tr}$Now let's look at the classical mechanics of $N$ particles in $d$ dimensions. The measure $\mu$ is given by $d \mu = d^{dN}xd^{dN}p$. The function $f(p,t)$ is determined by Hamilton's equations. We have an ensemble of states distributed according to some measure $\nu$. Usually we talk about the phase space density $\rho$ given by $d\nu = \rho d\mu$. Then the entropy is defined by $S=-\rho(p) \log \rho(p) d\mu$.

Now let's consider the time evolution of the entropy. We have $S(t)=-\int \rho(p,t) \log \rho(p,t) d\mu$. Thus we must find the time evolution of $\rho$. We have $\rho(p,t) = \frac{\rho(f^{-1}(p),0)}{\det \partial_p f(p,t)}$. But Louiville's theorem says the determinant in the denominator must be one, so $\rho(p,t) = \rho(f^{-1}(p),0)$. Now $S(t) = -\int \rho(f^{-1}(p),0) \log \rho(f^{-1}(p),0) d\mu$. Now again by Louville's theorem we can do the change of variables $f^{-1}(p) \to p$ to get $S(t)=-\int \rho(p,0) \log \rho(p,0) d\mu = S(0)$ so the entropy must be a constant.

Another case to look at is quantum mechanics. Here the phase space $\mathcal{P}$ is the space of wave functions and $\mu$ is the measure on this space (it is more complicated for infinite dimensional Hilbert spaces). The function $f$ is given by $| \psi(0) \rangle \to U(t,0)|\psi(0) \rangle$, where $U$ is the (unitary) time evolution operator. We have a distribution of states given by $\nu$ and the density matrix describing this collection of states is given by $\rho = \int |\psi \rangle \langle \psi| d \nu$. The entropy is then defined as $S = -\Tr(\rho \log \rho).$

Now let's consider the time evolution of the entropy. We have $S(t) = -\Tr(\rho(t) \log \rho(t))$. Thus we must find the time evolution of $\rho$. We have $\rho(t) = \int |\psi \rangle \langle \psi| d \nu_t$, where the subscript $t$ denotes we are talking about the distribution at the time $t$. Now since $\nu_t$ is the pushforward of $\nu_0$ under $f(\cdot, t)$, we have that $\rho(t) = \int U(t,0) |\psi \rangle \langle \psi| U^\dagger(t,0) d\nu_0=U(t,0) \int |\psi \rangle \langle \psi| d\nu_0 U^\dagger(t,0) = U(t,0) \rho(0) U^\dagger(t,0) $. Now since $\log (U(t,0) \rho(0) U^\dagger(t,0)) = U(t,0)\log (\rho(0) )U^\dagger(t,0)$, and by cyclicity of trace, we have $S(t) = -\Tr(\rho(t) \log \rho(t)) = -\Tr(\rho(0) \log \rho(0)) =S(0)$, so the entropy is constant.

Notice here that it wasn't sufficient for the dynamics to be reversible. The damped harmonic oscillator is reversible, but its entropy decreases (it gives entropy to its surroundings assuming its initial energy is much larger that $kT$). The dynamics really need to preserve volume in state space.

share|improve this answer
add comment

I'll forewarn that I'm no string theorist and Susskind's work is not therefore fully wonted to me (and likely I couldn't understand it if it were) so I do not fully know the context (of the supposed quote that entropy is hidden information).

But what he maybe means by "hidden" information is one or both of two things: the first theoretical, the second practical:

  1. The Kolmogorov complexity $K(\Omega)$ for a given system $\Omega$ (more precisely: the complexity of the system's unambiguous description) is in general not computable. $K(\Omega)$ is related to the concept of Shannon entropy $S_{Sha}(\Omega)$ (see footnote);
  2. Both a system's Kolmogorov complexity and Shannon entropy are masked from macroscopic observations by statistical correlations between microscopic components of the systems: thermodynamic systems the measurable entropy $S_{exp}(\Omega)$ (which is usually the Boltzmann) equals the true Shannon entropy $S_{Sha}(\Omega)$ plus any mutual information $M(\Omega)$ (logarithmic measure of statistical correlation) between the system's components: $S_{exp}(\Omega)= S_{Sha}(\Omega) + M(\Omega)$

Hopefully the following explanations will show you why these ideas of "hidden" are in no way related to being "destroyed" or even "unrecoverable".

A system's Kolmogorov complexity is the size (wontedly measured in bits) of the smallest possible description of the system's state. Or, as user @Johannes wonderfully put it: it's the minimum number of yes / no questions one would have to have answered to uniquely specify the system. Even if you can unambiguously and perfectly describe a system's state, there is in general no algorithm to decide whether a more compressed description can be equivalent. See the discussion of the Uncomputability theorem for a Kolmogorov complexity on Wikipedia for example. So in this sense, the true entropy of a thing is hidden from an observer, even though the thing and a perfect description of it are fully observable by them.

So much for the hiddenness of the entropy (quantity of information). But what of the information itself? Uncomputability of Kolmogorov complexity bears on this question too: given that the amount of entropy describing a system state is uncomputable, there is in general no way of telling whether that system's state has been reversibly encoded into the state of an augmented system if our original system merges with other systems: otherwise put in words more applicable to black holes: there is no algorithm that can tell whether our original system's state is encoded in the state of some other system that swallows the first one up.

For a discussion on the second point i.e. how the experimentally measured entropy and the Kolmogorov complexity differ, please see my answer at http://physics.stackexchange.com/a/71233/26076 I also discuss there why information might not be destroyed in certain simple situations, to wit: if the relevant laws of physics are reversible, then

The World has to remember in some way how to get back to any state it has evolved from (the mapping between system states at different times is one-to-one and onto).

This is a more general way of putting the unitary evolution description given in other answers.

Afterword: Charles Bennett in his paper "The thermodynamics of computation-a review" puts forward the intriguing and satisfying theory that the reason that physical chemists can't come up with a failsafe algorithm for calculating entropies of the molecules they deal with is precisely this uncomputability theorem (note that there does not rule out algorithms for certain specific cases, so the theorem can't prove that's why physical chemists can't calculate entropies, but it's highly plausible in the same sense that one could say that one reason why debugging software is a hard problem is Turing's undecidability of the halting problem theorem).

Footnote: Shannon entropy is a concept more readily applicable to systems which are thought of as belonging to a stochastic process when one has a detailed statistical description of the process. In contrast Kolmogorov complexity applies more to "descriptions" and one must define the language of the description to fully define $K(\Omega)$. Exactly how they are related (or even if either is relevant) in questions such as those addressed in the black hole information paradox is a question whose answer probably awaits further work beyond physics community "views" (as put in another answer) about whether or not information outlives the underlying matter and energy thrown into a black hole.

Another footnote (26th July 13): See also the Wikipedia page on the Berry Paradox, and a wonderful talk by Gregory Chaitin called "The Berry Paradox" and given at a Physics - Computer Science Colloquium at the University of New Mexico. The Berry Paradox introduces (albeit incompletely, but in everyday words) the beginnings of the ideas underlying Kolmogorov Complexity and indeed lead Chaitin to his independent discovery of the Kolmogorov Complexity, even though the unformalised Berry Paradox is actually ambigious. The talk also gives some poignant little examples of dealing personally with Kurt Gödel.


Edit 2nd August 2013 Answers to Prathyush's questions:

I could not understand the connection between thermodynamic entropy and kolmogorov complexity, Please can you comment on that. Esp the part "So in this sense, the true entropy of a thing is hidden from an observer, even though the thing and a perfect description of it are fully observable by them. " If you know the exact state of the system, then in physics entropy is zero, whether we can simplify the description does not come into picture

First let's try to deal with

If you know the exact state of the system, then in physics entropy is zero, whether we can simplify the description does not come into picture

Actually, whether or not there is possible simplification is central to the present problem. Suppose our description of our system $\Omega$ is $N_\Omega$ bits long. Moreover, suppose we have worked very hard to get the shortest full description we can, so we hope that $N_\Omega$ is somewhere near the Kolmogorov complexity $K(\Omega) < N_\Omega$. Along comes another "swallower" system $\Sigma$, which we study very carefully until we have what we believe is a full description of $\Sigma$, which is $N_\Sigma$ bits long. Again, we believe that $N_\Sigma$ is near $\Sigma$'s Kolmogorov complexity $K(\Sigma) < N_\Sigma$ The swallower $\Sigma$ absorbs system $\Omega$ - so the two systems merge following some physical process. Now we study our merged system very carefully, and find that somehow we can get a full description whose length $N_{\Omega \cup \Sigma}$ is much shorter than $N_\Omega + N_\Sigma$ bits long. Can we say that the merging process has been irreversible, in the sense that if we ran time backwards, the original, separated $\Omega$ and $\Sigma$ would not re-emerge? The point is we cannot, even if $N_{\Omega \cup \Sigma} \ll N_\Omega + N_\Sigma$. Why? Because we can never be sure that we truly did find the shortest possible descriptions of $\Omega$ and $\Sigma$. There is no way of telling whether $K(\Omega) = N_\Omega, K(\Sigma) = N_\Sigma$.

Ultimately what it being driven at here is the question of whether time evolutions in physics are one-to-one functions, i.e. given an ending state for a system, does this always unambiguously imply a unique beginning state? Our great central problem here is, forgive some floridity of speech, that we do not know how Nature encodes the states of her systems. Figuratively speaking, the coding scheme and codebook are what physicists make their business to work out. Kolmogorov Complexity, or related concepts, are presumed to be relevant here because it is assumed that if one truly knows how Nature works, then one knows what the maximally compressed (in the information theoretic sense) configuration space for a given system is and thus the shortest possible description of a system's state is a number that names which of the points in the configuration space a particular system is at. If the number of possible points in the ending configuration space - the ending Kolmogorov complexity (modulo an additive constant) - is less than the number of possible points in the beginning space, then we can say in general the process destroys information because two or more beginning states map to an ending state. Finding hidden order in seemingly random behaviour is a difficult problem: that fact makes cryptography work. Seemingly random sequences can be generated from exquisitely simple laws: witness Blum Blum Shub or Mersenne Twisters. We might observe seemingly random or otherwise fine structure in something and assume we have to have a hugely complicated theory to describe it, whereas Nature might be using a metaphorical Mersenne twister all along and summing up exquisite structure in a few bits in Her codebook!

Now let's try to deal with:

I could not understand the connection between thermodynamic entropy and kolmogorov complexity, Please can you comment on that.

One interpretation of the thermodynamic entropy is that it is an approximation to the "information content" the system, or the number of bits needed to wholly specify a system given only its macroscopic properties. Actually your comment "I could not understand the connection between thermodynamic entropy and kolmogorov complexity" is a very good answer to this whole question! - we don't in general know the link between the two and that thwarts efforts to know just how much information it really takes to encode a system's state unambiguously.

But the concepts are linked in some cases. The classic example here is the Boltzmann $H$-entropy for a gas made up of statistically independent particles:

$H = -\sum_i p_i \log_2 p_i$

where $p_i$ is the probability that a particle is in state number $i$. The above expression is in bits per particle (here I've just rescaled units so that the Boltzmann constant $k_B = \log_e 2$).

If indeed the particles' occupations of the states are truly random and statistically independent, then it can be shown through the Shannon Noiseless Coding Theorem that the number of bits needed to encode the states of a large number $N$ of them is precisely $H$ bits per particle. This is the minimum number of bits in the sense that if one tries to construct a code that assigns $H-\epsilon$ bits per particle then, as $N\rightarrow\infty$ the probability of coding failure approaches unity, for any $\epsilon > 0$. Conversely, if we are willing to assign $H+\epsilon$, then there always exists a code such that the probability of wholly unambiguous coding approaches unity as $N\rightarrow\infty$ for any $\epsilon > 0$. So, in this special case, the Boltzmann entropy equals the Kolmogorov complexity as $N\rightarrow\infty$: we have to choose $H+\epsilon$ bits per particle, plus a constant overhead to describe how the coding works in the language we are working with. This overhead spread over all the particles approaches nought bits per particle as $N\rightarrow\infty$.

When a thermodynamic system is at "equilibrium" and the particle state occupations statistically independent, we can plug the Boltzmann probability distribution

$p_i = \mathcal{Z}^{-1} e^{-\beta E_i}$

into the $H$ and show that it gives the same as the Clausius entropy $S_{exp}$ derived from experimental macrostates.

If there is correlation between particle occupations, similar comments in principle apply to the Gibbs's Entropy, if the joint state probability distributions are known for all the particles. However, the joint probability distributions are in general impossible to find, at least from macroscopic measurements. See the paper Gibbs vs Boltzmann Entropy by E. T. Jaynes, as well as many other works by him on this subject). Moreover, user Nathaniel of Physics Stack Exchange has an excellent PhD thesis as well as several papers which may be of interest. The difficulty of measuring the Gibbs' Entropy is yet another difficulty with this whole problem. I also gave another answer summarizing this problem.

A final way to link KC to other concepts of entropy: you can, if you like, use the notion of KC to define what we mean by "random" and "statistically independent". Motivated by the Shannon Noiseless Coding theorem, we can even use it to define probabilities. A sequence of variables is random if there is no model (no description) that can be used to describe their values other than to name their values. The degree of "randomness" in a random variable can be thought of like this: you can find a model that describes the sequence of variables somewhat - but it is only approximate. A shorter description of a random sequence is to define a model and its boundary conditions, then to code that model and conditions as well as the discrepancies between the observed variables and the model. If the model is better than guessing, this will be a pithier description than simply naming the values in full. Variables are "statistically independent" if there is no description, even in principle, that can model how the value of some variables affects the others and thus the pithiest description of the sequence is to name all the separate variables in full. This is what correlation functions between rvs do, for example: the knowledge of value of X can be used to reduce the variance of a second correlated variable Y through a linear model involving the correlation co-efficient (I mean, reduce the variance in the conditional probability distribution). Finally, we can turn the Shannon Noiseless Coding Theorem on its head and use it to define probabilities through the KC: the probability that discrete rv $X$ equals $x$ is $p$ if the following holds. Take a sequence of rvs and for each one record the sequence of truth values $X=x$" or $X\neq x$ and "find the pithiest possible description" (we shall need an "oracle" because of the uncomputability of KK) of this truth value sequence and its length in bits and bits per sequence member. The probability "p" is then the number such that $-p\log_2 p - (1-p)\log_2 (1-p)$ equals this bits per sequence member, as the sequence length $\rightarrow\infty$ (taking the limit both improves the statistical estimates and spreads the fixed length overhead in describing the coding scheme over many sequence members, so that this overhead does not contribute to the bits per sequence member). This approach gets around some of the philosophical minefield that arises in even defining randomness and probability - see the Stanford Dictionary of Philosophy entry "Chance Versus Randomness for some flavor of this.

Lastly:

If you know the exact state of the system, then in physics entropy is zero

Here our problems are the subtle distinctions (1) between an instance of an ensemble of systems, all assumed to be members of the same random process or "population" and the ensemble itself, (2) Information and Thermodynamic entropies and (3) unconditional and conditional information theoretic entropies.

When I said that "the true entropy of a thing is hidden from an observer, even though the thing and a perfect description of it are fully observable by them" well of course the information theoretic Shannon entropy, conditioned on the observer's full knowledge of the system is nought. By contrast, the thermodynamic entropy will be the same as it is for everybody. By yet another contrast, the information theoretic entropy for another observer who does not have full knowledge is nonzero. What I was driving at in this instance is the Kolmogorov Complexity, or the number of yes/no questions needed to specify a system from the same underlying statistical population, because this quantity, if it can be calculated before and after a physical process, is what one can use to tell whether the process has been reversible (in the sense of being a one-to-one function of system configuration).

I hope that these reflexions help you Prathyush on your quest to understand the indestructability, or otherwise, of information in physics.

share|improve this answer
    
Kolmogorov complexity is not "true Shannon entropy". They are two different (but related) things. –  Peter Shor Jul 17 '13 at 10:53
1  
@PeterShor Dear Peter: have another look at the discussion if you would please. I struggle with these concepts in situations like these (especially whether probabalistic ideas are even meaningful in situations like the Black Hole IP) and I don't think I'm alone. I'm simply trying to get across the notion that hidden is not the same as destroyed or even unrecoverable, and I didn't want to clutter that with other ideas too much - these deep discussions seriously test any technical writing abilities of mine. –  WetSavannaAnimal aka Rod Vance Jul 18 '13 at 4:28
1  
Downvoter: seriously? What is wrong with this as an explanation of how information might be hidden but not destroyed? Please give reasons: we might learn something from you. My understanding is that one of the main aims of this site is to share knowledge. –  WetSavannaAnimal aka Rod Vance Jul 31 '13 at 4:15
    
This is a bounty question, so more agressive downvotes can probably be explained by people playing hardball more vigorously than it is usually the case ... :-/ –  Dilaton Aug 1 '13 at 13:28
1  
I could not understand the connection between thermodynamic entropy and kolmogorov complexity, Please can you comment on that. Esp the part "So in this sense, the true entropy of a thing is hidden from an observer, even though the thing and a perfect description of it are fully observable by them. " If you know the exact state of the system, then in physics entropy is zero, whether we can simplify the description does not come into picture. –  Prathyush Aug 2 '13 at 8:46
show 6 more comments

How is the claim "information is indestructible" compatible with "information is lost in entropy"?

Let's make things as specific and as simple as possible. Let's forget about quantum physics and unitary dynamics, let's toy with utterly simple reversible cellular automata.

Consider a spacetime consisting of a square lattice of cells with a trinary (3-valued) field defined on it. The values are color-coded such that cells can be yellow, orange, and red. The 'field equations' consist of a set of allowed 2x2 colorings:

enter image description here

A total of 27 local color patterns are allowed. These are defined such that when three of the four squares are colored, the color of the fourth cell is uniquely defined. (Check this.)

The field equations don't contain a 'direction of evolution'. So how to define a timelike direction? Suppose that when looking "North" or "West" along the lattice directions, you hit a horizon beyond which an infinite sea of yellow squares stretches:

enter image description here

"North" and "West" we label as 'light rays from the past'. Given these two rays of cells, and using the field equations (the allowed 2x2 colorings), we can start reconstructing the past:

enter image description here

Here, the rule applied to color the cell follows from the square at the bottom of the center column in the overview of the 27 allowed 2x2 squares. This is the only cell out of the 27 that fits the given colors at the right, the bottom, and the bottom-right of the cell being colored.

Continuing like this, we obtain the full past up to any point we desire:

enter image description here

We notice that we constructed the full past knowing the colorings of 'light ray cells' that, excluding the uniform sea beyond the horizons, count no more than 25 cells. We identify this count as the entropy (number of trits) as observed from the point where the two light rays meet. Notice that at later times the entropy is larger: the second law of thermodynamics is honored by this simple model.

Now we reverse the dynamics, and an interesting thing happens: knowing only 9 color values of light rays to the future (again excluding the uniform sea beyond the horizon):

enter image description here

We can reconstruct the full future:

enter image description here

We refer to these 9 trits that define the full evolution of this cellular automata universe as the 'information content' of the universe. Obviously, the 25 trits of entropy do contain the 9 trits of information. This information is present but 'hidden' in the entropy trits. The entropy in this model will keep growing. The 9 trits of information remains constant and hidden in (but recoverable from) an ever larger number of entropy trits.

Many more observations can be made based on this toy model. For instance, the model does not sport a 'big bang' but rather a 'big bounce'. Furthermore, the information content (9 trits in the above example) of this big bounce being significantly smaller than the later entropy (growing without bound) is a direct consequence of a 'past horizon' being present in the model. These observations, however, go well beyond the questions asked.

share|improve this answer
2  
This post sounds so cool, but It's a little hard to follow... Can you make the reconstruction part more specific? Where are some of the numbers coming from? –  kηives Aug 1 '13 at 5:09
2  
If "entropy" is "hidden information", shouldn't the entropy be 9 trits and not 25? The 9 trits are clearly the ones that are hidden. –  Peter Shor Aug 1 '13 at 10:57
    
@Peter - correct, the information is hiding in the entropy. In the CA presented, the entropy is the number of trits that increases (25 at a given timestep, and increasing by two every timestep). The information hiding in the entropy is no more than 9 trits. PS. have corrected the leading question. –  Johannes Aug 1 '13 at 11:53
    
@kηives - have added a figure to render the reconstruction dynamics more explicit. Does this help? –  Johannes Aug 1 '13 at 11:56
1  
Thank you Prathyush. And thank you for reviving this thread. It was fun working out this toy model and turning it into an "entropy growing universe". –  Johannes Aug 2 '13 at 16:12
show 3 more comments

Like many people have said here, he's probably talking about unitarity. Susskind is echoing the general view among physicists. I don't think we have (yet) a concrete way to even precisely formulate the principle, leave alone any kind of proof. But based on unitarity in quantum mechanics and (for what it's worth) physical intuition about gravity, it seems like the sensible thing would be for information content to be conserved.

A simple illustration of this principle would be the no-cloning theorem. The way I see it, it says that you can't destroy the information in the register (the qubit into which you cant to copy some information) in a way consistent with unitary evolution. If you managed to do it, then you should be able to invert the unitary evolution and generate the information from the register which you're supposed to have destroyed.

As for hidden information, think of it as being temporarily hidden. When some information is inside the black hole, you can't access that information and the black hole has a corresponding entropy. When the black hole evaporates away, there is nothing left to contain the entropy, so the information must have been sent out somehow and it's now un-hidden (or so it's believed, as of today). Again, I don't think there's a concrete calculation to establish this definitively -- mainly since we don't have a good handle on quantum gravity.

share|improve this answer
add comment

I don't know in which context Susskind mentioned this, but he probably meant time evolution is unitary. That means, among other things, that it's reversible, ie no information can ever get lost because you can essentially, starting from any time (time-like slice), run time backwards (theoretically) and compute what happened earlier.

If black hole evolution was indeed perfectly thermal, it would violate unitarity and information would be lost indeed. Susskind, I believe, thinks that this is not the case.

share|improve this answer
    
What I've tried to highlight in my question is the fact that in practice you can not compute it, and I am not talking only about the impossibility of 'compute measurements' but even for quantum state (of an enough complex real system) because it has to be specified then you will need measurements to start with, so the whole state will be neither computable. The statement "information is indestructible" is a strange one, I would like to understand what it refers to, My question is how an 'hypothetical information' not recoverable by any mean can be still called information? –  HDE May 30 '12 at 12:33
    
I think you're reading too much into words. As I said, I guess he was probably just talking about unitarity. –  WIMP Dec 24 '12 at 10:46
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.