论文标题
噪声通道的零错误容量的可计算性
Computability of the Zero-Error Capacity of Noisy Channels
论文作者
论文摘要
零错误的容量在整个操作任务中起着重要作用，此外还必须进行实际应用。由于零误差容量的重要性，有必要研究其算法的可计算性，因为到目前为止尚无已知封闭公式的封闭公式。我们表明，嘈杂的通道的零误差容量不可计算Banach-Mazur，因此不可计算。我们还研究了离散无内存通道的零误差能力，图形的香农容量以及AHLSWEDE相对于0-1-偏差变化通道的最大误差容量的零误差能力的零错误容量的表征。我们将表明，有关半确定性的重要问题对于所有三个能力都是等效的。到目前为止，图形的香农容量的骨质填充可计算性是完全开放的。这就是为什么与半确定性的耦合很有趣的原因。
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.
