KOLMOGOROV COMPLEXITY AND THE ASYMPTOTIC BOUND FOR ERROR-CORRECTING CODES

摘要

The set of all error-correcting block codes over a fixed alphabet with q letters determines a recursively enumerable set of ratio- nal points in the unit square with coordinates (R, δ):= (relative transmission rate, relative minimal distance). Limit points of this set form a closed subset, defined by R ≤ α_q(δ), where α_q(δ) is a continuous decreasing function called the asymptotic bound. Its existence was proved by the first-named author in 1981 ([10]), but no approaches to the computation of this function are known, and in [14] it was even suggested that this function might be uncom- putable in the sense of constructive analysis. In this note we show that the asymptotic bound becomes com- putable with the assistance of an oracle producing codes in the order of their growing Kolmogorov complexity. Moreover, a natu- ral partition function involving complexity allows us to interpret the asymptotic bound as a curve dividing two different thermody- namic phases of codes.