318 );;,] Theory of Computer Science
EXAMPLE 10.5
If Land L are both recursively enumerable. show that Land L are recursive.
Solution
Let M 1 and M 2 be two TMs such that L = T(M 1 ) and L =T(M 2 ). We construct
a new two-tape TM M that simulates M] on one tape and M 2 on the otheL
If the input string w of M is in L, then M 1 accepts wand we declare that
M accepts w. If w E [ , then M 2 accepts wand we declare that M halts without
accepting. Thus in both cases, M eventually halts. By the construction of M
it is clear that T(lvl) = T(M]) = L Hence L is recursive. We can show that
[ is recursive, either by applying Example lOA or by interchanging the roles
of M) and M 2 in defining acceptance by M.
EXAMPLE 10.6
Show that A TM is not recursively enumerable.
Solution
We have already seen that A nv ! is recursively enumerable (by Theorem 10.5).
If it TIY! were also recursively enumerable, then A TM is recursive (by
Example 10.5). This ~ a contradiction since A TM is not recursive by
Theorem 10.5. Hence A TM is not recursively enumerable,
EXAMPLE 10.7
Show that the union of two recursively enumerable languages is recursively
enumerable and the union of two recursive languages is recursive.
Solution
Let L 1 and L 2 be two recursive languages and M 1 , M 2 be the corresponding
TMs that halt. We design a Th1 M as a two-tape TM as follows:
1. w is an input string to M.
2. M copies ,von its second tape.
3. M simulates M) on the first tape. If w is accepted by M 10 then M
accepts ,v.
4. M simulates /'11 2 on the second tape. If w is accepted by M 2 , then M
accepts w.
M always halts for any input w.
Tnus L J U L 2 = T(M) and hence L J U L 2 is recursive.
If L) and L 2 are recursively enumerable. then the same conclusion gives
a proof for L) U L 2 to be recursively enumerable. As M 1 and M 2 need not
halt, M need not halt.