Shannon Meets Turing: Non-Computability and Non-Approximability of the\n Finite State Channel Capacity

The capacity of finite state channels (FSCs) has been established as the\nlimit of a sequence of multi-letter expressions only and, despite tremendous\neffort, a corresponding finite-letter characterization remains unknown to date.\nThis paper analyzes the capacity of FSCs from a fundamental, algorithmic point\nof view by studying whether or not the corresponding achievability and converse\nbounds on the capacity can be computed algorithmically. For this purpose, the\nconcept of Turing machines is used which provide the fundamental performance\nlimits of digital computers. To this end, computable continuous functions are\nstudied and properties of computable sequences of such functions are\nidentified. It is shown that the capacity of FSCs is not Banach-Mazur\ncomputable which is the weakest form of computability. This implies that there\nis no algorithm (or Turing machine) that can compute the capacity of a given\nFSC. As a consequence, it is then shown that either the achievability or\nconverse must yield a bound that is not Banach-Mazur computable. This also\nmeans that there exist FSCs for which computable lower and upper bounds can\nnever be tight. To this end, it is further shown that the capacity of FSCs is\nnot approximable, which is an even stricter requirement than non-computability.\nThis implies that it is impossible to find a finite-letter entropic\ncharacterization of the capacity of general FSCs. All results hold even for\nfinite input and output alphabets and finite state set. Finally, connections to\nthe theory of effective analysis are discussed. Here, results are only allowed\nto be proved in a constructive way, while existence results, e.g., proved based\non the axiom of choice, are forbidden.\n