Problem Solving in Automata, Languages, and Complexity

238 COMPUTABILITY THEORY

each x = (~,t’), with t’ > t. Thus, M prints an infinite sequence of strings in
A. This means that M enumerates set A.

(e) + (b): Assume that A = Wy. Let x0 be the least string in A. Then,

define

l(x)

f(z) = { xo

if hWW, Y:, r(x)>,

otherwise.

It is clear that the range of f is set A. Furthermore, since halt is a primitive
recursive function, f is primitive recursive. 0

Theorem 5.14 Assume that A is an infinite set. Then, A is r.e. if and only

(f) A is the range of a one-to-one, recursive function.

Proof. In the last theorem, we showed that the condition (e) of A being

r.e. is equivalent to each of the conditions (a)-(d). It is clear that (f) 3 (c).

Therefore, we need only to prove that, for an infinite set A, (a) =+ (f):

Assume that machine M enumerates A. Then, we can design a new four-

tape DTM A&’ that works on input n as follows:

(1) &P uses tape 1 as the input tape, tape 4 as the output tape.

(2) AP uses tapes 2 and 3 to simulate &K When &! prints a string followed

by a blank on tape 3, AP checks whether the string has been printed

before. If yes, A&’ erases it.

(3) If the string just printed is new, then M’ checks whether this is the nth

string remained on tape 3. If so, it copies this string to tape 4 and halts.

Otherwise, it goes back to step (2). 0

Next we consider recursive sets. The following characterization of recursive
sets is very useful. For every set A C - (0, l}‘, we write A to denote the set
(0, l}* - A.

Theorem 5.15 A set A is recursive if and only if both A and A are r.e.

Proof. If A is recursive, then its characteristic function XA is recursive. That
is, XA = & for some n - > 0. so, we have

x E A e (3) print(x, 1, n, t),

x E A ( (3) print(x, 0, n, t).

By the projection theorem, both A and A are r.e.
Conversely, assume that A = VVn and A = W,. Then, define

time(x) = (mint)[halt(x, n, t) or h&(x, m, t)].

Since x is either in W, or in VVm, the function time is a recursive function.

Now, we see that XA(x) = haZt(x, n, time(x)) and it follows that A is recursive.

0