# Section 1.7: Problem 9 Solution

Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.

James R. Munkres

The concepts of decidability and effective enumerability can be applied not only to sets of expressions but also to sets of integers or to sets of pairs of expressions or integers. Show that a set
of expressions is effectively enumerable iff there is a decidable set
of pairs
(consisting of an expression
and an integer
) such that
.

The idea here, I think, is that
is such that (*)
iff
contains
for some
. By the way, (*) holds iff
.

Now, if such decidable set
exists (such that
, or, equivalently, (*) holds), then
is effectively enumerable. In fact, we don’t even need
to be decidable. Suppose that
is effectively enumerable. Then, to test whether
(one way), we can test whether
for 1 minute, then test whether
or
is in
for 2 minutes each, etc. We know that
iff
for some
iff given input
our procedure will return “yes” in some finite time
. Of course, if
is also decidable, then we can just, first, test whether
until it produces “yes” or “no”, then
etc. One thing to note is that neither of the two procedures specified here will ever end if
.

Now, suppose that
is effectively enumerable. We need to construct
such that (*) holds. Suppose that a procedure
will return “yes” for any input
in a finite amount of time, while it will never return “yes” and even may run forever for any input
. Let us construct a decidable set
that can be tested (both ways) using
. For this we need to restrict somehow the amount of time that
can run. So, let us restrict it by
. Namely, we let
be the set of pairs
such that given input
,
will produce "yes" in
units of time. Here by “units of time” we may mean anything measurable such that given any input
, it will take a fixed amount of the units of time for
to produce “yes”, which does not depend on any external factors. For example, we may count the number of steps (operations or commands) it takes to produce “yes”. Considering the real time before “yes” appears might be a bad idea, as it often depends on external factors. However, since one of our assumptions is that the procedure is deterministic, in particular, the procedure does not use any randomization devices, the number of steps should be fixed for any input. Now, such
satisfies (*), as if
, then
will produce “yes” after a fixed number of steps, and for any
that is at least as large as the number of steps it takes to produce “yes” for
,
. However, if
, then
will never produce “yes”, and so there is no
such that
. Moreover,
is decidable. Indeed, to test whether
, all we need is to run
with input
for
units of time (steps of the algorithm). If it produces “yes”, then
and we return “yes”, otherwise we return “no” (this case corresponds to both when
and when
but it takes longer than
units of time for
to produce “yes”).

It is interesting to note, that if we take the set
and procedure we constructed in the second part, and apply the algorithm from the first part back on
to test whether
, we will end up with a quite inefficient version of
, where we first test
with input
for 1 minute, then we test it (from scratch) for 2 minutes etc.