Error-correcting codes, Kolmogorov complexity, and thermodynamics

The set of all error--correcting block codes over a fixed alphabet  with $q$ letters 
determines a recursively enumerable set of  rational points in the unit square with
coordinates $(R,\delta )$:= {\it  (relative transmission rate, relative minimal distance).}
Limit points of this set form a closed subset, defined by $R\le \alpha_q(\delta )$, where
$\alpha_q(\delta )$ is a continuous decreasing function called {\it asymptotic bound.}
Its existence was proved by Yu.M. in 1981, but no approaches to the computation of
this function are known, and in a recent paper I have even suggested that this function
might be uncomputable in the sense of constructive analysis.

In this talk based upon a work in progress with  M. Marcolli I will show  that the asymptotic
bound becomes computable with the assistance of an oracle producing codes in the order
of their growing Kolmogorov complexity. Moreover, a natural partition function involving
complexity allows us to interpret the asymptotic bound as a curve dividing two different
thermodynamic phases of codes.