Computability Theory

86 Computability Theory

Proof. In one direction, assume that f is a partial function whose graph is the 6

1

relation

{hEx, yi | ∃z R(Ex, y, z)},

where R is a computable relation. Then given Ex, we need a “two-dimensional” search:

we want to locate both the answer y and the evidence z. The µ-operator does the

search; the dimensionality is easy to deal with:

f (Ex) = (µt R(Ex, (t)

0

, (t)

1

))

0

That is, we search for y and z, and then we ignore z and return y. This equation shows

that f is a computable partial function.

In the other direction, consider the computable partial function [[e]]

(n)

. We apply

the normal form theorem:

hEx, yi ∈ the graph of [[e]]

(n)