# The Computability of the Channel Reliability Function and Related Bounds
## 1 Introduction
In this work, we explore whether it is possible to compute the channel reliability function in this manner using a mathematically rigorous formalization of computability. Specifically, our analysis is based on the theory of Turing machines and recursive functions. In many cases, there is no direct characterization of the behavior of a general function over an abstract set in terms of an algorithm on a Turing machine. Consequently, a common strategy is to approximate the function successively using a sequence of computable upper and lower bounds, for which an algorithm is available. One can then ask the weaker question of whether it is possible to approximate the function in a computable manner. This requires computable sequences of computable upper and lower bounds. This approach is also necessary for the reliability function, and we conducted this analysis. Unfortunately, our results show that the channel reliability function is not a Turing computable performance function when the channel is considered as input. We also examine several other closely related functions, including the \(R_{\infty}\) function, the sphere packing bound function, the expurgation bound function, and the zero-error feedback capacity, all of which are closely tied to the reliability function. We treat all of these functions as functions of the channel. As envisioned, the sixth generation (6G) of mobile networks will introduce a wide range of new features [31]. These innovations bring new challenges to the design of wireless communication systems. Specifically, the Tactile Internet will enable not only the control of data but also the manipulation of physical and virtual objects [31]. With such applications, there arises an increased need to ensure the trustworthiness of the system and its services [32; 33]. 6G will impose more diverse and demanding quality-of-service (QoS) requirements on network resilience, reliability, service availability, and delay [31]. The channel reliability function plays a vital role in the reliability and delay performance analysis of communication systems. It is therefore of interest to explore whether the reliability and delay performance of communication systems can be verified automatically on digital hardware [33]. Analyzing the channel reliability function with respect to Turing computability becomes crucial in this context. The question of Turing computability for performance functions is a central issue in information theory, as closed-form expressions are only known for a few performance functions. It is therefore important to compute corresponding performance functions on available computers with provable performance, ensuring the strict requirements for future communication systems [31; 33]. The structure of this paper is as follows. In Section 2, we begin by presenting the basic definitions and known results that will be used throughout the paper. Section 3 focuses on the \(R_{\infty}\) function. We examine the decidability of connected sets with the \(R_{\infty}\) function and demonstrate that only an approximation from below is possible. This has implications for the sphere packing bound, and we show that it is not a Turing computable performance function. In Section 4, we analyze the reliability function and prove that it is also not Turing computable. The same result holds for the expurgation bound. In Section 5, we investigate the zero-error feedback capacity, which is closely related to the \(R_{\infty}\) function. We first address a question posed by [PERSON] and [PERSON] in [34] regarding the zero-error capacity with feedback, specifically for the case without feedback (which was examined in [35]). We then show that the zero-error feedback capacity is not Banach-Mazur computable and cannot be approximated by computable increasing sequences of computable functions. Additionally, we characterize the superadditivity of the zero-error feedback capacity and demonstrate that the \(R_{\infty}\) function is additive. In Section 6, we analyze the behavior of the expurgation bound rates.