Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Kolmogorov Complexity and Compression Distance (2023)

smunshi.net

Post reply on HN
Print view View original

11–20 of 106 posts

Re: Kolmogorov Complexity and Compression Distance (2023)

#11

Post by Opocio »

causal wrote: post #3

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

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)

Re: Kolmogorov Complexity and Compression Distance (2023)

#12

Post by nyrikki »

causal wrote: post #3

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

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

Re: Kolmogorov Complexity and Compression Distance (2023)

#13

Post by wood_spirit »

marius_k wrote: post #10

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.

Interestingly, dna programs are quite compressible

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

Re: Kolmogorov Complexity and Compression Distance (2023)

#14

Post by arketyp »

marius_k wrote: post #10

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.

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.

Re: Kolmogorov Complexity and Compression Distance (2023)

#15

Post by explaininjs »

causal wrote: post #3

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

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.

Re: Kolmogorov Complexity and Compression Distance (2023)

#16

Post by copx »

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

..and Bob is 100% right.

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

No, it is not. Given a perfectly random coin toss Bob's sequence is indeed just as likely as Alice's sequence and in no way "less random" because both sequences result from the same randomness with equal probability.

A nice example of human intuition being at odds with probability math, though. Bob'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 "understanding probability" subroutine.

Re: Kolmogorov Complexity and Compression Distance (2023)

#17

Post by ComplexSystems »

yamrzou wrote: post #5

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

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.

Re: Kolmogorov Complexity and Compression Distance (2023)

#18

Post by avmich »

wood_spirit wrote: post #6

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)! See http://prize.hutter1.net/

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

Re: Kolmogorov Complexity and Compression Distance (2023)

#19

Post by mojomark »

I'm going to keep reading (because I love the KC topic), but I'd appreciate anyone confirming if the following are errors in this article:

1.) Conflating usage of the term "random" and "complexity". After all, a set of "randomly" drawn sample permutations from an alphabet are all equally likely. However, their "complexity" may differ, which is basically the point of the article, but the term more or less "random" keeps being used to refer to permutations with more or less "complexity", which I think is probably going to perpetuate confusion on this topic.

2.) From the article: "Moreover, a string cannot be compressed if its KC(x)≥|x|". Shouldn't the expression accompanying this statement be KC(x)=|x| ?

Re: Kolmogorov Complexity and Compression Distance (2023)

#20

Post by tromp »

> let’s assume that there exists a universal language U

Why not specify it?

> That gives us the true language-agnostic definition of Kolmogorov Complexity as follows:

Choosing the language of Turing Machines does not make the definition language agnostic.

Aiming for the simplest definition of description complexity, I instead based my definitions on the older computational model of lambda calculus in [1].

Unlike the assumed UTM above, the universal lambda machine is easy to describe in detail:

    (λ 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)))
Furthermore, it allows almost identical definitions of various variations of descriptional complexity, namely

1) plain complexity

2) prefix complexity

3) monotone complexity

all of which have their application in Algorithmic Information Theory [2].

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

[2] https://homepages.cwi.nl/~paulv/kolmogorov.html

Post reply on HN