# 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
\(f\) is sequentially computable, i.e., \(f\) maps every computable sequence \(\{W_{n}\}_{n\in\mathbb{N}}\) with \(W_{n}\in\mathcal{CH}_{c}(\mathcal{X},\mathcal{Y})\) into a computable sequence \(\{f(W_{n})\}_{n\in\mathbb{N}}\) of computable numbers,
2. \(f\) is effectively uniformly continuous, i.e., there is a recursive function \(d:\mathbb{N}\to\mathbb{N}\) such that for all \(W_{1},W_{2}\in\mathcal{CH}_{c}(\mathcal{X},\mathcal{Y})\) and all \(N\in\mathbb{N}\) with \(d_{C}(W_{1},W_{2})\leq\frac{1}{d(N)}\), it holds that \(|f(W_{1})-f(W_{2})|\leq\frac{1}{2^{N}}\). Theorem 7: Let \(\mathcal{X},\mathcal{Y}\) be finite alphabets with \(|\mathcal{X}|\geq 2\) and \(|\mathcal{Y}|\geq 2\). There exists a computable sequence of computable continuous functions \(\{F_{N}\}_{N\in\mathbb{N}}\) on \(\mathcal{CH}_{c}(\mathcal{X},\mathcal{Y})\) with  
1. \(F_{N}(W)\geq F_{N+1}(W)\) with \(W\in\mathcal{CH}(\mathcal{X},\mathcal{Y})\) and \(N\in\mathbb{N}\),
2. \(\  
It holds  
\[\left|\sum_{y\in\mathcal{Y}:W(y|x)>0}Q(y)-\sum_{y\in\mathcal{Y}} \frac{NW(y|x)}{1+NW(y|x)}Q(y)\right|\] \[= \left|\sum_{y\in\mathcal{Y}:W(y|x)>0}\frac{1}{1+NW(y|x)}Q(y)\right|\] \[\leq \frac{1}{1+N\min_{y\in\mathcal{Y}}:W(y|x)>0}\,W(y|x)}.\]  
Therefore, we have  
\[\sum_{y\in\mathcal{Y}:W(y|x)>0}Q(y) \leq \frac{1}{1+N\min_{y\in\mathcal{Y}:W(y|x)>0}W(y|x)}\] \[+\sum_{y\in\mathcal{Y}}\frac{NW(y|x)}{1+NW(y|x)}Q(y).\]  
Because of (18), we have  
\[\Phi_{N}(W)\leq\Psi_{\infty}(W)\]  
for all \(W\in\mathcal{C}H_{c}(\mathcal{X},\mathcal{Y})\). (20) yields  
\[\sum_{y\in\mathcal{Y}:W(y|x)>0}Q(y) \leq \frac{1}{1+N\min_{x\in\mathcal{X}}\left(\min_{y\in\mathcal{Y}:W( y|x)>0}W(y|x)\right)}\] \[\{W\in\mathcal{C}H_{c}(\mathcal{X},\mathcal{Y}):R_{\infty}(W)>\lambda\}\]0  
So,  
\[\{W\in\mathcal{C}H_{c}(\mathcal{X},\mathcal{Y}):R_{\infty}(W)>\lambda\}\]1 \[\{W\in\mathcal{C}H_{c}(\mathcal{X},\mathcal{Y}):R_{\infty}(W)>\lambda\}\]2  
and  
\[\{W\in\mathcal{C}H_{c}(\mathcal{X},\mathcal{Y}):R_{\infty}(W)>\lambda\}\]3  
holds. So, we have  
\[\{W\in\mathcal{C}H_{c}(\mathcal{X},\mathcal{Y}):R_{\infty}(W)>\lambda\}\]4  
We now want to prove that the corresponding question in [34] can be answered positively for \(R_{\infty}\). Theorem 4.1: _Let \(\mathcal{X},\mathcal{Y}\) be finite alphabets with \(|\mathcal{X}|\geq 2\) and \(|\mathcal{Y}|\geq 2\). 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\}\]5is semi-decidable._  
Proof. : We use the computable sequences of computable continuous functions \(F_{N}\) from Theorem 7. It holds that  
\[\{W\in\mathcal{C}H_{c}(\mathcal{X},\mathcal{Y}):R_{\infty}(W)>\lambda\}\]6  
if and only if there is an \(N_{0}\) such that \(F_{N_{0}}<\lambda\) holds. As in the proof of Theorem 28 from [35], we now use the construction of a Turing machine \(TM_{R_{\infty},<\lambda}\), which exactly accepts the set  
\[\{W\in\mathcal{C}H_{c}(\mathcal{X},\mathcal{Y}):R_{\infty}(W)>\lambda\}\]7  
We now consider the approximability \"from below\" (this can be seen as a kind of reachability). We have shown that \(R_{\infty}(\cdot)\) can always be represented as a limit value of monotonically decreasing computable sequences of computable continuous functions. From this, it can be concluded that the sequence is then also a computable sequence of Banach-Mazur computable functions. We now have the following:  
**Theorem 9**. : _Let \(\mathcal{X},\mathcal{Y}\) be finite alphabets with \(|\mathcal{X}|\geq 2\) and \(|\mathcal{Y}|\geq 2\). There does not exist a sequence of Banach-Mazur computable functions \(\{F_{N}\}_{N\in\mathbb{N}}\) with_  
1. \(F_{N}(W)\leq F_{N+1}(W)\) _with_ \(W\in\mathcal{C}H_{c}(\mathcal{X},\mathcal{Y})\) _and_ \(N\in\mathbb{N}\)_;_
2. \(\lim_{N\to\infty}F_{N}(W)=R_{\infty}(W)\) _for all_ \(W\in\mathcal{C}H(\mathcal{X},\mathcal{Y})\)_._  
Proof. : We assume that such a sequence \(\{F_{N}\}_{N\in\mathbb{N}}\) does exist.