Shannon meets Turing: non-computability and non-approximability of the finite state channel capacity
From MaRDI portal
Publication:2225199
DOI10.4310/CIS.2020.V20.N2.A1zbMATH Open1470.94069arXiv2008.13270MaRDI QIDQ2225199FDOQ2225199
Holger Boche, H. Vincent Poor, Rafael F. Schaefer
Publication date: 5 February 2021
Published in: Communications in Information and Systems (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/2008.13270
Recommendations
- The capacity of finite-state channels in the high-noise regime
- Algorithmic complexity of quantum capacity
- Capacity and a lower bound to<tex>R_{mbox{comp}}</tex>for a channel with symbol fission
- On the computation of covert channel capacity
- Capacity of Finite State Channels Based on Lyapunov Exponents of Random Matrices
This page was built for publication: Shannon meets Turing: non-computability and non-approximability of the finite state channel capacity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2225199)
