Problem Solving in Automata, Languages, and Complexity

5.2 R.E. Sets and Recursive Sets 237

one-way write-only tape, such that when it is given the empty string E as the

input, M-prints an infinite sequence of strings ~1, ~2,... on the second tape,

with every two strings separated by a blank, such that A = (~1, ~2,... }.

Note that the strings printed by iV does not have to follow any specific order,

and they do not have to be distinct from each other. As long as M prints

only strings in A and every string in A is eventually printed, then A is said

to be enumerated by M.

Theorem 5.13 Assume that A is an nonempty set. Then, the following are

equivalent:

(a) A is Turing-enumerable.

(b) A is the range of a primitive recursive function.

(c) A is the range of a recursive function.

(d) A is the range of a partial recursive function.

(e) A is r.e.

Proof. The directions (b) 3 (c) and (c) 3 (d) are trivial. The direction (d)

+ (e) is just Example 5.12. We need to prove (a) * (c), (e) a (a) and (e)

* Cb)*

(a) a (c): Assume that machine M enumerates A. Then, we can design

a new four-tape DTM JP that prints, on input n, the nth string enumerated

by M:

M’ uses tape 1 as the input tape, treating the input n as a counter.

It uses tape 4 as the output tape, and uses tapes 2 and 3 to simulate

M. In the simulation, whenever M prints a string x followed by

a blank on tape 2, M’ examines tape 1. If the counter of tape 1

is 0, then M’ copies the string 2 to tape 4 and halts; otherwise, it

decreases the counter by 1, and continues the simulation of M.

We note that iV enumerates an infinite number of strings, and so M’
halts on every input n. Thus, the function computed by M’ is recursive. In
addition, its range is exactly the set A.
(e) 3 (a): Assume that A = IV& Then, we can design a DTM M that
enumerates A as follows:
(1) Set x := 0.
(2) Simulate MY on input Z(x) f or Y(X) moves (on tape 1). If it halts, then
print Z(x) on tape 2 and then print a blank B.
(3) Set x := x + 1 and go back to step (2).
(More precisely, we need to split tape 1 of M into two tracks, using one track
to store the values of x, Z(x) and T(X), and using the other to simulate MY.)
It is clear that M prints only strings in A. In addition, if a string x is in A,
then there exists an integer t such that halt@, y, t). It follows that z will be
printed by AL Finally, we observe that if haZt(r, y, t), then M will print x for