论文标题
使用Kolmogorov Oracle的零误差容量的可计算性
Computability of the Zero-Error capacity with Kolmogorov Oracle
论文作者
论文摘要
Shannon首先将离散经典通道的零误差容量定义为最低率的上限，该速率是一个人以误差概率传输信息的速率。找到零误差容量$ C_0 $的问题，该$为一个函数分配了每个通道的能力，它是根据图理论作为函数$θ$的，为每个简单的图为$θ$分配了一个值。本文研究了零误差容量的可计算性。为了进行计算，使用Turing机器和Kolmogorov Oracle的概念。总体上是否可以计算零错误的容量，这是未知的。我们表明，一般而言，零错误的容量是可以在Kolmogorov Oracle的帮助下进行半计算的。此外，我们证明$ c_0 $和$θ$是可计算的函数，并且仅当存在上限的可计算函数的可计算顺序，即，在信息理论的意义上存在相反的函数，这些函数存在，这些函数会在信息理论的意义上汇总到$ c_0 $或$ $θ$。最后，我们检查了Zuiddam的$ C_0 $和$θ$的特征，以算法的可计算性。
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 $Θ$, 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 $Θ$ 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 pointwise converge to $C_0$ or $Θ$. Finally, we examine Zuiddam's characterization of $C_0$ and $Θ$ in terms of algorithmic computability.
