# The Computability of the Channel Reliability Function and Related Bounds
## 2 Definitions and Basic Results  
### Basic Concepts of Computability Theory  
In this section, we present the basic definitions and results from computability theory that are necessary for this work. We begin with the fundamental definitions of computability, starting with the concept of a Turing machine [14].  
A Turing machine serves as a mathematical model for what we intuitively understand as computation machines. In this sense, they provide an abstract idealization of modern-day computers. Any algorithm that can be executed by a real-world computer can, in principle, be simulated by a Turing machine, and vice versa. However, unlike real-world computers, Turing machines are not constrained by limitations such as energy consumption, computation time, or memory size. Furthermore, all computation steps on a Turing machine are assumed to be executed flawlessly, with no possibility of error.  
Recursive functions, more specifically known as \(\mu\)_-recursive functions_, form a special subset of the set \(\bigcup_{n=0}^{\infty}\left\{f:\mathbb{N}^{n}\hookrightarrow\mathbb{N}\right\}\), where the symbol \"\(\hookrightarrow\)\" denotes a _partial mapping_. The set of recursive functions provides an alternative characterization of the notion of computability. Turing machines and recursive functions are equivalent in the following sense: a function \(f:\mathbb{N}^{n}\hookrightarrow\mathbb{N}\) is computable by a Turing machine if and only if it is a partial recursive function.  
Next, we introduce several key definitions from _computable analysis_[37; 38; 39], which we will apply in the subsequent sections.  
**Definition 1**.: _A sequence of rational numbers \(\{r_{n}\}_{n\in\mathbb{N}}\) is called a computable sequence if there exist recursive functions \(a,b,s:\mathbb{N}\to\mathbb{N}\) with \(b(n)\
eq 0\) for all \(n\in\mathbb{N}\) and_  
\[r_{n}=(-1)^{s(n)}\frac{a(n)}{b(n)},\ \ n\in\mathbb{N}.\]  
**Definition 2**.: _We say that a computable sequence \(\{r_{n}\}_{n\in\mathbb{N}}\) of rational numbers converges effectively, i.e., computably, to a number \(x\), if a recursive function \(a:\mathbb{N}\to\mathbb{N}\) exists such that \(|x-r_{n}|<\frac{1}{2^{N}}\) for all \(N\in\mathbb{N}\) and all \(n\in\mathbb{N}\) with \(n\geq a(N)\) applies._  
We can now introduce computable numbers.  
**Definition 3**.: _A real number \(x\) is said to be computable if there exists a computable sequence of rational numbers \(\{r_{n}\}_{n\in\mathbb{N}}\), such that \(|x-r_{n}|<2^{-n}\) for all \(n\in\mathbb{N}\). We denote the set of computable real numbers using \(\mathbb{R}_{c}\)._  
Next, we need suitable subsets of the natural numbers.  
**Definition 4**.: _A set \(A\subset\mathbb{N}\) is called recursive if there exists a recursive function \(f\), such that \(f(x)=1\) if \(x\in A\) and \(f(x)=0\) if \(x\in A^{c}\), where \(A^{c}\) stands for the complement set of \(A\)._  
**Definition 5**.: _A set \(A\subset\mathbb{N}\) is recursively enumerable if there exists a recursive function whose domain is exactly \(A\)._  
**Remark 1**.: _For the definition of recursive and partial recursive functions, see [37]. Recursive functions \(f:\mathbb{N}\to\mathbb{N}\) are the building blocks to develop the framework for computing theory on rational numbers, on real numbers, and on related functions defined over these number fields. This theory captures exactly what can be achieved in theory with digital computers in these number fields. We next introduce the concept of computable performance functions on the basis of computability theory. It is important to note that computability theory formalizes exactly what is computable with perfect digital computers._