248 COMPUTABILITYTHEORY
Example 5.27 Show that the set EMP = {z 1 WX = 8) is not recursive.
Proof. First, we note that
EMP = {z 1 wa: = 0) = {x 1 (Vy)(W) [halt(y, qt) = 01).
So, by the projection theorem, EMP is r.e. Thus, we try to show that EMP is
not recursive by a reduction from the halting problem K = {Z ] II: E WZ} to
EMP.
For any string x E (0, l}*, we construct a DTM W as follows:
On input Z, A.4’ erases x and write a:Bz on the tape. Then M’
simulates the universal DTM U on input (x, z). If the simulation
halts, then M’ halts and accepts the input; otherwise, it does not
halt.
Clearly, M’ will accept any input if U accepts (z, z) or, equivalently, if Ma:
accepts X. Also, M’ will not accept any input if Ma: does not accept X. Let y
be the code of the DTM M’, then the function f(z) = y is a reduction from
Ii’ to EMP.
It is left to show that f is a recursive function. For any fixed Z, let M” be
the DTM that, on any input x, outputs X. That is, M” computes the constant
function Ii’: (z) Z X. Then, it is easy to see that the function fi(z) = [code
of M”] is a primitive recursive function.
Next, we claim that the function fz(u, V) = [the code of the DTM M that
computes the composition of $&&,] is primitive recursive. To see this, assume
that maxstate = t. Then, to get M, all we need to do is to change each
state pi in Mu to qi+(t-+ and combine the new TM with M,. In Exercise
1 of Section 5.1, we showed that changing a state in the code of a DTM is a
primitive recursive operation. Thus, f:! is primitive recursive.
Now, we note that f (2) = f2(% f2(c, fl@))), w l-l ere c is the code of the
DTM that copies the input z into xBz, and u is the code of the universal
DTM U. Therefore, f is primitive recursive. It follows that Ii’ <m - EMP, and
so EMP (and hence EMP) is not recursive since K is not recursive. cl
Let us examine the above proof of K srn EMP more carefully. The proof
can be divided into two steps. First, we need to prove that the DTM M’
exists; that is, the function
1 if Mz halts on X,
g(Z) = { T otherwiseis a partial recursive function. Second, we need to argue that the code y of M’
can be computed from the code of Ma: (by a DTM); or, equivalently, we need
to show that the function f(z) = y is recursive. In the above, we only gave
an informal proof for the second step and relied on the Church-Turing Thesis
to support its correctness. Since many other proofs use similar arguments, we
formalize it below as a technical lemma, called the s-m-n theorem.