The Computability of the Channel Reliability Function and Related Bounds

Holger Boche, Christian DeppeAlgorithms 2025 · DOI

TL;DR

This paper delves into the fundamental question of whether key performance metrics in information theory, specifically the channel reliability function and related bounds, are computable by digital computers. The authors demonstrate that, surprisingly, these crucial functions are not Turing computable in general, implying that there's no universal algorithm that can calculate them for all possible communication channels. This has significant implications for designing and verifying future communication systems, especially as we move towards ultra-reliable networks.

What Problem Does This Paper Address?

In information theory, understanding how reliably data can be transmitted over a noisy channel is paramount. The channel reliability function, denoted as $E(W, R)$, quantifies the exponential rate at which decoding errors decrease as code length increases for a given transmission rate $R$ over a channel $W$. Finding a simple, closed-form expression for this function that can be computed by a digital computer has been a long-standing goal. While some related concepts like channel capacity have well-defined computable expressions, the reliability function and its associated bounds (like the sphere packing bound and expurgation bound) have proven more elusive.

The challenge lies in the fact that these functions depend not only on the transmission rate but also on the specific characteristics of the communication channel itself. The authors aim to determine if there exists a general algorithmic procedure (a Turing machine) that can compute these functions for any given channel and rate, or if inherent limitations prevent such a universal computation. This is crucial for practical applications where we need to verify system performance with provable guarantees.

Methods

The paper leverages the formal framework of Turing computability and Banach-Mazur computability. A function is considered Turing computable if there exists an algorithm (simulated by a Turing machine) that can compute its value for any valid input. Banach-Mazur computability is a related but potentially weaker notion.

The authors' approach involves:

  • Formal Definitions: Precisely defining concepts like computable sequences, computable numbers, computable channels, and computable performance functions using the language of computability theory.
  • Analyzing Related Functions: Investigating the computability of functions closely tied to the reliability function, such as the $R_\infty$ function and the zero-error feedback capacity.
  • Constructing Counterexamples/Proof by Contradiction: Demonstrating non-computability by showing that assuming computability leads to a logical contradiction. This often involves constructing specific channels or sequences of functions that violate the properties required for computability.
  • Leveraging Existing Results: Building upon prior work on channel capacity and related bounds, particularly concerning their semi-decidability and Banach-Mazur computability.

Datasets

Not discussed in the paper. The paper deals with theoretical functions and channels, not empirical datasets.

Key Insights and Ideas

  • The Uncomputable Nature of Reliability: The most striking finding is that the channel reliability function, a cornerstone of information theory for understanding error performance, is not Turing computable in general. This means there's no universal algorithm that can compute it for every possible communication channel.
  • Bounds Share the Same Fate: Crucially, the commonly used upper and lower bounds for the reliability function, such as the sphere packing bound and the expurgation bound, are also shown to be non-Turing computable. This limits our ability to approximate the reliability function algorithmically in a universally reliable way.
  • $R_\infty$ and Zero-Error Feedback Capacity are Also Problematic: The $R_\infty$ function and the zero-error feedback capacity, which are important in their own right and related to the reliability function, are found to be not even Banach-Mazur computable. This indicates a deeper level of non-computability.
  • Implications for Future Systems (e.g., 6G): The paper highlights that as communication systems become more complex and demand ultra-reliability (like in 6G), the non-computability of these performance metrics poses a challenge for system verification and certification. It raises questions about how to ensure trustworthiness when fundamental performance measures cannot be universally computed.
  • The Power of Formal Computability: The work underscores the importance of formal computability theory in revealing the fundamental limits of what can be computed, even in seemingly well-defined mathematical areas like information theory.

Key Results

  • The channel reliability function $E(W, R)$ is not a Turing computable performance function.
  • The sphere packing bound ($E_{sp}(W, R)$) and the expurgation bound ($E_{ex}(W, R, k)$) are also not Turing computable performance functions.
  • The $R_\infty$ function is not Banach-Mazur computable and is additive.
  • The zero-error feedback capacity ($C_{FB}^0(W)$) is not Banach-Mazur computable.
  • The paper establishes conditions under which certain related functions are or are not semi-decidable or Banach-Mazur computable, providing a detailed map of their computational properties.

Limitations and Future Work

  • Unclear Existence of Computable Upper Bounds: While the paper shows that common bounds are not Turing computable, it remains an open question whether any non-trivial upper bounds for the channel reliability function exist that are Turing computable.
  • Practical Implications for AI/ML: The authors note that while machine learning and AI are powerful tools, their limitations in computing capacity functions (and thus potentially reliability) mean they might not always find optimal solutions or guarantee closeness to optimality. This suggests a need for alternative theoretical frameworks.
  • Impact on System Verification: A key area for future work is to understand how the non-Turing computability of these performance functions will impact the system evaluation and certification of future communication systems, particularly in the context of stringent requirements like those for 6G. The paper draws a parallel to AI systems facing legal requirements, hinting at similar challenges in communication systems.

Summary updated

BibTeX
@article{boche2025computability,
  author = {Holger Boche and Christian Deppe},
  title = {{The Computability of the Channel Reliability Function and Related Bounds}},
  journal = {Algorithms},
  year = {2025},
  doi = {10.3390/a18060361},
}
Figure