From: Mauricio Fernandez <mfp@...>
Date: 2007-03-23T18:59:50+09:00
Subject: Re: Just for fun...

On Fri, Mar 23, 2007 at 05:20:36PM +0900, Trans wrote:
> On Mar 22, 11:45 pm, Clifford Heath <no.s...@please.net> wrote:
> > This is a very concise statement about what's flawed in your analysis.
> > It's not just about repetition, it's about removing *whatever* is
> > predictable. All's fair when it comes to improving predictability.
> 
> Of course. When I used the term "repetition" I didn't mean to be so
> narrow as to to suggest nothing more than "a a a a a". A better term
> would have been "patterns".

(redundancy)

> Predictability is not the whole center piece of
> compression either. If it were, you couldn't get much better a
> compression of Kings James than a file with this in it:
> 
>   "http://patriot.net/~bmcgin/kjv12.txt"
> 
> Pretty predictable. That may seems silly, but there's a point. This is
> not general compression. It doesn't really matter that the process of
> decompression involves a remote machine -- locality is relative. But
> even better, if I sent you a new algorithm for compressing King James,
> and along with it the file I sent you to uncompress had only one bit
> of data in it, "1", then how can it work? Of course, the algorithm
> itself had the entire content of King James within it. Pretty
> predictable again. But not general compression. When looking at
> general compression its important to take the size of all the elements
> involved as well, including the compression algorithm itself.

Given that Kolmogorov-Chaitin complexity is not computable, what's wrong with
finding practical algorithms that approximate it? 

I don't see the intention behind your remarks: surely, any practical
compression method we come up with is going to perform worse than the optimum
one (whose performance we can only estimate... using inferior compression
methods!), so what? The existence of an uncomputable lower bound on the length
of the description of a message is no more of a deterrent to research on
better (practical) compression methods than e.g. Shannon's theorem is to
channel coding.

Regarding your remark on the choice of the universal machine and some choices
not being "general compression", you could add that even if descriptive
complexity relative to two different universal machines differs at most by a
constant term, the latter does matter when we're approximating the algorithmic
complexity in practical scenarios...

-- 
Mauricio Fernandez  -   http://eigenclass.org   -  singular Ruby
                        ** Latest postings **
Rich exception hierarchies, multiple inheritance in Ruby
  http://eigenclass.org/hiki/exception-hierarchies
Towards compatibility with Ruby 1.9: Rails, Rake, RubyGems...
  http://eigenclass.org/hiki/porting-rails-to-ruby-1.9