Communications in Information and Systems

Volume 20 (2020)

Number 2

Mathematical Engineering: A special issue at the occasion of the 85th birthday of Prof. Thomas Kailath

Guest Editors: Ali H. Sayed, Helmut Bölcskei, Patrick Dewilde, Vwani Roychowdhury, and Stephen Shing-Toung Yau

Shannon meets Turing: Non-computability and non-approximability of the finite state channel capacity

Pages: 81 – 116

DOI: https://dx.doi.org/10.4310/CIS.2020.v20.n2.a1

Authors

Holger Boche (Institute of Theoretical Information Technology, Technische Universität München (Munich), Germany; and Munich Center for Quantum Science and Technology (MCQST), Munich, Germany)

Rafael F. Schaefer (Information Theory and Applications Chair, Technische Universität Berlin, Germany)

H. Vincent Poor (Department of Electrical Engineering, Princeton University, Princeton, New Jersey, U.S.A.)

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 Text (PDF format)

This work of H. Boche was supported in part by the German Federal Ministry of Education and Research (BMBF) within the national initiative for “Molecular Communication (MAMOKO)” under Grant 16KIS0914 and in part by the German Research Foundation (DFG) within the Gottfried Wilhelm Leibniz Prize under Grant BO 1734/20-1 and within Germany’s Excellence Strategy – EXC-2111 – 390814868.

This work of R. F. Schaefer was supported in part by the BMBF within the national initiative for “Post Shannon Communication (NewCom)” under Grant 16KIS1004 and in part by the DFG under Grant SCHA 1944/6-1. This work of H. V. Poor was supported by the U.S. National Science Foundation under Grants CCF- 0939370, CCF-1513915, and CCF-1908308.

Received 9 February 2020

Published 19 November 2020