News for hackers. Stuff that matters.
Re:Kolmogorov Complexity and Compression Distance by canjobear on Saturday March 30, 2024 @06:09PM (#39879157)
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.
Re:Kolmogorov Complexity and Compression Distance by uoaei on Saturday March 30, 2024 @09:45PM (#39880571)
The whole point of Kolmogorov complexity is that there exists some language for minimal description length of an arbitrary program and you compare optimal descriptions across languages. In other words, the point is to explicitly consider the choice of language as part of the encoding scheme that needs describing. That choice is included as part of the description whose length is being measured.
Re:Kolmogorov Complexity and Compression Distance by data_maan on Sunday March 31, 2024 @08:36AM (#39883712)
Is that really true? You could just take whatever you want to describe to be part of the language and arrive trivially at a description length of 1...?
Re:Kolmogorov Complexity and Compression Distance by smilliken on Sunday March 31, 2024 @01:40PM (#39886246)
I have an encoding improvement that can reduce the length of that program by 100% to an unbeatable 0 symbols (patent pending).
Re:Kolmogorov Complexity and Compression Distance by uoaei on Sunday March 31, 2024 @10:21PM (#39890280)
How long is the description length of the language...?