Problem Solving in Automata, Languages, and Complexity

5.2 R.E. Sets and Recursjve Sets 233

Theorem 5.8 (Projection Theorem) Let A - C (0, l}*. The followiplg are

equivalent:

(Q) There exists a primitive recursive predicate R such that A = {x 1 (3~)

R(x, Y)b

(b) There exists a recursive predicate R such that A = {x 1 (3y)R(x, y)}.

(c) A is r.e.

Proof. The direction (a) 3 (b) is ’ t rivial. The direction (b) ) (c) is proved

in Example 4.37. For (c) 3 (a), we assume that A = VI& and note that,

from Lemma 5.6, Wn = {x 1 (3t)haEt(x, n,t)}. 0

The

us look

above two theorems can often simplify our proofs abou t r.e. sets. Let

at some examples.

Example 5.9 Assume that sets A und B are r.e. Show that sets A U B and

A n B are also r.e.

Proof 1 (by the product DTM). Assume that A = I$& and B = Wm. First,

we consider C = A U B. The idea is to construct a new DTM M that
simulates both machines A& and Mm. The machine &! halts when one of the
machines Mn or Mm halts. An important point is that M needs to simulate
the machines Mn and Mm in parallel, because if we simulate one machine
first and if that machine does not halt then we will never be able to find out
whether the other machine halts or not.
To do so, we design a DTM M as the product DTM of Mn and Mm, like
the product automata introduced in Sections 2.2 and 3.5; that is, each state
of M encodes two states, one from Mn and the other from Mm. Furthermore,
M uses two separate tapes to simulate the tape configurations of the two
machines.
More precisely, assume that Mn has states Qn = {ql,... , qs} and Mm has
states Qm = {ql,..., qt}. Then, M has states Q = Qn x Qm plus some
auxiliary states, and it has two tapes. It first uses the auxiliary states to copy
the input from tape 1 to tape 2. Then, it uses the following instructions to
simulate Mn and Mm parallelly:

ifS,(qi,,al) = (qiz,a2,D1) and ~n(qj,~bl) = (qjsjh,-&), where b and h-n

are the transition functions of Mn and Mm, respectively.

Recall that, in the Turing machine system M, the highest-indexed state is

the halting state. So, M needs to halt when it reaches one of the following

states:

Since M should have a single halting state h, we add the following instructions

to M: