9 ms·
After a cursory glance this just looks like a restatement of Kolmogorov Complexity: "...the complexity is the length of the string's shortest description in som
by benmathes 17y ago
After a cursory glance this just looks like a restatement of Kolmogorov Complexity: "...the complexity is the length of the string's shortest description in some fixed universal description language."
Traditionally a Turing Machine is used as the fixed universal description language. This paper just substituted scheme.
http://en.wikipedia.org/wiki/Kolmogorov_complexity http://en.wikipedia.org/wiki/Kolmogorov_complexity
- btilly 17y agoThey are tied, but it is being restated by one of the independent discoverers of the concept. Furthermore the theorem he is talking about is original to him. There is no "just" to it.
- benmathes 17y agoAh, my mistake. I didn't read the dates on the link, and assumed it was recently created.