## 2 Materials and Methods
Having established the analytic theory of sampling and interpolation, we will now turn to the formalization of its computable variant. To this end, we provide a concise introduction to the theory of Turing machines [1], \(\mu\)-recursive functions [13], and computable analysis [14; 15; 16; 17]. Although mature topics in the field of computer science, they have not yet received much attention within the signal-processing community. Turing machines form an abstract mathematical model for digital computing. In fact, the widely accepted Church-Turing Thesis implies that they form a definitive and universal model of digital computing, i.e., any mathematical problem can (in principle) be solved through a real-world digital computer if and only if it can theoretically be solved by a Turing machine. Hence, if a certain algorithmic problem cannot be solved on a Turing machine, it can definitely not be solved on an actual digital hardware. The algorithms a Turing machine can compute is equivalent to the class of \(\mu\)-recursive functions, c.f. [18] for the proof of equivalence. By \(\mathbb{N}\), we denote the set of natural numbers including zero. Throughout this article, it will occasionally be necessary to exclude zero from \(\mathbb{N}\) to obtain a meaningful mathematical expression. As the reader may easily detect such a necessity from the relevant context, we avoid indicating them explicitly by a distinguished notation. We call a mapping natural-number function if it is of the form \(g:\mathbb{N}^{n}\supseteq\rightarrow\mathbb{N}\), \(n\in\mathbb{N}\), where the symbol \"\(\supseteq\rightarrow\)\" denotes partiality. That is, we have \(\text{dom}(g)\subseteq\mathbb{N}^{n}\). A partial natural-number function is called total if the inclusion is improper, i.e., if we have \(\text{dom}(g)\subseteq\mathbb{N}^{n}\). Then, the set of \(\mu\)-recursive functions \(\mathcal{U}\) consists of all those natural-number functions that we can construct from the sucessor function, constant functions, and projection functions through application of composition, primitive recursion, and unbounded search (Definition 2.1, p. 8, Definition 2.2, p. 10 in [14]). By \(\mathcal{U}(n)\), \(n\in\mathbb{N}\), we denote the set of \(\mu\)-recursive functions in \(n\) arguments, where \(\mathcal{U}(0)\) can be understood as the set \(\mathbb{N}\) itself, i.e., constant functions in zero arguments. Accordingly, we have \(\mathcal{U}(0)\cup\mathcal{U}(1)\cup\mathcal{U}(2)\cup\ldots=\mathcal{U}\). Observe that, generally speaking, \(\mu\)-recursive functions are partial. When Turing machines are modeled as actual state-based machines that perform computations in sequential processing steps, the domain of the corresponding \(\mu\)-recursive function equals the set of inputs for which the Turing machine halts its computation in finite time. A set \(\Omega\subseteq\mathbb{N}\) is called recursively enumerable if it is either empty or the domain of a \(\mu\)-recursive function. Consequently, a set \(\Omega\subseteq\mathbb{N}\) is recursively enumerable if and only if it is either empty or the range of a total \(\mu\)-recursive function. Furthermore, if \(\Omega\) is recursively enumerable, there exists a (total) \(\mu\)-recursive function \(g_{\Omega}:\mathbb{N}^{2}\rightarrow\{0,1\}\) that satisfies the following for all \(n\in\mathbb{N}\):  
* There exists a number \(m\in\mathbb{N}\) such that \(g_{\Omega}(n,m)=1\) is satisfied if and only if \(n\in\Omega\) holds true;
* If \(g_{\Omega}(n,m)=1\) holds true for a number \(m\in\mathbb{N}\), then \(g_{\Omega}(n,k)=1\) holds true for all \(k\in\mathbb{N}\) that satisfy \(k>m\). We call such a function a runtime function for \(\Omega\). A set \(\Omega\subset\mathbb{N}\) is called recursive if both \(\Omega\) and \(\mathbb{N}\setminus\Omega\) are recursively enumerable which, in turn, holds true if and only if the indicator function  
\[\mathds{1}_{\Omega}:\mathbb{N}\to\{0,1\},\ n\mapsto \begin{cases}1&\text{if }n \in\Omega,\\ 0&\text{otherwise},\end{cases}