Shannon's channel capacity with feedback for finite-state channels is one of the most natural quantities in information theory. The channel model is finite: bounded states, rational parameters, deterministic transitions. Everything about the description is computable.
Majumdar proves the capacity question is not. The threshold predicate—“Is the feedback capacity at least r?”—is undecidable even when restricted to rational unifilar channels with bounded state spaces. No algorithm can answer this question in general.
Note (2026-11-15; read against the paper's full text): the paper's result is that the exact threshold question (is the feedback capacity at least a rational q) is undecidable for a restricted class, binary-input binary-output rational unifilar finite-state channels with bounded state space. It says explicitly that it does not rule out approximation schemes, finite-horizon optimization, or solvability for special subclasses, and that exact formulas and computable bounds for structured subclasses remain valid. So the essay's 'no tools suffice' is stronger than the paper's scope. The incompleteness consequence is stated for sound, recursively axiomatizable theories that can represent the threshold predicate, as statements Cap(e, q) over that class; I found no mention of ZFC, so the essay's closing line about proof 'within ZFC of what that number is' is the essay's own wording.
The proof connects the capacity computation to Gödel-Tarski-Löb machinery. The threshold predicate does not lie in the existential theory of the reals, so you cannot reduce it to polynomial feasibility. The undecidability further implies incompleteness: any sufficiently expressive formal theory must contain true statements about specific feedback capacities that it cannot prove.
This is not “we lack the tools.” It is: no tools suffice. For specific channels where the capacity exists and is a definite real number, there may be no proof within ZFC of what that number is.
The surprise is where the complexity hides. The channel has finitely many states. The transition function is a lookup table. The input alphabet is finite. Every component is trivially computable. But the capacity lives in the asymptotic limit—infinitely many channel uses—and the limit concentrates enough computational complexity to embed undecidable problems. Finiteness of a model's description does not guarantee decidability of its asymptotic behavior. The complexity is not in the parts; it is in the infinite iteration of the parts.