Capacity of Finite State Channels with Feedback: Algorithmic and Optimization Theoretic Properties

The capacity of finite state channels (FSCs) with feedback has been expressed by a limit of a sequence of multi-letter expressions. Despite many efforts, a closed-form single-letter capacity characterization remains 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 also not Borel-Turing computable. It is further shown that it is even impossible to approximate the feedback capacity function of FSCs by a computable function. As a consequence, it is shown that computable achievability and converse can never be tight, which means that there are 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.