Kolmogorov Complexity and Compression Distance (2023) (opens in new tab)

> you cannot by any strategy make money on betting on the outcomes

What does "strategy" mean here? I might just happen to have a strategy which involves betting on the exact sequence of heads and tails in a given sequence. The analogy in terms of languages is that my language might just happen to have a short keyword that represents a given sequence of heads and tails.

I don't know much about Kolmogorow complexity so I'm certainly missing something here. Potentially there is a subtle clause in the technical definition that doesn't make it through to these articles.

Doesn't the modern variation break for programs with lossless encoding/decoding? At least, for sufficiently long sequences? A Huffman/byte-pair encoding would shred any trillion-bit+ sequence, for instance. But I intuitively expect many random trillion-bit sequences exist.

The two definitions say different things. What von Mises said is closer to cryptographic definitions of pseudorandomness, and in particular to next-bit unpredictability.

Do you have a citation? I didn’t know the idea went back that far.

The whole point of Kolmogorov complexity is that description lengths under different Turing-complete description languages (such as UTM and lambda calculus) are only different up to a constant that depends on the languages and not on the thing being described.

> let’s assume that there exists a universal language U such that it always gives us the shortest description length for all strings.

Read on a bit and it looks like proof by contradiction:

> However, let’s bring back the paradox we discussed above. According to that paradox, U cannot exist or U cannot provide shorter descriptions than every arbitrary L.

There is another, more insidious, problem with trying to give a language agnostic definition: Different languages will have different symbols which are outputable.

If you have a Turing machine which can only print out binary digits, then it can't print out a chinese character, no matter how long the input program is.

Yeah, you can do something like unicode, and associate a binary string with each chinese character--but printing out that binary string is not printing out the chinese character. It's printing out a binary string.

In particular, your lambda-calculus based turing machine cannot print out chinese characters. It therefore cannot be used to define a universal complexity for any string.

Me neither.

But how I see it is that for solving KC in full generality you'll have to:

- Start with the program that explicitly returns the original string. Let's say it has length N - run all possible programs that are shorter than N (just try all combinations of characters) - look at the results and pick the shortest program that compiles and outputs the original string

