# The Computability of the Channel Reliability Function and Related Bounds
## 5 Computability of the Zero-Error Capacity of Noisy Channels with Feedback  
In this section, we consider the zero-error capacity for noisy channels with feedback. In our paper [35], we examined the properties of the zero-error capacity without feedback. Let \(W\in\mathcal{C}H(\mathcal{X},\mathcal{Y})\). We already noted that [PERSON] showed in [40] that  
\[C^{FB}_{0}=\left\{ \begin{array}{ll}0&\text{if }C_{0}(W)=0\\ \max_{P}\min_{y}\log_{2}\frac{1}{\sum_{x:W(y|x)>0}P(x)}&\text{otherwise}.\end{array} \right. \tag{21}\]  
From (15), recall that  
\[\Psi_{\infty}(W)=\max_{p\in\mathcal{P}(\mathcal{X})}\min_{y\in\mathcal{Y}} \sum_{x:W(y|x)>0}P(x). \tag{22}\]Then, we have for \(W\) with \(C_{0}(W)\
eq 0\),  
\[C_{0}^{FB}=\log_{2}\frac{1}{\overline{\
u}_{\infty}(W)}.\]  
We know that \(C_{0}^{FB}(W)=R_{\infty}(W)\) if \(C_{0}(W)>0\). If \(C_{0}(W)=0\), then there is a channel \(W\) with \(C_{0}^{FB}(W)=0\) and \(R_{\infty}>0\). Like in Lemma 1, we can show the following:  
Lemma 2: _Let \(\mathcal{X},\mathcal{Y}\) be finite non-trivial alphabets. It holds that_  
\[C_{0}^{FB}:CH_{c}(\mathcal{X},\mathcal{Y})\rightarrow\mathbb{R}_{c}.\]  
From Theorem 5 and the relationship between \(C_{0}\) and \(C_{0}^{FB}\), we get the following results for \(C_{0}^{FB}\), which we have already proved for \(C_{0}\) in [35]. Theorem 13: _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\leq\lambda<\log_{2}\min\{|\mathcal{X}|,|\mathcal{Y}|\}\), the sets \(\{W\in CH_{c}(\mathcal{X},\mathcal{Y}):C_{0}^{FB}(W)>\lambda\}\) are not semi-decidable._  
Theorem 14: _Let \(\mathcal{X},\mathcal{Y}\) be finite alphabets with \(|\mathcal{X}|\geq 2\) and \(|\mathcal{Y}|\geq 2\). Then, \(C_{0}^{FB}:CH_{c}(\mathcal{X},\mathcal{Y})\rightarrow\mathbb{R}\) is not Banach-Mazur computable._  
Now, we will prove the following:  
Theorem 15: _Let \(\mathcal{X},\mathcal{Y}\) be finite alphabets with \(|\mathcal{X}|\geq 2\) and \(|\mathcal{Y}|\geq 2\). There is a computable sequence of computable continuous functions \(G\) with_  
1. \(G_{N}(W)\geq G_{N+1}(W)\) _for_ \(W\in CH(\mathcal{X},\mathcal{Y})\) _and_ \(N\in\mathbb{N}\)_;_
2. \(\lim_{n\rightarrow\infty}G_{N}(W)=C_{0}^{FB}(W)\) _for_ \(W\in CH(\mathcal{X},\mathcal{Y})\)_._  
Proof: We use for \(N\in\mathbb{N}\), \(y\in\mathcal{Y}\) and \(P\in\mathcal{P}(\mathcal{X})\) the function  
\[\sum_{x\in\mathcal{X}}\frac{NW(y|x)}{1+NW(y|x)}P(x).\]  
Then, for  
\[\Phi_{N}(W)=\min_{P\in\mathcal{P}(\mathcal{X})}\max_{y\in\mathcal{Y}}\sum_{x \in\mathcal{X}:W(y|x)>0}P(x),\]  
we have the same properties as in Theorem 7 and  
\[U_{N}(W)=\log_{2}\frac{1}{\Phi_{n}(W)}\]  
is an upper bound for \(C_{0}^{FB}\), which is monotonically decreasing. Now, the relation \(C_{0}^{FB}(W)>0\) holds for \(W\in CH(\mathcal{X},\mathcal{Y})\) if and only if there are two \(x_{1},x_{2}\in\mathcal{X}\) so that  
\[\sum_{y\in\mathcal{Y}}W(y|x_{1})W(y|x_{2})=0\]  
holds. We now set \(g(\hat{x},x)=\sum_{y\in\mathcal{Y}}W(y|\hat{x})W(y|x)=g(W,\hat{x},x)\) and have \(0\leq g(\hat{x},x)\leq 1\) for \(x,\hat{x}\in\mathcal{X}\). \(g\) is a computable continuous function with respect to \(W\in CH(\mathcal{X},\mathcal{Y})\). Now, we set  
\[V_{N}(W)=\left(1-\prod_{x,\hat{x}}g(W,\hat{x},x)^{N}\right)U_{N}(W)\]for \(N\in\mathbb{N}\). \(\{V_{N}\}_{N\in\mathbb{N}}\) is thus a computable sequence of computable continuous functions. Obviously, \(V_{N}(W)\geq V_{N+1}(W)\) for \(W\in\mathcal{C}H(\mathcal{X},\mathcal{Y})\) and \(N\in\mathbb{N}\) is satisfied. \[(1-\prod_{x,\xi}g(W,x,hx))^{N}=1\]  
if and only if \(C_{0}^{FB}>0\). So, for \(C_{0}^{FB}(W)=0\), we always have  
\[\lim_{N\to\infty}V_{N}(W)=0.\]  
For \(W\) with \(C_{0}^{FB}(W)\),  
\[C_{0}^{FB}=\log_{2}\frac{1}{\overline{\
u}_{\infty}(W)}.\]0  
This is shown in the proof of Theorem 7. This immediately gives us the following theorem. Theorem 16: Let \(\mathcal{X},\mathcal{Y}\) be finite alphabets with \(|\mathcal{X}|\geq 2\) and \(|\mathcal{Y}|\geq 2\).