compression, complexity, and the universe
Barry Adams
I`ve a few question on how to take this very interesting
measure forward.
On 16 Nov 1997 22:41:28 GMT, cbl...@caltech.edu (Charles Bloom) wrote:
>I suggest that it is this which defines complexity.
>That is, I define "complexity" by the difference between
>the Kolmogorov Complexity (the optimal compressability,
>or the absolute minimum entropy) and the optimal
>finite-context compressibility (which the current state of
>the art is very close to). This definition has some
>very appealing properties. For example, on purely
>random data, both the Kolmogorov and Finite-Context
>compressibility is zero, so that the complexity is zero.
>On the other hand, on perfectly predictable data like
>crystals, both the Kolmogorov compressibility and the Finite-
>Context compressibility are full (one, or infinity depending
>on your conventions), so the "complexity" is again zero.
Now you`ve got a complexity measure, what can you
say about how it evolves with time. Is their a law that
complexity like entropy always increases? Its always
seemed to me that by thermodynamics the universe could
have gone from low entropy to high entropy without creating
anything interesting in the process. Yet everywhere we
see complexity, from life to weather to geology.
Is the fact that the Kolmogorov Complexity is uncomputerable
a problem with this definition.
To find the KC, the shortest computer program that generates
the data. We would need to try every computer program in
order of size, and some of these would never halt. So the
Kolmogorov Complexity for mamy sequences is unknownable.
Is their a way of finding the KC which avoids this problem?
A quantum computer might find the KC, by running
a superposition of a programs shorter than n-bit, and halting
if any of the programs replicates the data. If it hadn`t found an
after a finite time, we would know to finite probability that the
data is incompressible in n-bits. This isn`t quite the same
complextity measure however, as it is the smallest program in
memory requirement and number of steps take, not the
shortest program that may be written down.
>Now consider something more interesting, take N digits of
>the number Pi. The finite-context compressibility is very
>low - the digits seem nearly random, the output length is O(N).
>However, the Kolmogorov compressibility is very high - a
>finite program can exactly predict Pi, the output is O(1).
>The same is true for any output generated by a pseudo-random
>number generator, or encrypted text.
Surely you can`t predict the encrypted text, you might be able
to decrypt it, but the plain text would always be unknown
information.
-SNIP-
> Finally, we exhibit that our "complexity"
>models entanglement. This is the same argument Bennet uses in
>"Complexity in the Universe" :
>
>take a data set x, with high complexity 'c', and a random
>string r. Now may a new string y = x XOR r. Now r
>alone is random (non-"complex"), y alone is random, and
>x alone has complexity c. However, r and y are entangled,
>so that 'ry' together also has complexity c, since if
>we have 'ry' we can un-xor by applying r to y, to get
>r + x, and then the complexities add.
>
>if C(x) = complexity of x , we see that (C(ab) - ( C(a) + C(b) ))
>is an excellent measure of the entanglement of the systems a & b.
>Note that since any single bit has complexity zero, we can
>apply this concept recursively on any data set, to see that the
>complexity is nothing more or less than a measure of the internal
>entanglement of a data set.
This is for classical entanglement, is it also meaningful for
quantum entanglement?
Barry Adams
Henry Baker
[good stuff deleted]
> Also,
> the entropy of something like a perfect crystal, or
> anything at low temperature, is nearly zero,
Actually, this isn't correct. The 'entropy' of a 'crystal'
even at nearly zero 'temperature' is dependent upon the quality
of the crystal. One can store quite large quantities of information
in the arrangement of dopants, for example. In fact, one of the
reasons why heat engines work pretty well is that the 'degrees of
freedom' used by higher temperatures don't really store very much
information. Since the 'temperature' is related to the _change_ in
information content relative to the _change_ in energy content, this
temperature rises pretty quickly when the information capacity
doesn't increase very much. (I.e., temperature doesn't say anything
about the _absolute_ value of the information/entropy.)
Charles Bloom
>Actually, this isn't correct. The 'entropy' of a 'crystal'
>even at nearly zero 'temperature' is dependent upon the quality
>of the crystal.
Nonetheless, it is much lower than the "random" entropy.
>One can store quite large quantities of information
>in the arrangement of dopants, for example.
However, it remains that the "complexity"
as I defined it will still be zero for these crystals
UNLESS you have arranged the dopants in a very clever way,
to not just encode information, but to encode patterns
wich would not be creatable by any finite-context markov
process.
let me take this opportunity to an addendum to my notes:
-------------------------------------------------------
Note that this work on complexity and entanglement is purely
classical! The definition of complexity here (Kolmogorov
minus finite-context entropy) is somehow related to the
Shannon entropy of quantum superpositions. That is, in
classical information the Shannon entropy is additive, but
in quantum superpositions it can exhibit entanglement
differences, as the "complexity" does here.
Also note that this complexity can be used a gauge of to
what extent a system evolves non-unitarily. If we consider
the system's state to be labelled by a number in a finite
range, then the time-evolution of that number generates a
linear data file. If the system evolves unitarily, i.e.
from a classical or quantum Hamiltonian, then this data file
will be perfectly compressible by a finite context model
(note that the context need not be 1 as is typically assumed
in physics, as long as it is finite), thus the "complexity"
will be zero. However, if the evolution is governed by a
super-operator, then there is a state AB which has complexity
zero, but each state A and B have non-zero complexity, because
their evolution can exhibit finite-state patterns (a change
in A at some time t can cause a change in B, which may not
effect A again for an unbounded time; this is a finite-state
statistical influence). We can create the same situation for
classical data sets quite easily. Take a finite context machine
and generate a data set D. Take every even byte and put it
in D1, take ever odd byte and put it in D2. Then D = D1+D2 has
"complexity" zero, but D1 and D2 don't.
While I'm on the subject, it seems also that some well-known
results in compression apply nicely to physics. For example,
I have shown in an article on the Kraft inequality
("http://www.cco.caltech.edu/~bloom/news/kraft.html")
that if you compress one possible outcome by a factor F, then you
must expand another by a factor greater than F (equal to F only when F = 0).
This is very close to Physics' second law - if I take entropy out of one
bucket, I must put it somewhere else so that the total increases.
Also, it is well known (and trivial) that the space of all high-entropy
data is much (infinitely) larger than the space of all low-entropy data.
This seems to have profound implications for the final state of the universe:
if there are near-random effects that can cause jumps of the "universe
wavefunction" from one state to another, then this random walk will always
end up in a maximal-entropy state after a time long compared to the jump
frequency. This would constitute a simple proof of the arrow of time,
assuming the initial condition that the universe was in a low-entropy state.
(a black hole big bang model is indeed a very low entropy state).
---------------------------------------
Charles Bloom cbl...@caltech.edu
http://www.cco.caltech.edu/~bloom/
Charles Bloom
> Now you`ve got a complexity measure, what can you
>say about how it evolves with time. Is their a law that
>complexity like entropy always increases?
Well, in my addendum (in the reply to Henry Baker) I note
that this measure of complexity is related to the measure
of to what extent a system evolves non-unitarily, though
that isn't really your question.
Actually, the measure evolves similarly to Bennet's logical
depth measure : it is NOT constrained to always increase
like the shannon or statistical entropy. For example, when
an organism dies and decays, the "complexity" decreases;
this is intuitively appealing, and true since after decay
the statistical entropy increases, but the finite-state
correlations are destroyed, so that the finite-context
predictions become ideal.
> Is the fact that the Kolmogorov Complexity is uncomputerable
>a problem with this definition.
Well, this is indeed a trouble with practical issues. The reason
we still use the Shannon entropy so heavily is partly that the
Kolmogorov (KC) is uncomputable (except by brute force; actually the
halting problem is not too serious, you can constrain yourself
to a class of algorithms which are gauranteed to halt, and while
you may not find the true KC, data-sets for which the KC require a
"strange" algorithm are rare indeed). Anyhoo, it is theoretically
valid to talk about a quantity which is well-defined, but practically
uncomputable (Hawking,Hartle, and others have worked with the wave-
function of the universe, which is even worse than the KC!)
As an example of a simple subset for computing the KC, you could consider
the class of all finite-state machines in which a symbol is emitted in
each transition between states. Thus to find the KC of an N-bit data
set, you need only consider machines with N states, and allow them to
take N steps. This is perfectly general except for the exclusion of
steps without symbol emission. As N goes large, your error is
exponentially small.
> A quantum computer might find the KC, by running
>a superposition of a programs shorter than n-bit, and halting
>if any of the programs replicates the data.
Actually, the KC problem is identical to the general optimization
problem : reproduce the action of a program with the minimum-length
equivalent program. It seems unlikely to me that quantum computing
will shed any light on either of these problems, because they do
not admit a "finesse" solution, though of course it would be the
most interesting thing if QC could tackle the KC.
>>The same is true for any output generated by a pseudo-random
>>number generator, or encrypted text.
>
>Surely you can`t predict the encrypted text, you might be able
>to decrypt it, but the plain text would always be unknown
>information.
Right; I actually talked about this more later in the context of
undoing a "bad compressor"'s action. You may not compress the
encrypted data perfectly, but un-encrypting and then coding is
far superior to coding the encrypted (near random) data. And
you can always consider the case where the original plain text
was trivial (i.e. "xxxxxxxxx...")
>>take a data set x, with high complexity 'c', and a random
>>string r. Now may a new string y = x XOR r. Now r
>>alone is random (non-"complex"), y alone is random, and
>>x alone has complexity c. However, r and y are entangled,
>>so that 'ry' together also has complexity c, since if
>>we have 'ry' we can un-xor by applying r to y, to get
>>r + x, and then the complexities add.
>
>This is for classical entanglement, is it also meaningful for
>quantum entanglement?
This is an extremely interesting question (again see the
addendum in the reply to Henry Baker), and one I have not
fully tackled yet. It does seem that this definition of
classical entanglement mirrors the properties of the quantum
entanglement to a very large extent. That is, if I take
my classical data sets r and y far apart, and let observers
make measurements (there's no problem of decorrelation or
collapse here), they will find a "complexity" of zero - near
random data, which they can make no sense of. Only if those
observers come together can they make a "complex" data set.
However, this is dramatically different from the quantum case:
with quantum data sets, two separated observers with data sets
r and y cannot get information out of their data sets by
making measurements, even if they have a classical channel
(aka phone) to talk over. They must bring their data physically
together, to make the entangled measurements to find information.
In the classical case, a phone is just as good as being there
in person.
john baez
In article <346fd86d...@news.demon.co.uk>,
Barry Adams <bad...@adept77.demon.co.uk> wrote:
> To find the KC, the shortest computer program that generates
>the data. We would need to try every computer program in
>order of size, and some of these would never halt. So the
>Kolmogorov Complexity for many sequences is unknowable.
It's worse than this! For any finite consistent set of
axioms extending the usual axioms of arithmetic, there is
a constant K such that *no bitstring can be proved to have
Kolmogorov complexity greater than K* --- despite the fact
that all but finitely many bitstrings have Kolmogorov
complexity greater than K!
The proof is very simple and sweet, but I prefer to leave it
as an exercise. I believe one can find it in Chaitin's book.
At first it seems mindblowingly paradoxical: even though most
things are very complicated, we can't *prove* any *particular
one* has Kolmogorov complexity greater than K.
After a while you get used to it.
john baez
In article <651lm1$q3u$1...@agate.berkeley.edu>,
Aaron Bergman <aaron....@yale.edu> wrote:
>The smallest number not expressable in under ten words
Hah! This, by the way, is the key to that puzzle I laid out:
prove that there's a constant K such that no bitstring can be
proved to have algorithmic entropy greater than K.
Let me take this as an excuse to say a bit more about this.
I won't give away the answer to the puzzle; anyone who gets
stuck can find the answer in Peter Gacs' nice survey, "Lecture
notes on descriptional complexity and randomness", available at
http://www.cs.bu.edu/faculty/gacs/
In my more rhapsodic moments, I like to think of K as the
"complexity barrier". The world *seems* to be full of incredibly
complicated structures --- but the constant K sets a limit on our
ability to *prove* this. Given any string of bits, we can't rule
out the possibility that there's some clever way of printing it
out using a computer program less than K bits long. The Encyclopedia
Brittanica, the human genome, the detailed atom-by-atom recipe for
constructing a blue whale, or for that matter the entire solar system
--- we are unable to prove that a computer program less than K bits
long couldn't print these out. So we can't firmly rule out the
reductionistic dream that the whole universe evolved mechanistically
starting from a small "seed", a bitstring less than K bits long.
(Maybe it did!)
So this raises the question, how big is K?
It depends on ones axioms for mathematics.
Recall that the algorithmic entropy of a bitstring is defined
as the length of the shortest program that prints it out. For
any finite consistent first-order axiom system A exending the
usual axioms of arithmetic, let K(A) be the constant such that
no bitstring can be proved, using A, to have algorithmic entropy
greater than K(A). We can't compute K(A) exactly, but there's a
simple upper bound for it. As Gacs explains, for some constant c
we have:
K(A) < L(A) + 2 log_2 L(A) + c
where L(A) denotes the length of the axiom system A, encoded as
bits as efficiently as possible. I believe the constant c is
computable, though of course it depends on details like what
universal Turing machine you're using as your computer.
What I want to know is, how big in practice is this upper
bound on K(A)? I think it's not very big! The main problem
is to work out a bound on c.