  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. 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-error-capacity 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.
