The algorithmic probability of a finite string 
relative to an optimal prefix-free 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. Summing 
over all finite output strings 
gives the halting probability 
, a Chaitin
constant (Calude et al. 2002, p. 362).
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.
