From: tcmay@got.net (Timothy C. May)
Date: Sat, 13 Apr 1996 07:23:34 +0800
To: cypherpunks@toad.com
Subject: Re: why compression doesn't perfectly even out entropy
Message-ID: <ad931eee1502100491ce@[205.199.118.202]>
MIME-Version: 1.0
Content-Type: text/plain


At 5:36 AM 4/11/96, jamesd@echeque.com wrote:
>At 10:36 PM 4/9/96 -0400, JonWienke@aol.com wrote:
>> Would anyone like to propose a means of measuring entropy that we can all
>> agree on?  I haven't seen anything yet that everyone likes.
>
>Nor will you:  To measure entropy is a deep unsolved philosophical
>and physical problem.

Indeed.

That there can be no simple definition of entropy, or randomness, for an
arbitrary set of things, is essentially equivalent to Godel's Theorem.

(To forestall charges that I am relying on an all-too-common form of
bullshitting, by referring to Godel, what I mean is that "randomness" is
best defined in terms of algorithmic information theory, a la Kolmogorov
and Chaitin, and explored in Li and Vitanyi's excellent textbook,
"Algorithmic Information Theory and its Applications.")

Think of it this way: when can a set of things, a string, etc., be
_compressed_. Answer: whenever a compression is found. Most things have no
real compressions, that is, they have no shorter description than
themselves. But they _might_ have a shorter description, a compression, and
we can never say for sure that they do not. Thus, even a set which we think
is of "high entropy" (roughly, "high randomness" or "no order" or "not
compressible") may actually have some hidden order, or compressibility, not
apparent at first glance.

That we can never know when we have achieved maximum compression is a
profound result of modern mathematics and information theory.

--Tim May

Boycott "Big Brother Inside" software!
We got computers, we're tapping phone lines, we know that that ain't allowed.
---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May              | Crypto Anarchy: encryption, digital money,
tcmay@got.net  408-728-0152 | anonymous networks, digital pseudonyms, zero
W.A.S.T.E.: Corralitos, CA  | knowledge, reputations, information markets,
Higher Power: 2^756839 - 1  | black markets, collapse of governments.
"National borders aren't even speed bumps on the information superhighway."