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