Kolmogorov Complexity and Compression Distance (2023)

&gt; let’s assume that there exists a universal language U<p>Why not specify it?<p>&gt; That gives us the true language-agnostic definition of Kolmogorov Complexity as follows:<p>Choosing the language of Turing Machines does not make the definition language agnostic.<p>Aiming for the simplest definition of description complexity, I instead based my definitions on the older computational model of lambda calculus in [1].<p>Unlike the assumed UTM above, the universal lambda machine is easy to describe in detail:<p><pre><code> (λ 1 1) (λ λ λ 1 (λ λ λ λ 3 (λ 5 (3 (λ 2 (3 (λ λ 3 (λ 1 2 3))) (4 (λ 4 (λ 3 1 (2 1)))))) (1 (2 (λ 1 2)) (λ 4 (λ 4 (λ 2 (1 4))) 5)))) (3 3) 2) (λ 1 ((λ 1 1) (λ 1 1))) </code></pre> Furthermore, it allows almost identical definitions of various variations of descriptional complexity, namely<p>1) plain complexity<p>2) prefix complexity<p>3) monotone complexity<p>all of which have their application in Algorithmic Information Theory [2].<p>[1] <a href="https:&#x2F;&#x2F;gist.github.com&#x2F;tromp&#x2F;86b3184f852f65bfb814e3ab0987d861" rel="nofollow">https:&#x2F;&#x2F;gist.github.com&#x2F;tromp&#x2F;86b3184f852f65bfb814e3ab0987d8...</a><p>[2] <a href="https:&#x2F;&#x2F;homepages.cwi.nl&#x2F;~paulv&#x2F;kolmogorov.html" rel="nofollow">https:&#x2F;&#x2F;homepages.cwi.nl&#x2F;~paulv&#x2F;kolmogorov.html</a>

Richard von Mises (brother of the economist) formulated a definition of randomness as a sequence of data that, were you a gambler, you cannot by any strategy make money on betting on the outcomes. This was before computational calculus and was later developed by Kolmogorov and others in algorithmic complexity. The modern variation would be (Wiki) &quot;considering a finite sequence random (with respect to a class of computing systems) if any program that can generate the sequence is at least as long as the sequence itself&quot;.

I think its bootless to try to define the &quot;minimum possible&quot; Kolmogorov complexity. Here&#x27;s why:<p>1. Note, kolmogorov complexity is defined by the length of the shortest <i>program</i> which prints out the string. What counts is the <i>number</i> of instructions, and not the <i>complexity of those instructions</i>.<p>2. So say S is a very complex spring. We can always construct a turing machine which could print out S using a zero length program: it could just start in a state which prints out S when you turn it on, and then halts.<p>3. So there is no such thing as a turing machine which prints out <i>every</i> string shorter than <i>any</i> other turing machine prints it out, QED.<p>That&#x27;s the bad news. The good news is we don&#x27;t even need to do that. For any string S, say that M and N are any two universal turing machines. Without loss of generality, specify that KM(S) &lt;= KN(S). Then there is always some C for which KM(S) &lt;= KN(S) + C. The constant C being the length of the program required to <i>emulate</i> machine M on machine N.<p>We are used to abstracting out constant sums and constant factors like this. The strings we are dealing with (as a species) are growing in length exponentially--that&#x27;s why we went from 8-bit, to 16bit, etc computers. So as the length of S goes to infinity, the difference between the its complexity for any two machines becomes negligible.

Kolmogorov complexity is a lovely subject and one of the more influential ones in my life.<p>THE book <a href="https:&#x2F;&#x2F;link.springer.com&#x2F;book&#x2F;10.1007&#x2F;978-0-387-49820-1" rel="nofollow">https:&#x2F;&#x2F;link.springer.com&#x2F;book&#x2F;10.1007&#x2F;978-0-387-49820-1</a> is absolutely a thing to read. It was for me 30 years ago and it aged well.

An excellent rabbit hole to dive into is the equivalence of compression and general AI. Every programmer should make a compressor (and, separately, a ray tracer)!<p>See <a href="http:&#x2F;&#x2F;prize.hutter1.net&#x2F;" rel="nofollow">http:&#x2F;&#x2F;prize.hutter1.net&#x2F;</a>

&gt; It has been demonstrated that KC(x), can be reasonably estimated by the number of bits required to encode x using a compressor C (such as gzip)<p>Talk about a cliffhanger :)<p>Using [0] you get 32B for Alice and 40B for Bob.<p>[0] It has been demonstrated that KC(x), can be reasonably estimated by the number of bits required to encode x using a compressor C (such as gzip)

Confused how the interesting number paradox proves KC cannot be computed.