The problem there is that you have to wait for all programs to end, and you don't know if they will end or not. So you have a problem that's equivalent to the halting problem (and that's not solvable) (and the halting problem is loosely related to the interesting number problem).

(This is not a proof and I don't have a background in the field btw)

The author is referring to something called Chaitin incompleteness.

https://en.wikipedia.org/wiki/Kolmogorov_complexity#Chaitin'...

Of course trivially some KC can be proven, ex a language with 1 or 0 characters that is interpreted to a specific string. Or to prove KC(x) where the compressed value has length N and you can list out all the results for all strings of length less than N, and they don't equal x, proves KC(x)=N.

The interesting number paradox (Berry's paradox) is more related to Chaitin incompleteness.

Basically, given a language there’s some code which enumerates proofs that KC of a string is more than some constant L, and returns the first one it finds.

If the constant L is large enough, it becomes larger than the entire proof generating code. So the proof generating code will never find a proof of any KC larger than L.

It's interesting to think about that the language gets more complex, proofs for larger strings become possible. And what it would mean for the languages to keep getting more complex indefinitely.

it's a similar train of thought to busy beaver numbers and how systems of logic (PA,ZFC) become independent to values like BB(745), and what it could mean to have more and more advanced types of logic which don't become independent until some high target n.

Impredicativity is the property you may want to dig into for formal proofs on why self references can be problematic.

There is an important difference between semantically complete and syntactically complete that may cause some barriers.

Gödels completeness theorem is about semantic completeness while his incompleteness theorems are about syntactic completeness.

From Wikipedia: > A formal system is syntactically complete if and only if no unprovable sentence can be added to it without introducing an inconsistency.

'This statement is false', which Gödel mapped to natural numbers is an example of that inconsistency.

If KC was computable, there would be an infinity of paradoxes like the interesting number paradox.

The Berry paradox that is linked to in the INP link in the page has a subheading that relates it to KC computability.

https://en.m.wikipedia.org/wiki/Berry_paradox

Similar to how the interesting number paradox relies on a "shortcut statement" to force-up the number of non-interest, If Kolmogorov complexity were computable you could create a "shortcut program" to force-down the shortest length of the program:

Given: TM length of a JS runtime is 1,000,000 cells.

Assume: KC is computable, and TM length of a `function KolmoglorovComplexity(string s)` is 4,000,000 cells.

Known: KC's of values grow infinitely large - only 2^n-1 possible values can ever be encoded by n bits.

Take: function Shortcut() { for (const s in generateEveryStringFromShortestUp()) { if ( KolomoglorovComplexity(s > 10,000,000) ) return s } }

You see that the Shortcut function is encoded in 5,000,135 cells (plus that string generator, but that's small/constant), but it computes a value of arbitrarily large complexity (rather, one cell increase in the program length causes 10x increase in the complexity). A contradiction.

Not quite. Specifically, assuming independent random tosses A and B sequences are equally likely. No objection here.

But the question posed is different: given a specific sequence, how likely it to have come from independent coin tosses? That is, how likely is it that Bob is cheating and his sequence was in fact not a sequence of a fair coin tosses.

And for this KC is a reasonable measure. My 2c.

The "bug" in this case imo, is that we interpret A's sequence as "random garbage" without regard to the actual contents, whereas we interpret B's as "all Ts". The question our brain asks then is "is it more likely to get random garbage or all Ts?"

Couldn’t you say that the distribution of tosses is less likely in the case of Bob?

That is a great book on the subject — the authors have published some important work in this area in papers as well.

One of Vitany's student used it to create the NCD (normalized compression distance), and then I went on to get Master/PhD degree on using it to authorship attribution.

I bought the book based on your, albeit anonymous, recommendation. Is there a python library you recommend for playing around with it?

1. Choice of language only matters up to an additive constant (e.g. you could just write a simulator so language A can run language B).

2. If you want something with less physical grounding, you could use lambda calculus instead of Turing machines.

3. Kolmogorov Complexity and Shannon Entropy are compared with one another because they both are talking about the same thing: optimal compression. Kolmogorov Complexity talks about the compressibility of individual objects and Shannon Entropy talks about compressibility of streams of i.i.d. random variables.

Many people seem to get hung up on questions related to the specifics about the implementation of computational models, but mathematicians don’t, because the fundamental aspects of the theory don’t change much when you swap out one particular model of universal computation for another.

As noted, Kolomogorov complexity depends on the specific UTM only up to a constant factor (this is known as the invariance theorem). But even the change in runtime, memory usage, and essentially anything else you might think are important are bounded by a factor that is either a constant or a “slow-growth” function (e.g. a polynomial) when you swap out one computational model for another. These small terms are generally dwarfed by the size of the data itself (even for small datasets) and the complexity of the algorithms used.

That said, I also share some of your confusion on the “specifics” when it comes to Solomonoff induction. I have yet to understand why the universal distribution uses negative exponentiated program size to weight the universal a priori probability of a particular string as opposed to some measure that involves program runtime or frequency over an equivalence class of programs that implement the same algorithm.

Solomonoff was careful to point out that his universal distribution is more of a class of distributions that have certain “universally optimal” convergence properties given a reasonable assumption on the underlying model of data generation: a deterministic algorithm with a short description that has access to a source of randomness. But I think many people since then have made the unwarranted leap that Solomonoff induction is the best induction scheme for all models of data generation, including data obtained via observation within our universe. I’m not sure that has been proven true. And if it has, I certainly haven’t come across the paper showing it.

Shannon entropy and Kolmogorov complexity are absolutely literally the same thing though! They are both purely theoretical and you cannot calculate the minimum Shannon entropy any better than you can calculate the Kolmogorov complexity. In fact if you could calculate one you could calculate the other trivially but we don't have a way to do that.

For those now thinking about how to calculate Shannon entropy using the defined formula what are you using for the symbols? If you used one bit symbols of '1' and '0' and a probability of each appearing a file that was just 11101110... repeating would you would find a different Shannon entropy to someone using 4 bit symbols. Shannon entropy is literally uncomputable in the real world. You can only compute it if you are given a fixed alphabet and frequencies but in the real world the optimal alphabet for a given file to calculate the minimum Shannon entropy is actually unknowable.

That's where Kolmogorov complexity comes in. It states that "well we don't actually have a way to define the alphabet in Shannon entropy in the real world but if we pretend we have a system (the universal computation) we could calculate it". They then add in the size of the program length that does the calculation as well to prevent cheating by having a language that has a dictionary specific to the thing to encode and call that Kolmogorov complexity. But that's it. They are literally the same thing in essence.

Kolmogorov complexity is in fact better than Shannon entropy for real world usage. It's every bit as computable in the real world (ie. not at all but at the very least you can do the best compression you can and make a guess!) but it at least states that upfront.

For anyone wanting to claim that they had a CS assignment to calculate Shannon entropy and it's totally computable your teacher should probably have explained that the symbol frequencies for the alphabet given aren't actually computable like that in the real world as the optimal symbol lengths themselves aren't actually computable. You cannot in the real world just say "compute the Shannon entropy of an alphabet with two symbols - B 30% and A 70%" because you don't actually know if B and A are the optimal alphabet to define to minimize Shannon entropy. BBBAAAAAAA repeated has no entropy but it fits the definition of the question given and would give you a different result.

With a Turing complete language, you can't know whether a given program eventually yields the string, or continues indefinitely

> So what's uncomputable here?

Deciding whether the universal machine will ever halt on a particular input. I.e. the good old halting problem.

The programs we check might not halt.

It's a lot better than the alternatives. Particularly the misused Shannon entropy.

The top rated answer for "how do i measure Shannon entropy" on stack overflow for example has an accepted answer of "count the probabilities of all 8bit sequences and then multiply the log of those probabilities together as per the equation". Which is a problematic answer. A file of all 8bit characters in sequence repeated many times over won't have any entropy but will have high entropy by this particular arbitrary measure. The problem with Shannon Entropy is that you have no way to define the optimal symbol lengths and frequencies for any given file.

Kolmogorov Complexity on the other hand at least gives some way for us to get a rough estimate. It's just as incalculable as Shannon entropy but at least by essentially explicitly stating "compress it using the best tool you have at hand and see how small it gets and also include the size of the compression program in the calculation to prevent cheating by using a dictionary" you can get some rough estimate.

Basically Kolmogorov Complexity is the best tool we have. It's not perfect because just like Shannon Entropy it's incalculable in reality but unlike Shannon Entropy we do have a good way to measure if one tool of calculating Kolmogorov Complexity is better than another tool. That measure is simply "does it compress better?".

It's literally the best way to measure randomness of an arbitrary file. Any other way is pretty game-able. If someone uses Shannon entropy to measure randomness just look at the alphabet they use for that measurement and repeat that alphabet sequentially over and over again and you'll have a high shannon entropy for a clearly non-random file. Likewise other measurements might be game-able with large dictionaries to lookup. Kolmogorov complexity includes the entire program so that game doesn't work here.

Interestingly, dna programs are quite compressible

https://en.m.wikipedia.org/wiki/Compression_of_genomic_seque...

Not sure what kinds of selection pressures there has been for shorter DNA strings, but presumably you could compress it a great deal putting it in a .zip file. Now imagine the havoc caused by random mutations on that format though.

If we ever find a perfect theory of physics, then that might be the smallest program to generate human DNA.

Some examples for a particular algorithm: https://rosettacode.org/wiki/LZW_compression

Definitely with you on the ray/path tracer :)

Regarding point 1), one can easily show that with probability >= 1 - 2^{-k}, a randomly chosen bitstring x of length n must satisfy KC(x) >= n-k. After all, there are only 1+2+... 2^{n-k-1} = 2^{n-k}-1 shorter descriptions. So highly compressible strings are highly unlikely.

Regarding 2), No, most strings x do not satisfy KC(x) = |x|, since you need to use some bits to specify that you're giving x literally. See the first theorem of [1].

[1] https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d8...

re #1: the conflation is justified, but you couldn't guess that just from what was presented in the OP. There are some cool theorems which justify it tho---if you like Kolmogorov complexity you are in for a fun ride.

re #2: No. Basically the > part of it handles the case when the smallest program which prints out the string is actually LARGER than the length of the string. In that case, the string is still incompressible. Compression means mapping from larger strings to smaller strings.

At my university (IIT, top school in India and well-known around the world) this was covered in an elective you could take, not part of the core CS curriculum.

Yes, at least in the UK. From working through some US university curricula - it's also present there as well.

You don't need Kolmogorov complexity for this; simple hypothesis testing will do. The null hypothesis is that the coin is fair and the alternative is that it's biased. If Bob was correct, then there would simply never be any way to refute the null hypothesis of a fair coin, no matter what, since it can simply output anything at all with equal probability as anything else. In reality, that isn't how hypothesis testing works, and pretty much any standard technique (computing p-values, likelihood ratios, etc) will agree that 20 tails in a row is extremely unlikely given the null hypothesis in a way that 10 tails and 10 heads is not.