# The Computability of the Channel Reliability Function and Related Bounds
## 2 Definitions and Basic Results
### Basic Concepts of Information Theory  
To define the reliability function and its related functions, we first need the definition of a discrete memoryless channel. In the theory of transmission, the receiver must be in a position to successfully decode all the messages transmitted by the sender. Let \(\mathcal{X}\) be a finite alphabet, and denote the set of all probability distributions on \(\mathcal{X}\) using \(\mathcal{P}(\mathcal{X})\). We define the set of computable probability distributions, \(\mathcal{P}_{c}(\mathcal{X})\), as the subset of \(\mathcal{P}(\mathcal{X})\) consisting of all distributions \(P\in\mathcal{P}(\mathcal{X})\) for which \(P(x)\in\mathbb{R}_{c}\) holds for all \(x\in\mathcal{X}\). Furthermore, for finite alphabets \(\mathcal{X}\) and \(\mathcal{Y}\), let \(\mathcal{CH}\) denote the set of all conditional probability distributions (or channels) \(P_{\mathcal{Y}|\mathcal{X}}:\mathcal{X}\to\mathcal{P}(\mathcal{Y})\). We define \(\mathcal{CH}_{c}\) as the set of computable conditional probability distributions, i.e., those for which \(P_{\mathcal{Y}|\mathcal{X}}(\cdot|x)\in\mathcal{P}_{c}(\mathcal{Y})\) holds for every \(x\in\mathcal{X}\). Let \(M\subset\mathcal{CH}_{c}(\mathcal{X},\mathcal{Y})\). We call \(M\) semi-decidable if and only if there is a Turing machine \(TM_{M}\) that either stops or computes forever, depending on whether \(W\in M\) is true. This means \(TM_{M}\) exactly accepts the elements of \(M\), and for an input \(W\in M^{c}=\mathcal{CH}_{c}(\mathcal{X},\mathcal{Y})\setminus M\), it computes forever. **Definition 6**. : _A discrete memoryless channel (DMC) is a triple \((\mathcal{X},\mathcal{Y},W)\), where \(\mathcal{X}\) is the finite input alphabet, \(\mathcal{Y}\) is the finite output alphabet, and \(W(y|x)\in\mathcal{C}H(\mathcal{X},\mathcal{Y})\), with \(x\in\mathcal{X}\), \(y\in\mathcal{Y}\). The probability that a sequence \(y^{n}\in\mathcal{Y}^{n}\) is received if \(x^{n}\in\mathcal{X}^{n}\) was sent is defined by_  
\[W^{n}(y^{n}|x^{n})=\prod_{j=1}^{n}W(y_{j}|x_{j}).\]  
**Definition 7**. : _A (deterministic) block code \(\mathcal{C}(n)\) with rate \(R\) and block length \(n\) consists of_  
* _A message set_ \(\mathcal{M}=\{1,2,...,M\}\) _with_ \(M=2^{nR}\in\mathbb{N}\)_;_
* _An encoding function_ \(e:\mathcal{M}\to\mathcal{X}^{n}\)_;_
* _a_Adecoding function_ \(d:\mathcal{Y}^{n}\to\mathcal{M}\)_._  
_We call such a code an \((R,n)\)-code._  
**Definition 8**. : _Let \((\mathcal{X},\mathcal{Y},W)\) be a DMC. Using \(\mathcal{C}(n)\), we denote a block code with the block length \(n\) and message set \(\mathcal{M}\)._  
1. _The individual message probability of error is defined by the conditional probability of error, given that message_ \(m\in\mathcal{M}\) _is transmitted:_ \[P_{e}(\mathcal{C}(n),W,m)=\Pr\{d(Y^{n})\
eq m|X^{n}=e(m)\}.\]
2. _We define the average probability of error by_ \[P_{e\text{av}}(\mathcal{C}(n),W)=\frac{1}{|\mathcal{M}|}\sum_{m\in\mathcal{M} }P_{e}(\mathcal{C}(n),W,m).\]  
\(P_{e,\text{av}}(W,R,n)\) _denotes the minimum error probability_ \(P_{e,\text{av}}(\mathcal{C}(n),W)\) _over all block codes_ \(\mathcal{C}(n)\) _of block length_ \(n\) _and with message set_ \(\mathcal{M}=2^{nR}\)_._
3. _We define the maximal probability of error by_ \[P_{e,\text{max}}(\mathcal{C}(n),W)=\max_{m\in\mathcal{M}}P_{e}(\mathcal{C}(n),W,m).\]  
\(P_{e,\text{max}}(W,R,n)\) _denotes the minimum error probability_ \(P_{e,\text{max}}(\mathcal{C}(n),W)\) _over all block codes_ \(\mathcal{C}(n)\) _of block length_ \(n\) _and with message set_ \(\mathcal{M}=2^{nR}\)_._
4. _The Shannon capacity for a channel_ \(W\in\mathcal{C}H(\mathcal{X},\mathcal{Y})\) _is defined by_ \[C(W):=\sup\{R:\lim_{n\to\infty}P_{e,\text{max}}(W,R,n)=0\}.\]
5. _The zero-error capacity for a channel_ \(W\in\mathcal{C}H(\mathcal{X},\mathcal{Y})\) _is defined by_ \[C_{0}(W):=\sup\{R:P_{e,\text{max}}(W,R,n)=0\text{ for some }n\}.\]  
**Remark 2**.