In information theory, we frequently define fundamental physical limits of communication channels, such as channel capacity, zero-error capacity, and the channel reliability function. A natural engineering assumption is that if a physical limit can be mathematically defined, a computer program can eventually be written to calculate it.
However, a profound tension exists between Shannon's information theory and Turing's computability theory: many of these foundational metrics are algorithmically uncomputable. As shown by Deppe et al., fundamental communication metrics like channel capacity and minimum mean square error (MMSE) can be Turing uncomputable even under smooth spectral densities. This algorithmic limitation prevents automated system design tools from relying on the algorithmic determination of these theoretical limits or their sharp upper bounds.
Why Existence Does Not Imply Computability
To understand why these limits evade computation, we must look at how they are mathematically constructed. Many information-theoretic limits are defined as limits over infinite product spaces. A classic tool for proving the existence of such limits is Fekete's lemma.
In On Effective Convergence in Fekete's Lemma and Related Combinatorial Problems in Information Theory, Böck et al. demonstrate that while Fekete's lemma guarantees that a limit value exists, it is structurally insufficient to ensure that the resulting limit is an algorithmically computable number.
The core of the issue lies in the rate of convergence. As noted in the context of Computability of the Zero-Error Capacity with Kolmogorov Oracle, a fundamental limit is only fully computable if there exists a sequence of computable upper bounds that converges to the true value at a known rate. In information theory, this is typically established via "achievability and converse" arguments. Without such a computable converse, the mere mathematical existence of a limit does not guarantee that a standard computer can determine its value to a specific precision in finite time.
The Halting Problem and Finite State Channels
The uncomputability becomes even more concrete when analyzing channels with memory, such as finite state channels (FSCs). In Capacity of Finite State Channels With Feedback: Algorithmic and Optimization Theoretic Properties, Grigorescu et al. establish that the computability of finite state channel capacity is intrinsically linked to the unsolvability of the Turing halting problem. Because a universal capacity-calculating algorithm would inherently be able to solve the halting problem, the feedback capacity of FSCs is fundamentally non-computable, even under weak computability notions like Banach-Mazur computability.
This connection creates a severe practical bottleneck: it is impossible to algorithmically find tight lower and upper bounds for the feedback capacity of unifilar FSCs that are simultaneously computable. Without these simultaneously computable bounds, automated systems cannot establish reliable performance envelopes for communication systems.
Furthermore, as Schaefer explains in Shannon meets Turing: Non-computability and non-approximability of the finite state channel capacity, no universal program can take a description of a communication channel with memory and output its maximum transmission rate. It remains an open question whether channel capacity is at least semidecidable—which would allow an algorithm to verify if a capacity exceeds a certain threshold, even if it runs indefinitely when it does not.
The Breakdown of Approximations and Bounds
One might hope that if exact capacities are uncomputable, we could still approximate them to any desired precision or rely on standard theoretical bounds. However, the uncomputability extends deeply into approximations and reliability metrics.
For instance, Deppe demonstrates in Computability of the Zero-Error Capacity of Noisy Channels that while we can algorithmically determine if a discrete memoryless channel is completely "useless" (having a capacity of zero), no general algorithm can compute or approximate its exact zero-error capacity to a specified precision for all channel configurations.
This limitation also breaks the tools used to analyze error rates in ultra-reliable networks. In The Computability of the Channel Reliability Function and Related Bounds, Deppe proves that the channel reliability function itself is not Turing computable. Crucially, commonly used theoretical bounds—such as the sphere packing bound and the expurgation bound—are also uncomputable. This leaves open the challenging question of whether any non-trivial, Turing-computable upper bounds exist at all, forcing system designers to rely on heuristics rather than universally reliable algorithmic approximations.
Key Foundational Work
Capacity of Finite State Channels With Feedback: Algorithmic and Optimization Theoretic Properties (2024) — contributed 7 concept elements to this direction.
Workshop on Information Theory and Related Fields - In Memory of Ning Cai (2024) — contributed 4 concept elements to this direction.
Shannon meets Turing: Non-computability and non-approximability of the finite state channel capacity (2020) — contributed 3 concept elements to this direction.