A Turing machine is a tuple $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$ where $Q$ is a finite set of states, $\Sigma$ is the input alphabet, $\Gamma \supseteq \Sigma \cup \{\sqcup\}$ is the tape alphabet, $\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$ is the transition function, $q_0$ is the start state, and $q_{\text{accept}}, q_{\text{reject}}$ are halting states.

A partial function $f: \mathbb{N}^k \rightharpoonup \mathbb{N}$ is computable (or recursive) if there exists a Turing machine that, on input $(n_1, \ldots, n_k)$, halts with $f(n_1, \ldots, n_k)$ on its tape when $f$ is defined, and does not halt otherwise. A total computable function is one that halts on all inputs.

A set $A \subseteq \mathbb{N}$ is decidable (recursive) if its characteristic function $\chi_A$ is computable. $A$ is computably enumerable (c.e., or recursively enumerable) if $A = \operatorname{dom}(f)$ for some computable partial function $f$, or equivalently, $A$ is the range of a total computable function (when $A$ is non-empty).