Technical Program

Paper Detail

Paper IDS.1.4
Paper Title Computability of the Zero-Error capacity with Kolmogorov Oracle
Authors Holger Boche, Christian Deppe, Technische Universität München, Germany
Session S.1: Capacity Computation
Presentation Lecture
Track Shannon Theory
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract 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_0$, which assigns a capacity to each channel as a function, was reformulated in terms of graph theory as a function $\Theta$, which assigns a value to each simple graph. This paper studies the computability of the zero-error capacity. For the computability, the concept of a Turing machine and a Kolmogorov oracle is used. It is unknown if the zero-error capacity is computable in general. We show that in general the zero-error capacity is semi-computable with the help of a Kolmogorov Oracle. Furthermore, we show that $C_0$ and $\Theta$ are computable functions if and only if there is a computable sequence of computable functions of upper bounds, i.e. the converse exist in the sense of information theory, which point-wise converges to $C_0$ or $\Theta$. Finally, we examine Zuiddam's characterization of $C_0$ and $\Theta$ in terms of algorithmic computability.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!