# The Computability of the Channel Reliability Function and Related Bounds
## 4 Computability of the Channel Reliability Function and the Sequence of Expurgation Bound Functions  
In this section, we consider the reliability function and the expurgation bound and show that these functions are not Turing computable performance functions. With the help of the results from [35] for \(C_{0}\) for noisy channels, we immediately get the following theorem:  
**Theorem 11**. : _Let \(\mathcal{X},\mathcal{Y}\) be finite alphabets with \(|\mathcal{X}|\geq 2\) and \(|\mathcal{Y}|\geq 2\). The channel reliability function \(E(\cdot,\cdot)\) is not a Turing computable performance function for \(\mathcal{C}H_{c}(\mathcal{X},\mathcal{Y})\times\mathbb{R}_{c}\)._  
Proof. : Here, \(f(W)=C_{0}(W)\) for \(W\in\mathcal{C}H_{c}(\mathcal{X},\mathcal{Y})\) is a Turing computable function, according to Definition 14. We already know that \(C_{0}\) is not Banach-Mazur computable on \(\mathcal{C}H_{c}(\mathcal{X},\mathcal{Y})\). This gives the proof in the same way as for the sphere packing bound, i.e., the proof of Theorem 10. Now, we consider the rate function for the expurgation bound. The \(k\)-letter expurgation bound \(E_{ex}(W,R,k)\) as a function of \(W\) and \(R\) is a lower bound for the channel reliability function. The latter can only be finite for certain intervals \((R_{k}^{ex}(W),C(W))\). Thus, we want to compute the function in these intervals. In their famous paper [13], [PERSON], [PERSON], and [PERSON] examined the sequence of functions \(\{E_{ex}(\cdot,\cdot,k)\}_{k\in\mathbb{N}}\) and analyzed the relationship to the channel reliability function. They conjectured that for all \(W\in\mathcal{C}H(\mathcal{X},\mathcal{Y})\) for all \(R\) with \(E(W,R)<+\infty\) (one would have convergence and also \(E_{ex}(W,R,k)<+\infty\)), the relation  
\[\lim_{k\to\infty}E_{ex}(W,R,k)=E(W,R)\]  
holds. This conjecture was first refuted in [42] and later refuted by a simpler example in [43]. It was already clear with the introduction of the channel reliability function that it had a complicated behavior. A closed-form formula for the channel reliability function is not yet known, and the results of this paper show that such a formula cannot exist. [PERSON], [PERSON], and [PERSON] tried in [13] in 1967 to find sequences of seemingly simple formulas for the approximation of the channel reliability function. It seems that they considered the sequence of the \(k\)-letter expurgation bounds to be very good channel data for its approximation. It was hoped that these sequences could be computed more easily with the use of new powerful digital computers. Let us now examine the sequence \(\{E_{ex}(\cdot,\cdot,k)\}_{k\in\mathbb{N}}\). We have already introduced the concept of computable sequences of computable continuous channel functions. We now introduce the concept of computable sequences of Turing computable performance functions. **Definition 18**. : _A sequence \(\{F_{k}\}_{k\in\mathbb{N}}\) of Turing computable performance functions is called a computable sequence if there is a Turing machine that generates the description of \(F_{k}\) for input \(k\) according to the definition of the function \(F_{k}\) for the values for which the function is defined._  
In the following theorem, we prove that the sequence of the \(k\)-letter expurgation bounds is not a computable sequence of computable performance functions. So, the hope mentioned above cannot be fulfilled. **Theorem 12**. : _Let \(\mathcal{X},\mathcal{Y}\) be finite alphabets with \(|\mathcal{X}|\geq 2\) and \(|\mathcal{Y}|\geq 2\). The sequence of the expurgation lower bounds \(\{E_{ex}(\cdot,\cdot,k)\}_{k\in\mathbb{N}}\) is not a computable sequence of Turing computable performance functions._  
Proof. : We prove the theorem by contradiction, assuming that there exists a Turing machine \(TM_{*}\) that generates a description of the function \(E_{ex}(\cdot,\cdot,k)\) for a given input \(k\), as definedin its formulation.