Shannon meets Turing: Non-computability and non-approximability of the finite state channel capacity
Shannon meets Turing: Non-computability and non-approximability of the finite state channel capacity
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 …