Re: why compression doesn't perfectly even out entropy

[tcmay@got.net (Timothy C. May)]

At 9:16 PM 4/15/96, Wei Dai wrote:
>On Thu, 11 Apr 1996, Timothy C. May wrote:
>
>> That there can be no simple definition of entropy, or randomness, for an
>> arbitrary set of things, is essentially equivalent to Godel's Theorem.
>
>I think what you mean is that there is no simple way to measure
>randomness.  Simple, nice definitions of randomness do exist.  Actually

Well, I don't view any of the "simple definitions" of randomness as
especially useful; that is, the simple definitions have a kind of
circularity (implicit in the points we both make). For example, "an object
is "random" if it has no shorter description than itself," the classic
Solomonoff-Kolmogorov-Chaitin definition, is quite elegant, but doesn't
help much in many cases. Because even this definition needs to be fleshed
out, thought about, pondered, and explored, this is why I said "there can
be no simple definition of entropy, or randomness, for an arbitrary set of
things."

Maybe you would say a simple definition does exist, but that interpreting
that definition and applying it to a set of things is harder....a
difference, I think, of emphasis. I hold that in looking at some object
(set, sequence, string, etc.) and asking "Is it random?," the very question
is misleading. It may _appear_ to be random to me, or to a particular
machine which is unable to find a compression (= shorter description,
implying nonrandomness), but someone else or some other program may find
the compression.


>> (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.")
>
>A year ago, you recommended me a book by the same authors titled _An
>Introduction to Kolmogorov Complexity and Its Applications_.  Have the
>authors written a new book, or are these the same?

The same book. I rely on carbon-based memory.

By the way, Greg Chaitin has a new version of his "Universal Turing
Machine" system implemented in JavaScript. At:

http://www.research.ibm.com/people/c/chaitin/nv/index.html

(Here I rely on non-carbon-based cut-and-paste.)

--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."