# The Computability of the Channel Reliability Function and Related Bounds
## 5 Computability of the Zero-Error Capacity of Noisy Channels with Feedback
Then, \(\max_{1\leq l\leq 2}C_{0}^{FB}(W_{l})>0\) must be, because if \(\max_{1\leq l\leq 2}C_{0}^{FB}(W_{l})=0\), then \(\max_{1\leq l\leq 2}C_{0}(W_{l})=0\), and thus \(C_{0}(W_{1}\otimes W_{2})=0\) also (since the \(C_{0}\) capacity has no super-activation). This means that \(C_{0}^{FB}(W_{1}\otimes W_{2})=0\), which would be a contradiction. If \(\min_{1\leq 2}C_{0}^{FB}(W_{l})>0\), then  
\[F(v,u) = \left(\sum_{l=1}^{|\mathcal{X}|}d_{l}(v)u_{l}\right), \tag{30}\]7 \[F(v,u) = \left(\sum_{l=1}^{|\mathcal{X}|}d_{l}(v)u_{l}\right), \tag{30}\]8 \[F(v,u) = \left(\sum_{l=1}^{|\mathcal{X}|}d_{l}(v)u_{l}\right), \tag{30}\]9  
This is a contradiction, and thus \(\min_{1\leq 2}C_{0}^{FB}(W_{l})=0\). Furthermore, \(\min_{1\leq l\leq 2}R_{\infty}(W_{l})>0\) must apply, because if \(\min_{1\leq l\leq 2}R_{\infty}(W_{l})=0\), then \(R_{\infty}(W_{1})=0\) without loss of generality. Then,  
\[\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),\]0 \[\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),\]1 \[\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),\]2 \[\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),\]3 \[\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),\]4  
because \(C_{0}^{FB}(W_{1})=0\) when \(R_{\infty}(W_{1})=0\). This is again a contradiction. With this, we have proven the theorem. We still want to show for which alphabet sizes the behavior according to Theorem 18 can occur. **Theorem 19**. : _1. If \(|\mathcal{X}_{1}|=|\mathcal{X}_{2}|=|Y_{1}|=|Y_{2}|=2\), then for all \(W_{l}\in\mathcal{C}H(\mathcal{X}_{l},\mathcal{Y}_{l})\) with \(l=1,2\), we have_  
\[\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),\]5  
_2. If \(\mathcal{X}_{1},X_{2},\mathcal{Y}_{1},\mathcal{Y}_{2}\) are non-trivial alphabets with_  
\[\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),\]6  
_then there exists \(\tilde{W}_{l}\in\mathcal{C}H(\mathcal{X}_{l},\mathcal{Y}_{l})\) with \(l=1,2\), such that_  
\[\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),\]7  
Proof. : 1. If \(C_{0}(W_{1})=C_{0}(W_{2})\), then (35) holds, since \(C_{0}(W_{1}\otimes W_{2})=0\). If \(\max\{C_{0}(W_{1}),C_{0}(W_{2})\}>0\), we can assume without loss of generality that \(C_{0}(W_{1})=0\). In this case, \(W_{1}\) must be either \[W_{1}= \begin{pmatrix}1&0\\ 0&1\end{pmatrix} \quad\text{or}\quad W_{1}= \begin{pmatrix}0&1\\ 1&0\end{pmatrix} ,\] which implies that \(C_{0}(W_{2})=1\), and consequently, \(C_{0}^{FB}(W_{2})=1\). Furthermore, if \(R_{\infty}(W_{2})>0\), then \(W_{2}\) must also be one of the two matrices above, ensuring that (35) holds. If instead \(R_{\infty}(W_{2})=0\), Theorem 17 guarantees that (35) remains valid. 2. We now prove (36) under the assumption that \(|\mathcal{X}_{1}|=|\mathcal{Y}_{1}|=2\) and \(|\mathcal{X}_{2}|=|\mathcal{Y}_{2}|=3\). If we have found channels \(\hat{W}_{1},\hat{W}_{2}\) for this case, such that (36) holds, then it is also clear how general case 2 can be proved. We set \(\hat{W}_{1}= \begin{pmatrix}1&0\\ 0&1\end{pmatrix}