2
$\begingroup$

I wonder how it's possible that:

it can be shown that all reasonable choices of programming languages lead to quantification of the amount of absolute information in individual objects that is invariant up to an additive constant.

from the Preface to the First Edition, An Introduction to Kolmogorov Complexity and Its Applications by Li & Vitanyi.

I don't know how they defined "reasonable choice of programming language", but in my sense, it seems natural that the choice of programming language could mix the rank of the complexity. If the programming language fits the object, the program would be shorter, and if not, it would be longer.

But, if I understood it all right, the paragraph above says that no matter which programming language you choose for the strings(objects), the rank of the length of the programs would not change!

Is it really possible? and could someone explain how it's possible?

It is well known that either AND and NOT or OR and NOT can be a primitive function for a computer,

and if I want to implement AND with (OR and NOT), it goes like

NOT(NOT a OR NOT b) instead of just AND!!!

$\endgroup$
  • 6
    $\begingroup$ You are quoting from the preface to the book that then explores this question in exhaustive detail, over 790 pages. It might be worth reading just a little past the preface. $\endgroup$ – András Salamon May 6 '13 at 14:17
5
$\begingroup$

What Li and Vitanyi mean by a reasonable programming language is one that is Turing-complete. This means that you can simulate it on a Turing machine and you can simulate a Turing machine on it, so it has the same expressive power as a Turing machine. This gives you a kind of class of languages. I can prove that C is equivalent to a Turing machine, and that Java is equivalent to C, so Java is equivalent to a TM. In over fifty years, no-one has found a reasonable mechanism that is more powerful than a Turing machine (without resorting to things like time travel). This means that the Turing complete languages are considered those that are most reasonable for expressing the principle of computation (see the Church -Turing thesis).

This means that if we agree that the information content of a string should be defined as the length of the shortest program in a Turing complete language, we can never disagree much beyond that. Say that we have a string $x$ and you recon that this string contains only fifteen bits of information. I can then simulate your Turing-complete language in my Turing-complete language and run your fifteen bit program. Since my simulation of your language does not depend on $x$, we can never disagree by more than a constant amount, and for large enough $x$, the difference will become negligable.

So up to a constant term, the information content is a property of the string itself.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy