The capacity of finite state channels (FSCs) with feedback has been shown to be a limit of a sequence of multi-letter expressions. Despite many efforts, a closed-form single-letter capacity characterization is unknown to date. In this paper, the feedback capacity is studied from a fundamental algorithmic point of view by addressing the question of whether or not the capacity can be algorithmically computed. To this aim, the concept of Turing machines is used, which provides fundamental performance limits of digital computers. It is shown that the feedback capacity of FSCs is not Banach-Mazur computable and therefore not Borel-Turing computable. As a consequence, it is shown that either achievability or converse is not Banach-Mazur computable, which means that there are computable FSCs for which it is impossible to find computable tight upper and lower bounds. Furthermore, it is shown that the feedback capacity cannot be characterized as the maximization of a finite-letter formula of entropic quantities.

翻译：有反馈的限定状态频道(FSCs)的能力已被证明是多字母表达式序列的一个限制。尽管做出了许多努力,但封闭式单字母能力特征迄今还未知。本文从基本的算法角度研究了反馈能力,解决了能否从逻辑上计算能力的问题。为此,使用了图灵机的概念,它提供了数字计算机的基本性能限制。它表明FSCs的反馈能力不是Banach-Mazur compublicable-Mazur compublicable,因此不是Borel-Turing compublicable。结果,它显示要么可实现性或可实现性不是Banach-Mazur compublicable,这意味着无法找到可计算到的紧紧和下限的可计算FSC。此外,还表明反馈能力不能被定性为最大程度的百分数公式。