The $5000 Compression Challenge (2001)

Nice idea, but doesn't this require a linear increase of the length of the partial files and a quadratic size of the original file?

If the length of a file is X, then in the next file you must skip the first X characters and look for a "5" that in average is in the X+128 position. So the average length of the Nth file is 128*N and if you want to reduce C bytes the size of the original file should be ~128C^2/2 (instead of the linear 128*C in the article).

Is there a link to the file that he had to compress?

Hmm. At least it's still fine to define limits of the complexity for infinite strings. That should be unique, e.g.:

lim n->\infty K(X|n)/n

Possible solutions that come tom mind:

1) UTMs are actually too powerful, and we should use a finitary abstraction to have a more sensible measure of complexity for finite strings.

2) We might need to define a kind of "relativity of complexity". This is my preferred approach and something I've thought about to some degree. That is, that we want a way of describing the complexity of something relative to our computational resources.

I expected this too, so I asked an LLM to write a quick Go program that would tell me how many bytes repeated. I created a 1.44MB file from /dev/random and then ran it through the program. Here are the bytes that repeat the most.

  Top 10 repeated byte patterns and their counts:
  Bytes: 7eda16, Count: 3
  Bytes: 65b1a4, Count: 3
  Bytes: 71d745, Count: 3
  Bytes: b72808, Count: 2
  Bytes: 60e3ee, Count: 2
  Bytes: 6e9152, Count: 2
  Bytes: 26446b, Count: 2
  Bytes: e4a05a, Count: 2
  Bytes: 67f86a, Count: 2
  Bytes: 92c487, Count: 2

Since the most common three byte sequence only appears 3 times, it seems like a non-starter. No longer byte sequences appeared more than twice either.

I generated the random digits with this:

  dd if=/dev/random of=random.bin bs=1024 count=1440

> You cannot specify the “size” of an arbitrary Turing machine

Related to compression this is, as I said, irrelevant. Kolmogorov complexity, in the first order naive sense, picks a machine then talks about length. In the complete sense, due to Kolmorogov invariance which extends the naive version to any possible encoding, it shows that there is a fundamental minimal length over any machine Then one proves that the vast majority of strings are incompressible. Withtout this machine invariance there could be no notion of inherent Kolmorogov complexity of a string.

This has all been known since the 1960s.

So no, it matters not which UTM, FSM, TM, Java, Hand coded wizard machine, or whatever you choose. This line of reasoning has been investigated decades ago and thrown out since it does not work.

Your claim

>then there exist an infinite number of UTMs that will compress any specific string

combined with your claim

> For example, suppose we have ~17k programming languages to choose from—the language selection itself encodes about 14 bits (log2(17000)) of information.

Does not let you use that information to compress the string you wish to compress, unless you're extremely lucky that the string matches the particular information in the language choice matches, say, the string prefix so you know how to use the language encoded information to apply to the string. Otherwise you need to also encode the information of how the language choice maps to the prefix (or any other part), and that information is going to be as large or larger than what you want. Your program, to reconstruct the data you think language choice hides, will have to restore that data - how does your program choice exactly do this? Does it list all 17k languages and look up the proper information? Whoops, once again your program is too big.

So no, you cannot get a free ride with this choice.

By your argument, Kolmogorov complexity (the invariance version over any possible machine) allows compression of any string, which has been proven impossible for decades.