Computability Theory

Recursive Enumerability 91

Note that (g  Q)(Ex) is undefined unless both Ex ∈ Q and g(Ex) ↓. Informally, the

procedure for computing (g  Q)(Ex) involves first trying to verify that Ex ∈ Q, and then

computing g(Ex).

Proof 1. (g  Q)(Ex) = g(Ex) + 0 · c

Q

(Ex). a

Proof 2. (g  Q)(Ex) = y ⇔ Ex ∈ Q and g(Ex) = y, so the graph of g  Q is the inter-

section of two (n + 1)-ary r.e. relations. a

All of the noncomputable sets are noncomputable, but some are more noncom-

putable than others. One way to make sense out of that statement is to look at ways in

which membership questions about one set might be “reduced” to membership ques-

tions about another.

More