Re: [Phys-l] entropy +- disorder +- complexity

[John Denker <jsd@av8n.com>]

On 04/28/2011 09:03 AM, Stefan Jeglinski wrote:

> Perhaps different subject, but what is your suggestion as to a 
> effective analog to this (card) example in "real" thermodynamics, 
> when speaking to someone better at physics than card-sharking? (I'm 
> getting at the "peeking" more than the entropy going to zero).

1a) Maxwell daemons and Szilárd engines directly address the peeking
 issue.  The concepts involved are at the heart of thermodynamics.
 
 In a Szilárd engine, surely the particle is on one side or the other.
   a) If we don't know which side, we can't operate the engine.
   b) If we "peek" or otherwise find out which side, then we
    can operate the engine.

1b) This is intimately connected to the thermodynamics of computation,
 including reversible computation.  This is a prerequisite for
 quantum computation.


2) Spin echo experiments are another category of examples.  Compared
 to Szilárd engines, spin echo experiments are easier to carry out
 in practice.  Here the emphasis is more on /knowing/ side-information
 (rather than peeking to obtain the side-information).  Initially 
 there is a huge amount of side-information (often on the order of a 
 mole of bits) ... and then it is gradually lost.


====================

You asked for a tutorial on algorithmic information theory. That's 
a good question, but alas I don't have a comparably good answer.  I
found
  http://www.scholarpedia.org/article/Algorithmic_probability
  http://www.scholarpedia.org/article/Algorithmic_information_theory

which seem quite reasonable as far as they go, but they're perhaps 
too terse to qualify as a tutorial.  Also unless I overlooked something,
they leave out one of the interesting results:  The Solomonoff
formula for the probability is a sum of exponentials.  It turns
out that this sum is almost always well approximated by its largest
term, so this approach (which I recommend in principle) is very nearly 
equivalent to the oft-quoted approach of simply going with the single
/shortest/ description.

They cite Li and Vitányi (1997) as "the standard AIT textbook"
which might be the answer to the question.  I haven't read the
book, but it gets good reviews:
  http://www.amazon.com/Introduction-Kolmogorov-Complexity-Applications-Computer/dp/0387948686