论文标题
算法的可计算性和能力实现输入分布的近似性
Algorithmic Computability and Approximability of Capacity-Achieving Input Distributions
论文作者
论文摘要
通道的容量通常可以表征为某些熵量的最大化。从实际的角度来看，不仅要计算容量值，而且要找到相应的优化器，即能力实现输入分布，这是主要的兴趣。本文解决了是否可以找到可以根据渠道计算最佳输入分布的算法的一般问题。为此，使用了图灵机的概念，该概念提供了数字计算机的基本性能限制，因此完全指定哪些任务在原则上是算法可行的。对于离散的无内存通道显示的是，算法不可能计算容量调整后的输入分布，在该输入分布中，该通道作为算法（或Turing Machine）的输入。最后，进一步表明，甚至不可能算法近似这些输入分布。
The capacity of a channel can usually be characterized as a maximization of certain entropic quantities. From a practical point of view it is of primary interest to not only compute the capacity value, but also to find the corresponding optimizer, i.e., the capacity-achieving input distribution. This paper addresses the general question of whether or not it is possible to find algorithms that can compute the optimal input distribution depending on the channel. For this purpose, the concept of Turing machines is used which provides the fundamental performance limits of digital computers and therewith fully specifies which tasks are algorithmically feasible in principle. It is shown for discrete memoryless channels that it is impossible to algorithmically compute the capacity-achieving input distribution, where the channel is given as an input to the algorithm (or Turing machine). Finally, it is further shown that it is even impossible to algorithmically approximate these input distributions.
