TY - GEN

T1 - Computability of the Zero-Error Capacity of Noisy Channels

AU - Boche, Holger

AU - Deppe, Christian

N1 - Publisher Copyright:
© 2021 IEEE.

PY - 2021

Y1 - 2021

N2 - Zero-error capacity plays an important role in a whole range of operational tasks, in addition to the fact that it is necessary for practical applications. Due to the importance of zero-error capacity, it is necessary to investigate its algorithmic computability, as there has been no known closed formula for the zero-error capacity until now. We show that the zero-error capacity of noisy channels is not Banach-Mazur computable and therefore not Borel-Turing computable. This result also implies the uncomputability of the zero-error capacity for real-valued channel matrices characterized by means of an oracle machine. We also investigate the relationship between the zero-error capacity of discrete memoryless channels, the Shannon capacity of graphs, and Ahlswede's characterization of the zero-errorcapacity of noisy channels with respect to the maximum error capacity of 0-1-arbitrarily varying channels. We will show that important questions regarding semi-decidability are equivalent for all three capacities. So far, the Borel-Turing computability of the Shannon capacity of graphs is completely open. This is why the coupling with semi-decidability is interesting. The authors conjecture that the zero-error capacity of a noisy channel may be computable with respect to some computation models other than the Turing machine, like neuromorphic-computers and specific types of quantum computers.

AB - Zero-error capacity plays an important role in a whole range of operational tasks, in addition to the fact that it is necessary for practical applications. Due to the importance of zero-error capacity, it is necessary to investigate its algorithmic computability, as there has been no known closed formula for the zero-error capacity until now. We show that the zero-error capacity of noisy channels is not Banach-Mazur computable and therefore not Borel-Turing computable. This result also implies the uncomputability of the zero-error capacity for real-valued channel matrices characterized by means of an oracle machine. We also investigate the relationship between the zero-error capacity of discrete memoryless channels, the Shannon capacity of graphs, and Ahlswede's characterization of the zero-errorcapacity of noisy channels with respect to the maximum error capacity of 0-1-arbitrarily varying channels. We will show that important questions regarding semi-decidability are equivalent for all three capacities. So far, the Borel-Turing computability of the Shannon capacity of graphs is completely open. This is why the coupling with semi-decidability is interesting. The authors conjecture that the zero-error capacity of a noisy channel may be computable with respect to some computation models other than the Turing machine, like neuromorphic-computers and specific types of quantum computers.

KW - Computability

KW - Zero-error capacity

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

U2 - 10.1109/ITW48936.2021.9611383

DO - 10.1109/ITW48936.2021.9611383

M3 - Conference contribution

AN - SCOPUS:85123432259

T3 - 2021 IEEE Information Theory Workshop, ITW 2021 - Proceedings

BT - 2021 IEEE Information Theory Workshop, ITW 2021 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2021 IEEE Information Theory Workshop, ITW 2021

Y2 - 17 October 2021 through 21 October 2021

ER -