# The Computability of the Channel Reliability Function and Related Bounds
## 2 Definitions and Basic Results
### Computable Channels and Computable Performance Functions
_Compute the following two tests in parallel:_ 1. _Use the Turing machine_ \(TM_{>\underline{f}(W)}\) _and test_ \(R>\underline{f}(W)\) _using_ \(TM_{>\underline{f}(W)}\) _for input_ \(R\in\mathbb{R}_{c}\)_._ 2. _Use the Turing machine_ \(TM_{<\overline{f}(W)}\) _and test_ \(R<\overline{f}(W)\) _using_ \(TM_{<\overline{f}(W)}\) _for input_ \(R\in\mathbb{R}_{c}\)_._ _Let these two tests run until both Turing machines stop. If both Turing machines stop in 2, then compute_ \(G(W,R)\) _and set_ \(TM(W,R)=G(W,R)\)_._  
\(TM\) _actually generates a Turing computable performance function, and the Turing machine \(TM\) stops for the input \((W,R)\) if and only if \(R\in(\underline{f}(W),\overline{f}(W))\) applies. Then, it gives the value \(G(W,R)\) as output. This follows from the fact that the Turing machine \(TM_{>\underline{f}(W)}\) stops for input \(R\in\mathbb{R}_{c}\) if and only if \(R>\underline{f}(W)\). The second Turing machine \(TM_{<\overline{f}(W)}\) from 2 stops exactly when \(R<\overline{f}(W)\), i.e. the Turing machine \(TM\) in 2., which simulates \(TM_{>\underline{f}(W)}\) and \(TM_{<\overline{f}(W)}\) in parallel, stops exactly when \(R\in(\underline{f}(W),\overline{f}(W))\) applies._  
**Remark 6**. : _Using the above approach, we can try, for example, to find upper and lower bounds for the channel reliability function by allowing general Turing computable functions \(G:CH(\mathcal{X},\mathcal{Y})_{c}\times\mathbb{R}_{c}^{+}\to\mathbb{R}_{c}\cup \{\bot\}\) and algorithmically determine the interval from \(\mathbb{R}_{c}^{+}\) for which the function \(G(W,\cdot)\) delivers lower or upper bounds for the channel reliability function._  
**Definition 16** (Banach-Mazur computable channel function). : _We call \(f:CH_{c}(\mathcal{X},\mathcal{Y})\to\mathbb{R}_{c}\) a Banach-Mazur computable channel function if every computable sequence \(\{W_{r}\}_{r\in\mathbb{N}}\) from \(CH_{c}(\mathcal{X},\mathcal{Y})\) is mapped by \(f\) into a computable sequence from \(\mathbb{R}_{c}\)._For practical applications, it is necessary to have performance functions that satisfy Turing computability. Depending on \(W\), the channel reliability function or the bounds for this function should be computed. This computation is carried out by an algorithm that also receives \(W\) as input. This means that the algorithm should also be recursively dependent on \(W\); otherwise, a special algorithm would have to be developed for each \(W\) (depending on \(W\) but not recursively dependent), since the channel reliability function for this channel, or a bound for this function, is computed. It is now clear that when defining the Turing computable performance function, the Turing computable channel functions \(\underline{f},\overline{f}\) cannot be dispensed with, because the channel reliability function depends on the specific channel and the permissible rate region for which the function can be computed. For \(\overline{f}\), one often has the representation \(\overline{f}(W)=C(W)\) with \(W\in\mathcal{CH}_{c}(\mathcal{X},\mathcal{Y})\). For \(\underline{f}\), the choice \(\underline{f}(W)=C_{0}(W)\) with \(W\in\mathcal{CH}_{c}(\mathcal{X},\mathcal{Y})\) for the channel reliability function is a natural choice, because the channel reliability function is only useful for this interval. (We note that we showed in [35] that \(C_{0}(W)\) is not Turing computable in general.) For the Turing computability of the channel reliability function or corresponding upper and lower bounds, it is therefore a necessary condition that the dependency of the relevant rate intervals on \(W\) be Turing computable--that is, recursive. **Remark 7**. : _As noted in the Introduction, very few closed-form expressions for performance functions are known in information theory. Even for relatively simple scenarios, such as secure message transmission over a wiretap channel with an active jammer, closed-form solutions are not available (see [54; 55; 56]). Existing methods in information theory provide convergent multi-letter sequences for determining capacity.