Kolmogorov Complexity and Compression Distance (2023)
1–10 of 106 posts
Re: Kolmogorov Complexity and Compression Distance (2023)
#2[dead]
Re: Kolmogorov Complexity and Compression Distance (2023)
#3Confused how the interesting number paradox proves KC cannot be computed.
Re: Kolmogorov Complexity and Compression Distance (2023)
#4Confused how the interesting number paradox proves KC cannot be computed.
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.
Re: Kolmogorov Complexity and Compression Distance (2023)
#5Well, 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.
Re: Kolmogorov Complexity and Compression Distance (2023)
#6An 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)!
Re: Kolmogorov Complexity and Compression Distance (2023)
#7> 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)
Talk about a cliffhanger :)
Using [0] you get 32B for Alice and 40B for Bob.
[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)
Re: Kolmogorov Complexity and Compression Distance (2023)
#8I think maybe another way to put this is that Alice's number is in a typical set [0] of the distribution of bitstrings whereas Bob'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's, but most strings it will encode close to optimally.
Re: Kolmogorov Complexity and Compression Distance (2023)
#9Richard 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) "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".
Re: Kolmogorov Complexity and Compression Distance (2023)
#10Sometimes 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.