Shannon meets Gödel-Tarski-Löb: Undecidability of Shannon Feedback Capacity for Finite-State Channels
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914405078269952 |
|---|---|
| author | Majumdar, Angshul |
| author_facet | Majumdar, Angshul |
| contents | We study the exact decision problem for feedback capacity of finite-state channels (FSCs). Given an encoding $e$ of a binary-input binary-output rational unifilar FSC with specified rational initial distribution, and a rational threshold $q$, we ask whether the feedback capacity satisfies $C_{fb}(W_e, π_{1,e}) \ge 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 the real numbers. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_17317 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Shannon meets Gödel-Tarski-Löb: Undecidability of Shannon Feedback Capacity for Finite-State Channels Majumdar, Angshul Information Theory Signal Processing We study the exact decision problem for feedback capacity of finite-state channels (FSCs). Given an encoding $e$ of a binary-input binary-output rational unifilar FSC with specified rational initial distribution, and a rational threshold $q$, we ask whether the feedback capacity satisfies $C_{fb}(W_e, π_{1,e}) \ge 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 the real numbers. 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. |
| title | Shannon meets Gödel-Tarski-Löb: Undecidability of Shannon Feedback Capacity for Finite-State Channels |
| topic | Information Theory Signal Processing |
| url | https://arxiv.org/abs/2603.17317 |