Something I&#x27;ve always noticed with the notion of Kolmogorov complexity is that the question of determining the lowest level of computation is problematic.<p>For example, in the article, the author first defines the basic idea of KC. But then they correctly point out that the basic idea depends very much on the exact language that is chosen. So they describe how theorists have defined the notion of universal computation. But even this adjustment doesn&#x27;t seem to escape the fact the we still depend on a system of mathematical symbols to describe the theory. And the notion of a Turing machine itself depends on other abstract concepts such as time and space, each with their own inherent, conceptual complexity. What sorts of minds (i.e. brains) are required to make sense out of the theory and what physical system is required for them to operate correctly? If the definition of KC includes a notion of how complex the Turing machine is that is required to compute a string, then the further down you go, the less the difference in complexity should be between any one string and another. After all, they all exist in the same universe!<p>I guess it just goes to show how much the idea of KC lives in the realm of theory. As soon as you pose the question of complexity so abstractly, you invite in all kinds of theoretical considerations that make the meaning more slippery. That&#x27;s why KC really doesn&#x27;t deserve to be compared to Shannon entropy as it often is.<p>But let me draw a comparison anyway like I said you shouldn&#x27;t! Because Alice from the article could also have made a strong argument against Bob by just pointing out that the Shannon entropy of his string was lower, which is very relevant in terms of the number of heads or tails and the likelihood of seeing a particular count of them.

&gt;Bob claims that since the probability of getting both his and Alice’s sequence is the same (2−20 ), it proves that there was no foul-play involved.<p>..and Bob is 100% right.<p>&gt;Bob credits his excellent luck. Alice is smart and cannot be easily convinced. She get’s back at Bob by claiming that probability cannot be used in this context as it reveals no information regarding the randomness of the obtained sequences. One can take a quick glance at the obtained sequences and easily point out that Alice’s sequence is more random than Bob’s sequence.<p>No, it is not. Given a perfectly random coin toss Bob&#x27;s sequence is indeed just as likely as Alice&#x27;s sequence and in no way &quot;less random&quot; because both sequences result from the same randomness with equal probability.<p>A nice example of human intuition being at odds with probability math, though. Bob&#x27;s result seems less likely but it really is not. Which reminds me that I actually had to write my own computer simulation of the Monty Hall Problem before I was willing to believe the correct answer. I think (most?) human brains have a bug in the &quot;understanding probability&quot; subroutine.

I&#x27;m going to keep reading (because I love the KC topic), but I&#x27;d appreciate anyone confirming if the following are errors in this article:<p>1.) Conflating usage of the term &quot;random&quot; and &quot;complexity&quot;. After all, a set of &quot;randomly&quot; drawn sample permutations from an alphabet are all equally likely. However, their &quot;complexity&quot; may differ, which is basically the point of the article, but the term more or less &quot;random&quot; keeps being used to refer to permutations with more or less &quot;complexity&quot;, which I think is probably going to perpetuate confusion on this topic.<p>2.) From the article: &quot;Moreover, a string cannot be compressed if its KC(x)≥|x|&quot;. Shouldn&#x27;t the expression accompanying this statement be KC(x)=|x| ?

I think maybe another way to put this is that Alice&#x27;s number is in a typical set [0] of the distribution of bitstrings whereas Bob&#x27;s might not be. Depending on the tolerance, the typical set can have near-total coverage of the distribution. Another way of making this about compression is that a random code that could encode typical set strings well probably will suffer some overhead when encoding Bob&#x27;s, but most strings it will encode close to optimally.<p>[0] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Typical_set" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Typical_set</a>

A side question: is this taught in CS curriculum you know? It was at my uni (fairly good one, in a minor European country), and this experience biases me because I assume every CS knows Kolmogorov complexity.

Well, I reached the end of the article (interesting btw), and still not convinced why bob can&#x27;t claim that there was no foul-play involved and that his got his result due to excellent luck.

&gt; Another thing to note is that Kolmogorov complexity of a string cannot be computed. There cannot exist a computer that will always guarantee the Kolmogorov complexity for all the strings.<p>Sounds a bit puzzling. Surely for a particular programming language we can enumerate all programs, ordered by length etc. and check which is the shortest one giving the given string. So what&#x27;s uncomputable here? For long strings that could take long time, but - ?

If you want something like Kolmogorev complexity for molecules, check out assembly theory. I am a CS person, but there are interesting, related ideas here.<p><a href="https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;Assembly_theory" rel="nofollow">https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;Assembly_theory</a>

Kolmogorov Complexity does not help with giving a universal measure of complexity or randomness: <a href="https:&#x2F;&#x2F;forwardscattering.org&#x2F;page&#x2F;0" rel="nofollow">https:&#x2F;&#x2F;forwardscattering.org&#x2F;page&#x2F;0</a>

Sometimes I wonder what would be the smallest program to generate humans DNA. How many operations would it take and how would it compare to real world iterations of total evolution.