The algorithmic probability of a finite string 
relative to a universal
Turing machine 
is
 |
where the programs 
in the sum are those for which 
eventually halts with output 
. These programs form a prefix-free
code, and 
is the program length. Thus 
is the probability that
a stream of independent random bits begins with a program
that makes 
output 
.
It is a universal lower semicomputable semimeasure.
Changing the universal Turing machine
changes 
by at most a multiplicative constant. Algorithmic probability
is closely related to Kolmogorov complexity
through the coding theorem. It gives greater weight to strings
generated by shorter programs, thereby implementing an
Occam-type preference for simpler descriptions in algorithmic induction.
