The halting probability 
of a self-delimiting Turing
machine 
is the probability that a stream of independent fair
bits begins with a halting program
for 
.
The halting programs form a prefix-free
code, and
 |
where 
is the length of program 
in bits. The Kraft
inequality ensures 
(Calude et al. 2002, p. 362).
If 
simulates every self-delimiting Turing machine
with at most a constant additive overhead in program
length, then 
is a Chaitin's constant (Calude et al. 2002,
p. 362). Merely being a universal Turing
machine in the usual computability sense does not ensure this stronger property
(Calude et al. 2002, p. 362).
For the compressed register machine 
of Calude et al. (2002, p. 366), let 
count the halting programs
of total length 
bits, including both program and
data and excluding run-time errors. These machine-specific counts begin 1, 1, 3,
8, 50, 311, ... at 
(OEIS A400878; Calude et al. 2002, p. 367).
Since each character occupies 7 bits,
 |
