# The Computability of the Channel Reliability Function and Related Bounds
## 5 Computability of the Zero-Error Capacity of Noisy Channels with Feedback
For all \(\lambda\in\mathbb{R}_{c}\) with \(0\leq\lambda<\log_{2}\min\{|\mathcal{X}|,|\mathcal{Y}|\}\), the sets \(\{W\in\mathcal{C}H_{c}(\mathcal{X},\mathcal{Y}):C_{0}^{FB}(W)<\lambda\}\) are semi-decidable. Now, we want to look at the consequences of the results above for \(C_{0}^{FB}\). The same statements apply here as in section 3 for \(R_{\infty}\) with regard to the approximation from below. \(C_{0}^{FB}\) cannot be approximated by monotonically increasing sequences. There is an elementary relationship between \(R_{\infty}\) and \(C_{0}^{FB}\), which we use in the following. Again, we assume that \(\mathcal{X},\mathcal{Y}\) are finite non-trivial alphabets. We remember the following functions:  
\[C_{0}^{FB}=\log_{2}\frac{1}{\overline{\
u}_{\infty}(W)}.\]1  
where \(\Psi_{\infty}(W)=\max_{Q\in\mathcal{P}(\mathcal{Y})}\min_{x\in\mathcal{X}} \sum_{y:W(y|x)>0}Q(y)\). \[C_{0}^{FB}=\left\{ \begin{array}{ll}0&C_{0}(W)=0\\ G(W)&C_{0}(W)>0\end{array} ,\right. \tag{24}\]  
where \(G(W)=\log_{2}\frac{1}{\Psi_{\infty}(W)}\) and  
\[\Psi_{\infty}(W)=\min_{p\in\mathcal{P}(\mathcal{X})}\min_{y\in\mathcal{Y}} \sum_{x:W(y|x)>0}P(x). \tag{25}\]  
Let \(A(W)\) be the \(|\mathcal{Y}|\times|\mathcal{X}|\) matrix with \((A(W))_{kl}\in\{0,1\}\) for \(1\leq k\leq|\mathcal{Y}|\) and \(1\leq l\leq|\mathcal{X}|\), such that \((A(W))_{kl}=1\) if and only if \(W(k(l))>0\). Furthermore, let  
\[\mathcal{M}_{\mathcal{X}}=\left\{u\in\mathbb{R}^{|\mathcal{X}|}:u=\left( \begin{array}{c}u_{1}\\ \ldots\\ u_{|\mathcal{X}|}\end{array} \right),u_{l}\geq 0,\sum_{l=1}^{|\mathcal{X}|}u_{l}=1\right\} \tag{26}\]  
and  
\[\mathcal{M}_{\mathcal{Y}}=\left\{v\in\mathbb{R}^{|\mathcal{Y}|}:v=\left( \begin{array}{c}v_{1}\\ \ldots\\ v_{|\mathcal{Y}|}\end{array} \right),v_{l}\geq 0,\sum_{l=1}^{|\mathcal{Y}|}v_{l}=1 \right\}. \tag{27}\]For \(v\in\mathbb{R}^{|\mathcal{Y}|}\) and \(u\in\mathbb{R}^{|\mathcal{X}|}\), we consider the function \(F(v,u)=v^{T}A(W)u\). The function \(F\) is concave in \(v\in\mathcal{M}_{\mathcal{Y}}\) and convex in \(u\in\mathcal{M}_{\mathcal{X}}\). \(\mathcal{M}_{\mathcal{Y}}\) and \(\mathcal{M}_{\mathcal{X}}\) are closed convex and compact sets, and \(F(v,u)\) is continuous in both variables. So,  
\[\max_{v\in\mathcal{M}_{\mathcal{Y}}}\min_{u\in\mathcal{M}_{\mathcal{X}}}F(v,u)= \min_{u\in\mathcal{M}_{\mathcal{X}}}\max_{v\in\mathcal{M}_{\mathcal{Y}}}F(v,u). \tag{28}\]  
Let \(v\in\mathcal{M}_{\mathcal{Y}}\) be fixed. Then,  
\[F(v,u) = \left(\sum_{l=1}^{|\mathcal{X}|}\left(\sum_{k=1}^{|\mathcal{Y}|}v _{k}A_{kl}(W)\right)u_{l}\right) \tag{29}\] \[F(v,u) = \left(\sum_{l=1}^{|\mathcal{X}|}d_{l}(v)u_{l}\right), \tag{30}\]  
with \(d_{l}(v)=\sum_{k=1}^{|\mathcal{Y}|}v_{k}A_{kl}(W)\). Now, \(d_{l}(v)\geq 0\) for \(1\leq l\leq|\mathcal{X}|\). Hence,  
\[\min_{u\in\mathcal{M}_{\mathcal{X}}}F(v,u)=\min_{1\leq l\leq|\mathcal{X}|}d_{l }(v)=\min_{1\leq l\leq|\mathcal{X}|}\sum_{k:A_{kl}(W)>0}v_{k}=\min_{x\in \mathcal{X}}\sum_{y:W(y|x)>0}Q_{v}(y),\]  
with \(Q_{v}(y)=v_{y}\) for \(y\in\{1,\ldots,|\mathcal{Y}|\}\). So,  
\[\max_{v\in\mathcal{M}_{\mathcal{Y}}}\min_{u\in\mathcal{M}_{\mathcal{X}}}F(v,u )=\max_{Q\in\mathcal{P}(\mathcal{Y})}\min_{x\in\mathcal{X}}\sum_{y:W(y|x)>0}Q_ {v}(y)=\Psi_{\infty}(W).\]  
Furthermore, for \(u\in\mathcal{M}_{\mathcal{X}}\) fixed,  
\[F(v,u) = \left(\sum_{k=1}^{|\mathcal{Y}|}\left(\sum_{l=1}^{|\mathcal{X}|}u _{l}A_{kl}(W)\right)v_{k}\right)\] \[= \left(\sum_{k=1}^{|\mathcal{Y}|}\beta_{k}(u)v_{k}\right),\]  
with \(\beta_{k}(u)=\sum_{l=1}^{|\mathcal{X}|}u_{l}A_{kl}(W)\geq 0\) and \(1\leq k\leq|\mathcal{Y}|\). Therefore,  
\[\max_{v\in\mathcal{M}_{\mathcal{Y}}}F(v,u)=\max_{1\leq k\leq|\mathcal{Y}|}\beta _{k}(u)=\max_{1\leq k\leq|\mathcal{Y}|}\sum_{l:A_{kl}(W)>0}u_{l}=\max_{y\in \mathcal{Y}}\sum_{x:W(Y|x)>0}p_{u}(x)\]  
with \(p_{u}(x)=u_{x}\) for \(1\leq x\leq|\mathcal{X}|\). It follows that  
\[\min_{u\in\mathcal{M}_{\mathcal{X}}}\max_{v\in\mathcal{M}_{\mathcal{Y}}}F(v,u )=\min_{p\in\mathcal{P}(\mathcal{X})}\max_{y\in\mathcal{Y}}\sum_{x:W(y|x)>0}P( x)=\Psi_{\infty}(W).\]  
We get the following lemma.