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...
详细信息
ISBN:
(纸本)9781424482641
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 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.
暂无评论