# The choice of programming language and the length of a program

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

• 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. – András Salamon May 6 '13 at 14:17

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.