Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

-----

PS C:\programming\Kolmogorov> ruby .\interpreter.rb "puts(\`"ab\`" * 20)"

abababababababababababababababababababab

So even with this universal language, we still have Ksilly,x2(x2)=0

-----

So you input string "puts(\`"ab\`" * 20)" into a ruby program, and somehow Kolmogorov complexity is 0 and not length of the argument you passed? I don't buy that.



Yea, he's wrong on that. The point of tailoring languages to a string still -- weakly -- stands, though: but he could also do that for a finite number of strings. Weakly also because he completely misses the point of Kolmogorov complexity. It's not meant to be practical in any way. It's a mathematical tool to uncover some facts about the complexity of things (mostly mathematical objects) and a more solid framework for data compression and randomness, which he glanced at the beginning of the article. In a sense it's like other non-computable constructions, it provides truths without specific instances, because their existence would be too powerful.

Some of the interesting theorems are found in a chapter of the following book:

http://www.amazon.com/Elements-Information-Theory-Thomas-Cov...

It gives a good grasp that Kolmogorov complexity answers meaningful questions not well defined in regular information theory: questions of optimality in finite lengths.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: