See why the series in the definition of algorithmic probability always converges
Convergence of the series defining algorithmic probability
The convergence of \(P(s) = \sum\limits_{p:\ U_{pr}(p)=s} 2^{-|p|} \) can be proven
using Kraft’s inequality.
In a nutshell:
Let’s first observe that there is a one-to-one correspondence between a finite
binary string \(p\) and an interval \([0.p, 0.p + 2^{-|p|}]\), where \(|p|\) is the length of \(p\) and \(0.p\) designates a real number by its binary development.
The length of such an interval is \(2^{-|p|}\).
If you think about it, you’ll see that all these intervals are disjoint, because all programs \(p\) are considered to be prefix.
As a consequence, the sum is necessarily smaller than 1.