(Notes from Chapter 4, Section 4)
Let \(B \subseteq \mathbb{N}^m\). Let \(P(x_1,\ldots,x_m)\) be the characteristic function of \(B\). That is \(P(x_1,\ldots,x_m) = \left \{ \begin{array}{ll} 1 & \text{if } (x_1,\ldots,x_m) \in B \\ 0 & \text{otherwise. } \end{array} \right .\)
We say that \(B\) belongs to some class of functions if \(P(x_1,\ldots,x_m)\) belongs to the class in question.
For example, we say that \(B\) is computable (or recursive) if \(P(x_1,\ldots,x_m)\) is a computable function, and that \(B\) is a primitive recursive set if \(P(x_1,\ldots,x_m)\) is a primitive recursive predicate.
Theorem 4.1. Let the sets \(B,C\) belong to some PRC class \({\cal C}\). Then so do the sets \(B\cup C\), \(B \cap C\), \(\overline{B}\).
Theorem 4.2. Let \({\cal C}\) be a PRC class, and let \(B\) be a subset of \(\mathbb{N}^m\) where \(m \geq 1\). Then \(B\) belongs to \({\cal C}\) iff \[\{ [x_1,\ldots,x_m] \in \mathbb{N} \mid (x_1,\ldots,x_m) \in B\}\] belongs to \({\cal C}\).
Proof. (\(\Rightarrow\)): Let \(B' = \{ [x_1,\ldots,x_m] \in \mathbb{N} : (x_1,\ldots,x_m) \in B\}\). If \(P_B(x_1,\ldots,x_m)\) is the characteristic function of \(B\), then \[P_{B'}(x) \iff P_B((x)_1,\ldots,(x)_m)~\&~\operatorname{Lt}(x) \leq m\] is the characteristic function of \(B'\). (The book has \(\operatorname{Lt}(x) = m\) which is not correct since it requires that \(x_m \neq 0\).) Clearly, if \(P_B\) belongs to \({\cal P}\), so does \(P_{B'}\).
(\(\Leftarrow\)): if \(P_{B'}(x)\) is the characteristic function of \(B'\), then \[P(x_1,\ldots,x_m) \iff P_{B'}([x_1,\ldots,x_m])\] is the characteristic function of \(B\). Clearly, \(P_B\) belongs to \({\cal C}\) if \(P_{B'}\) belongs to \({\cal C}\).
For example, \(\{ [x,y] \in \mathbb{N} \mid \operatorname{HALT}(x,y)\}\) is not a computable set.
The set \(B \subseteq \mathbb{N}\) is called recursively enumerable (abbreviated as r.e.) if there is a partially computable function \(g(x)\) such that \[B = \{ x \in \mathbb{N} \mid g(x)\downarrow\}.\]
Hence, if \({\cal P}\) is a program that computes \(g\), then \(B\) is the set of all inputs to \({\cal P}\) for which \({\cal P}\) eventually halts.
(R.e. sets are also called semi-recursive and semi-computable.)
Theorem 4.3. If \(B\) is a recursive set, then \(B\) is r.e.
Theorem 4.4. The set \(B\) is recursive iff \(B\) and \(\overline{B}\) are both r.e.
Theorem 4.5. If \(B\) and \(C\) are r.e. sets, so are \(B\cup C\) and \(B\cap C\).
Write \[ W_n = \{x \in \mathbb{N} \mid \Phi(x,n) \downarrow \}.\] That is, \(W_n\) is the set of inputs to the program with number \(n\) such that the program eventually halts.
Theorem 4.6. (Enumeration Theorem). A set \(B\) is r.e. iff there is an \(n\) for which \(B = W_n\).
The above theorem gets its name from that \[W_0,W_1,W_2,\ldots\] is an enumeration of all r.e. sets.
Define \[K = \{ n \in \mathbb{N} \mid n \in W_n\}.\] Note that \[n \in W_n \iff \operatorname{HALT}(n,n).\]
Theorem 4.7. \(K\) is r.e. but not recursive.
The next theorem is the main result of this section.
Theorem 4.11. Suppose that \(S \neq \emptyset\). Then the following are equivalent:
\(S\) is r.e.;
\(S\) is the range of a primitive recursive function;
\(S\) is the range of computable (recursive) function;
\(S\) is the range of a partially computable (partial recursive) function.
Proof. \(1 \Rightarrow 2\) follows from Theorem 4.9 below. \(2 \Rightarrow 3 \Rightarrow 4\) is obvious. \(4 \Rightarrow 1\) follows from Theorem 4.10 below. (Note that this theorem provides the motivation for the term recursively enumerable.)
Theorem 4.8. Let \(B\) be an r.e. set. Then there is a primitive recursive predicate \(R(x,t)\) such that \(B = \{ x \in \mathbb{N} \mid (\exists t) R(x,t)\}\).
Theorem 4.9. Let \(S\) be a nonempty r.e. set. Then there is a primitive recursive function \(f(u)\) such that \[S = \{ f(u) \mid n \in \mathbb{N}\}.\] That is, \(S\) is the range of \(f\).
Proof Since \(S\) is nonempty, we can take some \(x_0 \in S\). By Theorem 4.8, \[S = \{ x \mid (\exists t) R(x,t) \}\] for some primitive recursive predicate \(R\). Let \[ f(u) = \left \{\begin{array}{ll} l(u) & \text{if } R( l(u), r(u) ) \\ x_0 & \text{otherwise.} \end{array}\right .\] Note that \(f\) is primitive recursive. Also, \(f(u) \in S\) for all \(u\) since if \(R(l(u), r(u)\) holds, that means \((\exists t)R((l(u),t)\) holds, implying that \(f(u) = l(u) \in S\).
Conversely, if \(x \in S\), then \(R(x,t_0)\) holds for some \(t_0\). Then, \[ f(\langle x, t_0\rangle) = l(\langle x, t_0 \rangle) = x.\]
Theorem 4.10. Let \(f(x)\) be a partially computable function and let \(S = \{ f(x) \mid f(x) \downarrow \}\). Then \(S\) is r.e.
Proof It suffices to show that \[ g(x) = \left \{ \begin{array}{ll} 0 & \text{if } x \in S \\ \uparrow & \text{otherwise} \end{array} \right . \] is partially computable. Let \({\cal P}\) be a program that computes \(f\) and let \(\#({\cal P}) = p\). Then the following program computes \(g(x)\): \[\begin{array}{ll} [A] & \textbf{if } \neg \operatorname{STP}^{(1)}(Z,p,T) \textbf{ goto } B \\ & V \leftarrow f(Z) \\ & \textbf{if } V = X \textbf{ goto } E \\ [B] & Z \leftarrow Z + 1 \\ & \textbf{if } Z \leq T \textbf{ goto } A \\ & T \leftarrow T + 1 \\ & Z \leftarrow 0 \\ & \textbf{goto } A \end{array}\]