Abstract:
The optimal prefix-free machine U is a universal
decoding algorithm used to define the notion of program-size
complexity H(s) for a finite binary string s. Since the set
of all halting inputs for U is chosen to form a prefix-free
set, the optimal prefix-free machine U can be regarded as
an instantaneous code for noiseless source coding scheme. In
this paper, we investigate the properties of optimal prefix-free
machines as instantaneous codes. In particular, we investigate
the properties of the set U`1
(s) of codewords associated with
a symbol s. Namely, we investigate the number of codewords in
U`1
(s) and the distribution of codewords in U`1
(s) for each
symbol s, using the toolkit of algorithmic information theory.