# The Computability of the Channel Reliability Function and Related Bounds
## 1 Introduction
Determining the behavior of the channel reliability function across the entire interval \((0,C)\) is a challenging problem. Various approaches have attempted to compute the reliability function algorithmically by constructing sequences of upper and lower bounds. The first significant contribution in this direction was made by [PERSON], [PERSON], and [PERSON] in [13]. A fundamental question that arises is whether the reliability function can be computed in this manner. To investigate this, we employ the framework of Turing computability [14]. In general, a function is considered Turing computable if there exists an algorithm capable of computing it. The Turing machine serves as the most fundamental and powerful model of computation, underpinning theoretical computer science. Unlike physical computers, which have practical constraints, a Turing machine is an abstract mathematical construct that can be rigorously analyzed using formal mathematical methods. It is important to note that the Turing machine represents the ultimate performance limit of current digital computers, including supercomputers. A Turing machine models an algorithm or a program, where computation consists of step-by-step manipulation of symbols or characters that are read from and written to a memory tape according to a set of rules. These symbols can be interpreted in various ways, including as numbers. To perform computations on abstract sets, the elements of the set must be encoded as strings of symbols on the tape. This approach allows Turing computability to be defined for real and complex numbers. The use of digital computers to compute approximations of channel capacities or channel reliability functions has been a prominent topic in information theory. The computation of channel capacity for discrete memoryless channels (DMCs) is a convex optimization problem, and in 1972, an algorithm for approximating the capacity of a DMC on digital computers was independently published in [15] and [16]. Even for binary symmetric channels with rational crossover probabilities (excluding the case \(p=\frac{1}{2}\)), the channel capacity is a transcendental number. As a result, despite the relative simplicity of these channels, their capacity can only be approximated with finite precision by digital computers. In contrast to the problem of computing channel capacity, determining the behavior of the channel reliability function over the entire interval \((0,C)\subset\mathbb{R}\) is a significantly more complex task. A common approach to this challenge involves considering sequences of upper and lower bounds for \(E(R)\) (see [13]). In general, the _channel reliability function_ is a well-studied topic in information theory. Originally introduced and analyzed for discrete memoryless channels (DMCs), the concept has since been significantly extended to various other scenarios and channel models. In [17], the reliability function of a DMC was studied at rates above capacity. Subsequent refinements and theoretical bounds were proposed, such as the Poor-Verdu upper bound addressed in [18]. Extensions beyond DMCs include continuous channels and channels with feedback or secrecy constraints. For instance, upper bounds for Gaussian channels were developed in [19], while the role of feedback in Poisson and Gaussian channels was explored in [20; 21]. The impact of signal constraints was analyzed in [22], and improved Gaussian channel bounds were proposed in [23]. Secrecy considerations and cost constraints were incorporated into the analysis of the reliability and secrecy functions in [24]. The reliability function in the presence of side information, as in the Gelfand-Pinsker channel, was considered in [25]. More recently, a new upper bound for DMCs was given in [26], and noisy feedback for binary symmetric channels was studied in [27]. These developments culminated in the analysis of reliability functions in quantum communication settings. Foundational work includes [28; 29], and recent advancements include [30].