# The Computability of the Channel Reliability Function and Related Bounds
## 1 Introduction  
In [1], [PERSON] established the foundations of information theory by characterizing the key mathematical properties of communication channels. For a transmission rate \(R\) that is less than the channel capacity \(C\), the probability of erroneous decoding with respect to an optimal code decreases exponentially as the code length \(n\in\mathbb{N}\) increases. [PERSON] introduced the channel reliability function \(E(R)\) as being the exponent governing this exponential decrease in relation to the transmission rate \(R\). A major goal in information theory is to find a closed-form expression for the channel reliability function. This expression should be computable and fully determined by the parameters of the communication task. Naturally, we must define what constitutes a closed-form expression. In [2], [PERSON], and in [3], [PERSON] and [PERSON] discuss different approaches to defining closed-form expressions. All of the various representations satisfy the requirement that the corresponding functions can be computed algorithmically using a digital computer. This can be achieved with great precision, depending on the inputs within their domain of definition. [PERSON]'s characterization of the capacity for message transmission via the discrete memoryless channel (DMC) in [1], [PERSON]'s characterization of the capacity for message transmission via the multiple access channel in [4], and [PERSON] and [PERSON]'s characterization of the identification capacity for DMCs in [5] are all significant examples of closed-form solutions using elementary functions. These provide important instances of the computability of the corresponding performance functions, as defined in the previous context. The precise definition of computability, as outlined by [PERSON], is presented in Section 2. [PERSON]'s characterization of the zero-error capacity for the pentagram also represents a closed-form number according to [PERSON]'s definition in [2], which can be computedalgorithmically--an outcome that is desirable. However, the characterization of the zero-error capacity for a cyclical heptagon remains an open problem. Moreover, it is still unclear whether the zero-error capacities of DMCs can take computable values for computable channels. Additionally, the algorithmic computability of the broadcast capacity region is still uncertain. In the age of artificial intelligence, it is increasingly important to determine whether a digital computer can solve a given problem or compute a given function. Since every function that can be computed by a digital computer can also be computed by a Turing machine (as will be discussed in more detail below), this question is reduced to asking whether a function is computable. It is therefore crucial to distinguish between determining how to compute the zero-error capacity and whether it is computable at all. In this work, we focus on the latter: the computability of the zero-error capacity. The Lovasz \(\theta\)-function for graphs was analyzed in [6] from three distinct research perspectives related to various graph invariants. This investigation resulted in new insights into the Shannon capacity of graphs, observations on cospectral and nonisomorphic graphs, and bounds on graph invariants while also serving as a tutorial in zero-error information theory and algebraic graph theory. Further observations on the Lovasz \(\theta\)-function are provided by the author in [7]. In this paper, we provide a negative answer to the question of whether the channel reliability function and several related bounds are algorithmically computable by Turing machines. Significant research has been conducted on the channel reliability function, but many aspects of its behavior remain unresolved (see surveys [8] and [9]). In fact, a complete characterization of the channel reliability function is still unknown for binary-input binary-output channels. As a result, considerable efforts have been made to derive computable lower and upper bounds for the function (see [10; 11; 12]).