TY - GEN

T1 - Computability of the Zero-Error Capacity with Kolmogorov Oracle

AU - Boche, Holger

AU - Deppe, Christian

N1 - Publisher Copyright:
© 2020 IEEE.

PY - 2020/6

Y1 - 2020/6

N2 - 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 C0, which assigns a capacity to each channel as a function, was reformulated in terms of graph theory as a function Θ, 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 C0 and Θ 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 C0 or Θ. Finally, we examine Zuiddam's characterization of C0 and Θ in terms of algorithmic computability.

AB - 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 C0, which assigns a capacity to each channel as a function, was reformulated in terms of graph theory as a function Θ, 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 C0 and Θ 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 C0 or Θ. Finally, we examine Zuiddam's characterization of C0 and Θ in terms of algorithmic computability.

KW - Kolmogorov Oracle

KW - Turing computability

KW - zero-error capacity

UR - http://www.scopus.com/inward/record.url?scp=85090403322&partnerID=8YFLogxK

U2 - 10.1109/ISIT44484.2020.9173984

DO - 10.1109/ISIT44484.2020.9173984

M3 - Conference contribution

AN - SCOPUS:85090403322

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2020

EP - 2025

BT - 2020 IEEE International Symposium on Information Theory, ISIT 2020 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2020 IEEE International Symposium on Information Theory, ISIT 2020

Y2 - 21 July 2020 through 26 July 2020

ER -