(Notes from Chapter 4, Sections 4.6 - 4.8)
Let \(\operatorname{TOT}\) be the set of all numbers \(p\) such that \(p\) is the number of a program that computes a total function of one variable. That is, \[\operatorname{TOT} = \{ z \in \mathbb{N} \mid (\forall x)\Phi(x,z) \downarrow \}.\]
In other words, \(\operatorname{TOT}\) is the set of numbers \(z\) such that \(W_z = \mathbb{N}\).
Theorem 6.1. \(\operatorname{TOT}\) is not r.e.
Let \(A,B\) be sets. \(A\) is many-one reducible to \(B\), written \(A \leq_m B\), if there is a computable function \(f\) such that \[ A = \{x \in \mathbb{N} \mid f(x) \in B\}.\]
Theorem 6.2. Suppose that \(A \leq_m B\).
If \(B\) is recursive, then \(A\) is recursive.
If \(B\) is r.e., then \(A\) is r.e.
Let \[K_0 = \{ \langle x, y \rangle \mid \Phi_y(x) \downarrow \}.\]
Fact. If \(A\) is r.e., then \(A\) is many-one reducible to \(K_0\).
Proof. Let \(g(x)\) be a partially computable function such that \(A = \{x \mid g(x) \downarrow \}\). Let \(z_0\) be the number for a program that computes \(g\). Then \begin{eqnarray*} A & = & \{ x \in \mathbb{N} \mid \Phi(x,z_0) \downarrow \} \\ & = & \{ x \in \mathbb{N} \mid \langle x, z_0 \rangle \in K_0 \}. \end{eqnarray*}
A set \(A\) is m-complete if
\(A\) is r.e.;
for every r.e. set \(B\), \(B \leq_m A\).
Hence, \(K_0\) is m-complete. In fact, \(K\) can be shown to be m-complete. The first step is to show that \(K_0 \leq_m K\). Then establish the following.
Theorem 6.3. If \(A \leq_m B\) and \(B \leq_m C\), then \(A \leq_m C\).
Corollary 6.4. If \(A\) is m-complete, \(B\) is r.e., and \(A \leq_m B\), then \(B\) is m-complete.
Proof. Let \(C\) be r.e. Since \(A\) is m-complete, \(C \leq_m A\). As \(A \leq_m B\) by assumption, we have \(C \leq_m B\) by Theorem 6.3.
We write \(A \equiv_m B\) if \(A \leq_m B\) and \(B \leq_m A\).
In summary, we have
Theorem 6.5.
\(K\) and \(K_0\) are m-complete.
\(K \equiv_m K_0\).
Let \[\operatorname{EMPTY} = \{ x \in \mathbb{N} \mid W_x = \emptyset\}.\]
Theorem 6.6. \(\operatorname{EMPTY}\) is not r.e.
Proof. Since \(K\) is r.e. but not recursive, \(\overline{K}\) is not r.e. We show that \(\overline{K} \leq_m \operatorname{EMPTY}\).
Let \({\cal P}\) be the program \[Y \leftarrow \Phi(X_2,X_2).\] Let \(p = \#({\cal P})\). Note that \({\cal P}\) halts if and only if \(\Phi(X_2,X_2)\) is defined.
By the parameter theorem, \[\psi_{\cal P}^{(2)}(x_1,x_2) =\Phi^{(2)}(x_1,x_2,p) = \Phi^{(1)}(x_1, S_1^1(x_2,p)).\] So for any \(z\), \begin{eqnarray*} z \in \overline{K} & \iff & \Phi(z,z) \uparrow \\ & \iff & \psi_{\cal P} (x,z) \uparrow \text{ for all } x \\ & \iff & \Phi^{(1)} (x,S_1^1(z,p)) \uparrow \text{ for all } x \\ & \iff & W_{S_1^1(z,p)} = \emptyset \\ & \iff & S_1^1(z,p) \in \operatorname{EMPTY} \end{eqnarray*} Since \(f(z) = S_1^1(z,p)\) is computable, we get \(\overline{K} \leq_m \operatorname{EMPTY}\) as desired.
Define the predicate \(P(x) \iff \Phi_x(x) = 1\). We show that \(P(x)\) is not computable.
Suppose to the contrary that \(P(x)\) is computable. Define \[ h(x) = \left \{ \begin{array}{ll} 0 & \text{if } \Phi_x(x) = 1\\ 1 & \text{otherwise.} \end{array} \right.\] Then \(h\) is computable. Let \(z_0\) be a number such that \(h(x) = \Phi_{z_0}(x)\). Since \(h\) is total, \(\Phi_{z_0}(x)\downarrow\) for all \(x\). From the definition of \(h\), we have \[ \Phi_{z_0}(x) = 1 \iff \Phi_x(x) \neq 1.\] Setting \(x = z_0\), we obtain \[ \Phi_{z_0}(z_0) = 1 \iff \Phi_{z_0}(z_0) \neq 1,\] a contradiction.
Let \(\Gamma\) be some collection of partially computable functions of one variable. Define \[R_\Gamma = \{t \in \mathbb{N} \mid \Phi_t \in \Gamma\}.\]
Theorem 7.1 (Rice's Theorem). Let \(\Gamma\) be a collection of partially computable functions of one variable. Let there be partially computable functions \(f(x)\) and \(g(x)\) such that \(f(x)\) belongs to \(\Gamma\) but \(g(x)\) does not. Then \(R_\Gamma\) is not recursive.
Theorem 8.1 (Recursion Theorem). Let \(g(z,x_1,\ldots,x_m)\) be a partially computable function of \(m+1\) variables. Then there is a number \(e\) such that \[ \Phi_e^{(m)}(x_1,\ldots,x_m) = g(e,x_1,\ldots,x_m).\]
Proof. Note that \[g( S_m^1(v,v),x_1,\ldots,x_m)\] is an \(m\)-ary partially computable function where \(S_m^1\) is as in the parameter theorem. Then, there exists \(z_0\) such that \[\Phi^{(m+1)}(x_1,\ldots,x_m, v, z_0) = g( S_m^1(v,v),x_1,\ldots,x_m).\] But by the parameter theorem, we have \[\Phi^{(m+1)}(x_1,\ldots,x_m, v, z_0) = \Phi^{(m)}(x_1,\ldots,x_m, S_m^1(v, z_0)).\] Setting \(v = z_0\) and \(e = S_m^1(z_0,z_0)\), we have \[g( e,x_1,\ldots,x_m) = \Phi^{(m))}(x_1,\ldots,x_m, e)= \Phi_e^{(m))}(x_1,\ldots,x_m)= .\]
We can use the recursion theorem to prove that \(\operatorname{HALT}(x,y)\) is not computable. If it were computable, then \[ f(x,y) = \left \{\begin{array}{ll} \uparrow & \text{if } \operatorname{HALT}(y,x) \\ 0 & \text{otherwise} \end{array}\right.\] would be partially computable. So by the recursion theorem, there exists \(e\) such that \[ \Phi_e(y) = f(e,y) = \left \{\begin{array}{ll} \uparrow & \text{if } \operatorname{HALT}(y,e) \\ 0 & \text{otherwise} \end{array}\right.\] This gives, \[\neg \operatorname{HALT}(y,e) \iff \operatorname{HALT}(y,e),\] a contradiction.
The recursion theorem can be used to justify definitions of functions based on more complex forms of recursion. Let \(g, h\) be computable functions. Let \(a \in \mathbb{N}\). Suppose we want to determine if there is a partially computable function satisfying \begin{eqnarray*} f(0) & = & a \\ f(y+1) & = & h(y, f(g(y))) \end{eqnarray*}
Define \[ F(z,y) = \left \{ \begin{array}{ll} a & \text{if } y = 0 \\ h(y~\dot{-}~1, \Phi_z( g(y~\dot{-}~1))) & \text{otherwise}. \end{array}\right.\] Clearly, \(F(z,y)\) is partially computable. By the recursion theorem, there exists \(e\) such that \[\Phi_e(y) = F(e,y) = \left \{ \begin{array}{ll} a & \text{if } y = 0 \\ h(y~\dot{-}~1, \Phi_e( g(y~\dot{-}~1))) & \text{otherwise}. \end{array}\right.\] Thus, we can set \(f\) to \(\Phi_e\).
Corollary 8.2. There is a number \(e\) such that for all \(x\), \[\Phi_e(x) = e.\]
Proof. Applying the recursion theorem to the computable function \[g(z,x) = u_1^2(z,x) = z,\] we obtain a number \(e\) such that \[ \Phi_e(x) = g(e,x) = e.\]
Theorem 8.3 (Fixed Point Theorem). Let \(f(z)\) be a computable function. Then there is a umber \(e\) such that \[ \Phi_{f(e)} (x) = \Phi_e(x)\] for all \(x\).
Proof. Let \(g(z,x) = \Phi_{f(z)}(x)\). Then \(g\) is partially computable. By the recursion theorem, there exists a number \(e\) such that \[\Phi_e(x) = g(e,x) = \Phi_{f(e)}(x).\]
Proof of Rice's Theorem. Suppose that \(R_\Gamma\) were computable. Then the predicate \(P_\Gamma\) defined by \[ P_\Gamma (t) \iff t \in R_\Gamma\] is computable. Define \[ h(t,x) = \left \{\begin{array}{ll} g(x) & \text{if } P_\Gamma(t) \\ f(x) & \text{otherwise.} \end{array}\right.\] Then \(h\) is partially computable. By the recursion theorem, there exists a number \(e\) such that \[\Phi_e(x) = h(e,x) = \left \{\begin{array}{ll} g(x) & \text{if } e \in R_\Gamma \\ f(x) & \text{otherwise.} \end{array}\right.\]
Thus, if \(e \in R_\Gamma\), then \(\Phi_e(x) = g(x)\), implying that \(e \notin R_\Gamma\) since \(g(x)\) does not belong to \(\Gamma\).
But if \(e \notin R_\Gamma\), then \(\Phi_e(x) = f(x)\), implying that \(e \in R_\Gamma\) since \(f\) belongs to \(\Gamma\).
Thus, \(e \in R_\Gamma \iff e\notin R_\Gamma\), a contradiction.