Shannon meets Gödel-Tarski-Löb: Undecidability of Shannon Feedback Capacity for Finite-State Channels

Angshul Majumdar · 2026

Read Shannon meets Gödel-Tarski-Löb: Undecidability of Shannon Feedback Capacity for Finite-State Channels by Angshul Majumdar (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-17317.txt.

Introduction

Majumdar proves that an exact decision problem about feedback capacity of finite state channels is undecidable. Given a channel encoding and a rational threshold, the question is whether the feedback capacity meets that threshold. He shows no algorithm can answer all instances, even for a narrow class of rational unifilar channels with bounded state space. A consequence is that the threshold predicate escapes the existential theory of the reals. He links the result to Gödel-Tarski-Löb incompleteness phenomena.

Catalog record

CREATORAngshul Majumdar
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE63689
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.17317

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Shannon meets Gödel-Tarski-Löb: Undecidability of Shannon Feedback Capacity for Finite-State Channels Angshul Majumdar Abstract We study the exact decision problem for feedback capacity of finite-state channels (FSCs). Given an encoding e e of a binary-input binary-output rational unifilar FSC with specified rational initial distribution, and a rational threshold q q , we ask whether the feedback capacity satisfies C fb ​ ( W e , π 1 , e ) ≥ q . C_{\mathrm{fb}}(W_{e},\pi_{1,e})\geq q. We prove that this exact threshold problem is undecidable, even when restricted to a severely constrained class of rational unifilar FSCs with bounded state space. The reduction is effective and preserves rationality of all channel parameters. As a structural consequence, the exact threshold predicate does not lie in the existential theory of the reals ( ∃ ℝ \exists\mathbb{R} ), and therefore cannot admit a universal reduction to finite systems of polynomial equalities and inequalities over ℝ \mathbb{R} . In particular, there is no algorithm deciding all instances of the exact feedback-capacity threshold problem within this class. These results do not preclude approximation schemes or solvability for special subclasses; rather, they establish a fundamental limitation for exact feedback-capacity reasoning in general finite-state settings. At the metatheoretic level, the undecidability result entails corresponding Gödel–Tarski–Löb incompleteness phenomena for sufficiently expressive formal theories capable of representing the threshold predicate. I Introduction I-A Exact feedback-capacity thresholding as a decision problem Shannon’s foundational work established channel capacity as the central operational quantity in communication theory [ 21 , 22 ] . In many classical memoryless settings, capacity admits a clean variational characterization and a well-understood coding theorem. For channels with memory, however, exact capacity analysis is substantially more delicate: the operational quantity remains well-defined, but the associated optimization is typically history-dependent and asymptotic in nature [ 9 , 7 , 10 ] . This paper studies the following exact decision problem for channels with memory and feedback. Given: • an effective encoding e\in\{0,1\}^{\ast} of a binary-input binary-output rational unifilar finite-state channel W_{e} together with its specified rational initial state distribution \pi_{1,e} , and • a rational threshold q\in\mathbb{Q} , determine whether Cfb(W_{e},\pi_{1,e})\geq q. As in Section III , we denote this predicate by Cap(e,q) and the associated language by LCap . The emphasis is on exactness . We are not studying a finite-horizon surrogate, an additive-approximation problem, or a promise-gap variant. The question is whether the exact infinite-horizon feedback-capacity functional crosses a rational threshold. I-B Historical context and the FSC feedback-capacity literature The broader context is the long line of work on channels with memory, finite-state channel (FSC) models, and feedback capacity. Classical information-theoretic treatments already make clear that memory changes the analytical character of capacity problems, even before feedback is introduced [ 9 , 7 , 10 ] . Finite-state models became a central abstraction because they retain a concrete stochastic structure while capturing temporal dependence, hidden channel modes, and input/state/output interactions. In the feedback setting, a key conceptual step was the introduction of directed information by Massey [ 16 ] , which provides the correct information measure for causal communication over channels with memory. This perspective was developed further by Kramer [ 14 ] and underlies modern feedback-capacity formulations for channels with memory and state [ 28 , 27 , 10 ] . For finite-state channels specifically, several milestone results established exact characterizations or computable formulations for important subclasses. In particular, the works of Chen–Berger [ 5 ] , Yang–Kavčić–Tatikonda [ 30 ] , and Permuter–Weissman–Goldsmith [ 17 ] form a canonical core of the FSC feedback-capacity literature. These papers develop dynamic-programming and structural formulations, and they show that substantial progress is possible when one exploits channel-specific properties. A second major thread focuses on unifilar FSCs, where deterministic state evolution given (S_{t},X_{t},Y_{t}) makes finer structural analysis possible. In this line, single-letter upper bounds and graph/context based formulations have led to powerful computable bounds and exact results for important examples [ 19 ] . This thread is especially relevant for the present paper because our undecidability theorem is proved within a rational unifilar FSC class, not outside it. Taken together, the literature shows both sides of the story: • there is deep and successful theory for structured FSC subclasses, and • exact feedback capacity remains intrinsically asymptotic and structurally delicate in general. This naturally raises the foundational question addressed here: whether a universal exact threshold decision procedure can exist for a broad effectively specified FSC class. I-C What is proved here and how it is positioned The main result of this paper is a structural limitation theorem for exact feedback-capacity reasoning. (1) Undecidability of exact thresholding. We prove that the predicate Cap(e,q) is undecidable even for a severely restricted class of channels: binary-input, binary-output, rational, unifilar finite-state channels (with the bounded-state delayed-activation construction used later). Thus, undecidability already appears in a highly concrete and information-theoretically natural FSC family. (2) A barrier to universal real-algebraic exact formulations. We further show that the exact threshold language LCap is not in \exists\mathbb{R} (under the reduction notion fixed later). Equivalently, the exact predicate cannot be captured by a universal existential semialgebraic formulation. This places the problem outside the standard ETR/ \exists\mathbb{R} framework used for many exact geometric and algebraic decision problems [ 4 , 18 , 20 ] . (3) Computability-theoretic consequences for exact certification. From the undecidability theorem and the formal setup in Section III , we derive information-theoretic impossibility consequences: there is no universal exact certified-bounding scheme and no universal finite auxiliary-state/finite-letter exact characterization valid across the full encoded class. (4) Gödel–Tarski–Löb consequences. Finally, once exact capacity-threshold truth is encoded as an arithmetic predicate and shown undecidable, standard meta-theoretic consequences follow for recursively axiomatizable theories extending the base entropic theory T_{0} : incompleteness, undefinability barriers, and Löb-style limitations on uniform internal reflection for exact threshold truth [ 11 , 26 , 15 , 3 , 23 ] . This contribution is not a new computable upper bound, a new dynamic program, or a new single-letter ansatz. It is a boundary theorem explaining why no universal exact framework of that type can exist at the level of generality studied here. I-D What this paper does not claim Because undecidability results are easy to misinterpret, we state the scope explicitly. First, the paper does not contradict the many positive results for structured FSC subclasses. Exact formulas, computable bounds, and dynamic-programming characterizations for special channels remain valid and important [ 5 , 30 , 17 , 19 ] . Second, the paper does not rule out approximation methods, finite-horizon optimization, or decidability under additional assumptions (for example, stronger structural restrictions beyond those imposed here). Our theorem concerns the exact infinite-horizon threshold predicate over the encoded class. Third, the paper does not assert that all capacity-like quantities for channels with memory are undecidable. The statement is narrower and sharper: the exact feedback-capacity threshold problem for the specified unifilar FSC class is undecidable. The correct interpretation is therefore constructive rather than pessimistic: the theorem identifies a rigorous boundary between successful structured exact theories and impossible universal exact theories. I-E An inconspicuous logic bridge The main arguments are information-theoretic and computability-theoretic, but one later consequence is naturally proof-theoretic. Once exact capacity-threshold truth is formalized in the language Lent

Read the complete text