# The Computability of the Channel Reliability Function and Related Bounds
## 3 Results for the Rate Function \(R_{\infty}\) and Applications on the Sphere Packing Bound  
In this section, we analyze the function \(R_{\infty}\) and its implications for the sphere packing bound. Specifically, we demonstrate that \(R_{\infty}\) is not a Turing computable performance function. We begin by expressing \(R_{\infty}(W)\) as  
\[R_{\infty}(W)=\min_{Q\in\mathcal{P}(\mathcal{Y})}\max_{x\in\mathcal{X}}\log_{2 }\frac{1}{\sum_{y:W(y|x)>0}Q(y)}. \tag{14}\]  
From this, we derive the equivalent representations:\[R_{\infty}(W) = \min_{Q\in\mathcal{P}(\mathcal{Y})}\max_{x\in\mathcal{X}}\log_{2} \frac{1}{\sum_{y:W(y|x)>0}Q(y)}\] \[= \min_{Q\in\mathcal{P}(\mathcal{Y})}\log_{2}\frac{1}{\min_{x\in \mathcal{X}}\sum_{y:W(y|x)>0}Q(y)}\] \[= \log_{2}\min_{Q\in\mathcal{P}(\mathcal{Y})}\frac{1}{\min_{x\in \mathcal{X}}\sum_{y:W(y|x)>0}Q(y)}\] \[= \log_{2}\frac{1}{\overline{\Psi_{\infty}(W)}},\]  
where  
\[\Psi_{\infty}(W)=\max_{Q\in\mathcal{P}(\mathcal{Y})}\min_{x\in \mathcal{X}}\sum_{y:W(y|x)>0}Q(y). \tag{15}\]  
In summary, the following holds true: let \(\mathcal{X},\mathcal{Y}\) be arbitrary non-trivial finite alphabets; then, for \(W\in\mathcal{C}H_{c}(\mathcal{X},\mathcal{Y})\)  
\[R_{\infty}(W)=\log_{2}\frac{1}{\overline{\Psi_{\infty}(W)}}. \tag{16}\]  
**Lemma 1**. : _It holds that_  
\[R_{\infty}:\mathcal{C}H_{c}(\mathcal{X},\mathcal{Y})\to\mathbb{R}_{c}.\]  
Proof. : Let \(W\) be fixed. We consider the vector \(\Big{(}Q(1)\quad\cdots\quad Q(|\mathcal{Y}|)\Big{)}^{\mathsf{T}}\) of the convex set  
\[\mathcal{M}_{Prob}=\{u\in\mathbb{R}^{|\mathcal{Y}|}:u= \begin{pmatrix}u_{1}\\ \vdots\\ u_{|\mathcal{Y}|}\end{pmatrix} ,u_{l}\geq 0,l=1,\ldots,|\mathcal{Y}|,\sum_{l}u_{l}=1\}.\]  
\(G(u):=\min_{x}\sum_{y:W(y|x)>0}u_{y}\) is a computable continuous function on \(\mathcal{M}_{Prob}\). Thus, for \(\Psi_{\infty}(W)=\max_{u\in\mathcal{M}_{Prob}}G(u)\), we always have \(\Psi_{\infty}(W)\in\mathbb{R}_{c}\) with \(\Psi_{\infty}(W)>0\), and thus \(R_{\infty}(W)\in\mathbb{R}_{c}\). **Remark 8**. : _We do not know whether \(C_{0}:\mathcal{C}H_{c}(\mathcal{X},\mathcal{Y})\to\mathbb{R}_{c}\) holds for any finite \(\mathcal{X},\mathcal{Y}\). This statement holds for \(\max\{|\mathcal{X}|,|\mathcal{Y}|\}\leq 5\), but the general case is open._  
For finite alphabets \(\mathcal{X},\mathcal{Y}\) and \(\lambda\in\mathbb{R}_{c}\) with \(\lambda>0\), we want to analyze the set  
\[\{W\in\mathcal{C}H_{c}(\mathcal{X},\mathcal{Y}):R_{\infty}(W)>\lambda\}.\]  
To accomplish this, we refer to the proof of Theorem 23 in [35]. Along the same lines, one can show that the following holds true:  
**Theorem 5**. : _Let \(\mathcal{X},\mathcal{Y}\) be non-trivial finite alphabets. For all \(\lambda\in\mathbb{R}_{c}\) with \(0<\lambda<\log_{2}(\min\{|\mathcal{X}|,|\mathcal{Y}|\})\), the set_  
\[\{W\in\mathcal{C}H_{c}(\mathcal{X},\mathcal{Y}):R_{\infty}(W)>\lambda\}\]  
_is not semi-decidable._The following theorem can be derived from a combination of the proof of Theorem 5 and Theorem 24 in [35]. The proof is carried out in the same way as the proof of Theorem 24 in [35]. Theorem 6: _Let \(\mathcal{X},\mathcal{Y}\) be non-trivial finite alphabets. The function \(R_{\infty}:\mathcal{CH}_{c}(\mathcal{X},\mathcal{Y})\to\mathbb{R}\) is not Banach-Mazur computable._  
We now prove a stronger result then what we were able to show for \(C_{0}\) in [35] so far. We show that the analogous question, like the question in [34] for \(C_{0}\) for the function \(R_{\infty}\), can be answered positively. We need a concept of distance for \(W_{1},W_{2}\in\mathcal{CH}(\mathcal{X},\mathcal{Y})\). Therefore, for fixed and finite alphabets \(\mathcal{X},\mathcal{Y}\), we define the distance between \(W_{1}\) and \(W_{2}\) based on the total variation distance  
\[d_{C}(W_{1},W_{2})=\max_{x\in\mathcal{X}}\sum_{y\in\mathcal{Y}}|W_{1}(y|x)-W_{ 2}(y|x)|. \tag{17}\]  
Definition 17: A function \(f:\mathcal{CH}(\mathcal{X},\mathcal{Y})\to\mathbb{R}\) is called computable continuously if the following are true:  
1.