论文标题
香农遇到图灵：有限状态渠道容量的非竞争性和不易XIBIBIBITIS
Shannon Meets Turing: Non-Computability and Non-Approximability of the Finite State Channel Capacity
论文作者
论文摘要
有限状态通道（FSC）的能力仅作为一系列多字母表达式的限制，尽管巨大的努力，但迄今为止相应的有限字母表征仍然未知。本文通过研究是否可以通过研究算法计算相应的可实现性和相当的可实现性和相反界限来分析FSC的能力。为此，使用图灵机的概念，可提供数字计算机的基本性能限制。为此，研究了可计算的连续函数，并确定了此类功能的可计算序列的属性。结果表明，FSC的能力不是可计算的Banach-Mazur，这是最弱的可计算性形式。这意味着没有算法（或图灵机）可以计算给定FSC的容量。结果，可以证明可实现性或匡威必须产生不可计算的banach-mazur的结合。这也意味着存在可计算的下限和上限永远不会紧密的FSC。为此，进一步表明，FSC的容量不可近似，这比非竞争性更严格。这意味着无法找到对一般FSC能力的有限字母熵表征。所有结果甚至适用于有限输入和输出字母和有限状态集。最后，讨论了与有效分析理论的联系。在这里，仅允许以建设性的方式证明结果，而存在基于选择的公理的存在结果，则被禁止证明。
The capacity of finite state channels (FSCs) has been established as the limit of a sequence of multi-letter expressions only and, despite tremendous effort, a corresponding finite-letter characterization remains unknown to date. This paper analyzes the capacity of FSCs from a fundamental, algorithmic point of view by studying whether or not the corresponding achievability and converse bounds on the capacity can be computed algorithmically. For this purpose, the concept of Turing machines is used which provide the fundamental performance limits of digital computers. To this end, computable continuous functions are studied and properties of computable sequences of such functions are identified. It is shown that the capacity of FSCs is not Banach-Mazur computable which is the weakest form of computability. This implies that there is no algorithm (or Turing machine) that can compute the capacity of a given FSC. As a consequence, it is then shown that either the achievability or converse must yield a bound that is not Banach-Mazur computable. This also means that there exist FSCs for which computable lower and upper bounds can never be tight. To this end, it is further shown that the capacity of FSCs is not approximable, which is an even stricter requirement than non-computability. This implies that it is impossible to find a finite-letter entropic characterization of the capacity of general FSCs. All results hold even for finite input and output alphabets and finite state set. Finally, connections to the theory of effective analysis are discussed. Here, results are only allowed to be proved in a constructive way, while existence results, e.g., proved based on the axiom of choice, are forbidden.
