# The Computability of the Channel Reliability Function and Related Bounds
## 7 Conclusions  
We have shown that the channel reliability function is not a Turing computable performance function. The same conclusion holds for the functions associated with the sphere packing bound and the expurgation bound. An interesting aspect of our work is that the constraints we impose on Turing computable performance functions are strictly weaker than those typically required for Turing computable functions. Specifically, we do not require that the Turing machine halt for all inputs \((W,R)\in\mathcal{C}_{h}\times\mathbb{R}_{c}^{+}\). This means we allow the Turing machine to compute indefinitely for certain inputs, i.e., it may never halt for some inputs. Consequently, we permit performance functions that are not defined for all \((W,R)\in\mathcal{C}_{h}\times\mathbb{R}_{c}^{+}\). However, we do require the Turing machine to halt for inputs \((W,R)\in\mathcal{C}_{h}\times\mathbb{R}_{c}\) whenever the performance function \(F\) is defined, and in such cases, the machine must return the computable value \(F(W,R)\) as output. This ensures that the algorithm generated corresponds to the number \(F(W,R)\) according to Definition 15. Additionally, we considered the \(R_{\infty}\) function and the zero-error feedback capacity, both of which play a critical role in the context of the channel reliability function. We demonstrated that neither the \(R_{\infty}\) function nor the zero-error feedback capacity is Banach-Mazur computable. Furthermore, we proved that the \(R_{\infty}\) function is additive. We also established that for all finite alphabets \(\mathcal{X},\mathcal{Y}\) with \(|\mathcal{X}|\geq 2\) and \(|\mathcal{Y}|\geq 2\), the channel reliability function itself is not a Turing computable performance function. Moreover, we showed that the commonly studied bounds, which have been extensively examined in the literature, are also not Turing computable performance functions. It remains unclear whether non-trivial upper bounds for the channel reliability function that are Turing computable even exist. In [13], the sequence of \(k\)-letter expurgation bounds was considered an effective method for approximating the channel reliability function. It was hoped that these sequences could be computed more efficiently using modern digital computers. However, we have shown that this is not the case. Table 1 gives an overview of the main results of the paper. As mentioned in the Introduction, future communication systems, such as 6G, will face stringent requirements for trustworthiness. Ultra-reliability, along with the corresponding performance functions, is central to 6G, and this paper addresses that challenge. It is currently unclear how the non-Turing computability of performance functions will impact the system evaluation and certification of future communication systems. A recent study [62] showed that the non-Turing computability of performance functions in artificial intelligence (AI) leads to digital AI algorithms being unable to meet essential legal requirements. It is an intriguing research question whether similar issues might arise in the context of communication systems. This work does not claim that machine learning or artificial intelligence (AI) approaches are useless for computing capacity functions. Rather, it demonstrates that certain solutions cannot be found by such methods, or that a computer may not be able to assess how close a given result is to the optimum. Nevertheless, employing machine learning tools remains valuable; one must simply be aware that these approaches do not always guarantee optimality. In such cases, alternative theoretical frameworks may be necessary. Turing computability and Banach-Mazur computability are two central notions in the theory of computation. Every function that is Turing computable is also Banach-Mazur computable, meaning that Banach-Mazur computability subsumes Turing computability. However, the converse does not hold: not every Banach-Mazur computable function is Turing computable.