We've hit a math wall: there are some internet connections where it’s literally impossible to figure out how fast they can go.
March 19, 2026
Original Paper
Shannon meets Gödel-Tarski-Löb: Undecidability of Shannon Feedback Capacity for Finite-State Channels
arXiv · 2603.17317
The Takeaway
By linking the laws of information to the logic of Gödel, this paper shows that there are some data transmission problems that no algorithm can ever solve. It reveals a fundamental and permanent 'blind spot' in our ability to optimize how we send information through certain networks.
From the abstract
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, \pi_{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