Computability of the Zero-Error Capacity with Kolmogorov Oracle
Computability of the Zero-Error Capacity with Kolmogorov Oracle
The zero-error capacity of a discrete classical channel was first defined by Shannon as the least upper bound of rates for which one transmits information with zero probability of error. The problem of finding the zero-error capacity C <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</sub> , which assigns a capacity to each channel as …