# The Computability of the Channel Reliability Function and Related Bounds
## 2 Definitions and Basic Results
### Computable Channels and Computable Performance Functions  
We need further basic concepts for computability. We want to investigate the function \(E(W,R)\) and the upper bounds like \(E_{SP}(W,R)\) and \(E_{ex}(W,R)\) for \(k\in\mathbb{N}\) as functions of \(W\) and \(R\). These functions are generally only well defined for fixed channels \(W\) on sub-intervals of \([0,C(W)]\) as functions depending on \(R\). For example, for \(W\in CH(\mathcal{X},\mathcal{Y})\) with \(C_{0}(W)>0\), \(E(W,R)\) is infinite for \(R<C_{0}(W)\). Hence, \(E(W,R)\) must be examined and computed as a function of \(R\) on the interval \((C_{0}(W),C(W)]\). Similar statements also apply to the other functions that have already been introduced. We now fix non-trivial alphabets \(\mathcal{X},\mathcal{Y}\) and the corresponding set \(\mathcal{C}H_{c}(\mathcal{X},\mathcal{Y})\) of the computable channels and \(R\in\mathbb{R}_{c}\). **Definition 14** (Turing computable channel function). : _We call a function \(f:\mathcal{C}H_{c}(\mathcal{X},\mathcal{Y})\to\mathbb{R}_{c}\) a Turing computable channel function if there is a Turing machine that converts any program for the representation of \(W\in\mathcal{C}H_{c}(\mathcal{X},\mathcal{Y})\) into a program for the computation of \(f(W)\)--that is, \(f(W)=TM_{f}(W)\), \(W\in\mathcal{C}H_{c}(\mathcal{X},\mathcal{Y})\)._We want to determine whether there is a closed form for the channel reliability function. For this, we need the following definition, which we discuss in more detail in Remark 5 below. **Definition 15** (Turing computable performance function). : _Let \(\bot\) be a symbol. We call a function \(F:CH(\mathcal{X},\mathcal{Y})_{c}\times\mathbb{R}_{c}^{+}\to\mathbb{R}_{c}\cup \{\bot\}\) a Turing computable performance function if there are two Turing computable channel functions \(\underline{f}\) and \(\overline{f}\) with \(f(W)\leq\overline{f}(W)\) for \(W\in CH_{c}(\mathcal{X},\mathcal{Y})\), and a Turing machine \(TM_{F}\), which is defined for input \(R\in\mathbb{R}_{c}^{+}\) and \(W\in CH_{c}(\mathcal{X},\mathcal{Y})\). The Turing machine \(TM_{F}\) stops for the variables \(R\in\mathbb{R}_{c}^{+}\) and \(W\in CH_{c}(\mathcal{X},\mathcal{Y})\) and any representation for \(W\) and \(R\) as input if and only if \(R\in(\underline{f}(W),\overline{f}(W))\) and the Turing machine \(TM_{F}\) delivers \(F(W,R)=TM_{F}(W,R)\). If \(R\
ot\in(\underline{f}(W),\overline{f}(W))\), then \(TM_{F}\) does not stop._  
**Remark 5**. : _The requirement for function \(F:CH(\mathcal{X},\mathcal{Y})_{c}\times\mathbb{R}_{c}^{+}\to\mathbb{R}_{c} \cup\{\bot\}\) to be a Turing computable performance function is relatively weak. For example, let us take \(W\) and \(R\) as inputs. Then, the interval \((\underline{f}(W),\overline{f}(W))\) is computed first. If \(R\) is now in the interval \(((\underline{f}(W),\overline{f}(W))\), then the Turing machine \(TM_{F}\) must stop for the input \((W,R)\) and deliver the result for \(F(W,R)\). We impose no requirements on the behavior of the Turing machine for input \(W\) and \(R\
ot\in(\underline{f}(W),\overline{f}(W))\). In particular, the Turing machine \(TM_{F}\) does not have to stop for the input \((W,R)\) in this case._  
_Take, for example, any Turing computable function \(G:CH(\mathcal{X},\mathcal{Y})_{c}\times\mathbb{R}_{c}^{+}\to\mathbb{R}_{c}\cup \{\bot\}\) with the corresponding Turing machine \(TM_{G}\). Furthermore, let \(\underline{TM}:CH_{c}(\mathcal{X},\mathcal{Y})\to\mathbb{R}_{c}\) and \(\overline{TM}:CH_{c}(\mathcal{X},\mathcal{Y})\to\mathbb{R}_{c}\) be any two TMs, so that \(\underline{TM}(W)\leq\overline{TM}(W)\) always holds for \(W\in CH_{c}(\mathcal{X},\mathcal{Y})\). Then, the following Turing machine \(TM:CH_{c}(\mathcal{X},\mathcal{Y})\times\mathbb{R}_{c}\to\mathbb{R}_{c}\cup \{\bot\}\) defines a Turing computable performance function._  
1. _For any input_ \(W\in CH_{c}(\mathcal{X},\mathcal{Y})\) _and_ \(R\in\mathbb{R}_{c}\)_, first compute_ \(\underline{f}(W)=\underline{TM}(W)\) _and_ \(\overline{f}(W)=\overline{TM}(W)\)_._
2.