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

41–50 of 106 posts

Re: Kolmogorov Complexity and Compression Distance (2023)

#41

Post by chaboud »

a_wild_dandan wrote: post #39
arketyp wrote: post #9

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) "considering a finite sequence random (with respect to a class of compu…

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.

There is no encoding that would shred "any" (read: every) trillion bit sequence. If that were true, some fundamentals of information theory and compressibility would break down.

Lossless encoding works by taking advantage of the more commonly observed sequences of data having lower information entropy. For things like audio encoding, where discontinuous sequences aren't naturally observed (or pleasing to listen to), lossless encoding has a lot to work with.

Re: Kolmogorov Complexity and Compression Distance (2023)

#42

Post by causal »

srcreigh wrote: post #4
causal wrote: post #3

Confused 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 K…

This seems to assume that KC can be infinite. That must have been proven at some point? Otherwise it may be that there is some upper-bound for L which happens to also be the KC for a KC-computer.

Re: Kolmogorov Complexity and Compression Distance (2023)

#43

Post by causal »

Opocio wrote: post #11
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 fo…

That intuitively makes sense to me.

Re: Kolmogorov Complexity and Compression Distance (2023)

#44

Post by derbOac »

anonzzzies wrote: post #38

Kolmogorov complexity is a lovely subject and one of the more influential ones in my life. THE book https://link.springer.com/book/10.1007/978-0-387-49820-1 is absolutely a thing to read. It was for me 30 years ago and it aged well.

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

Re: Kolmogorov Complexity and Compression Distance (2023)

#45

Post by veerd »

davesque wrote: post #37

Something I've always noticed with the notion of Kolmogorov complexity is that the question of determining the lowest level of computation is problematic. 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…

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.

Re: Kolmogorov Complexity and Compression Distance (2023)

#46

Post by nerdponx »

Hunpeter wrote: post #30
copx wrote: post #16

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

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?"

Right. It might be more interesting to consider the count of Ts and Hs instead of considering exact sequences.

Re: Kolmogorov Complexity and Compression Distance (2023)

#47

Post by mxkopy »

rhelz wrote: post #26
tromp wrote: post #20

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

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--b…

I feel like a conversion from binary strings to Unicode/Chinese characters would be in PTIME, so adding a conversion machine would be a nonfactor for languages in most complexity classes.

Re: Kolmogorov Complexity and Compression Distance (2023)

#48

Post by mxkopy »

a_wild_dandan wrote: post #39
arketyp wrote: post #9

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) "considering a finite sequence random (with respect to a class of compu…

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.

For any fixed compression scheme, there is an input string that is actually lengthened by it rather than shortened.

However Huffman isn’t a fixed compression scheme since it makes a different frequency tree for different corpora.

Re: Kolmogorov Complexity and Compression Distance (2023)

#49

Post by smallnamespace »

mxkopy wrote: post #47
rhelz wrote: post #26

Earlier quoted context omitted.

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--b…

I feel like a conversion from binary strings to Unicode/Chinese characters would be in PTIME, so adding a conversion machine would be a nonfactor for languages in most complexity classes.

The stronger result here is that any sort of conversion you can explicitly specify can be turned into a program.

Since Kolmogorov Complexity is specified in terms of lengths of programs, that means the KC between two different pairs of encodings can differ at most by a constant amount (the size of the program that converts back and forth).

The above is a bit handwavey, there are details you can tighten up (Is it the program size or something smaller? The program length in which encoding?), but heuristically that's why theorists can talk about "the" Kolmogorov complexity without getting bogged down in with pesky encoding details.

It's also why we usually don't worry too much about the fine details of Turing Machines (alphabet, etc.), since you can generally emulate one sort of Turing Machine pretty easily with a short program written on another.

Re: Kolmogorov Complexity and Compression Distance (2023)

#50

Post by amelius »

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.

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