"The Undecidable Channel"

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.

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.