Occam’s razor states that entities must not be multiplied beyond necessity. What is necessity?

Definition Kolmogorov complexity of a string is the length of the shortest possible program that outputs , i.e.

The Kolmogorov complexity measures the information content. The function is (in general) not computable, although the Kolmogorov complexity of an integer is computable.

where is some prime factorisation. We can use this is prove the infinitude of primes (which of course is a rather simple proof without incompressibility):

Any number can be represented as . Now assume that there are only  distinct primes. The exponents are then . We can then further represent the exponents by bits, so

And this is a contradiction? Why? Because of incompressibility! According to this, we would be able to describe any number with less than bits! So there must be infinitely many primes…