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…
Like this:
Like Loading...
