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 $A$ of expressions is effectively enumerable iff there is a decidable set $B$ of pairs $<\alpha,n>$ (consisting of an expression $\alpha$ and an integer $n$ ) such that $A=\mbox{dom}B$ .
The idea here, I think, is that $B$ is such that (*) $\alpha\in A$ iff $B$ contains $<\alpha,n>$ for some $n\in\mathbb{N}$ . By the way, (*) holds iff $\mbox{dom}B=A$ .
Now, if such decidable set $B$ exists (such that $\mbox{dom}B=A$ , or, equivalently, (*) holds), then $A$ is effectively enumerable. In fact, we don’t even need $B$ to be decidable. Suppose that $B$ is effectively enumerable. Then, to test whether $\alpha\in A$ (one way), we can test whether $<\alpha,1>\in B$ for 1 minute, then test whether $<\alpha,1>$ or $<\alpha,2>$ is in $B$ for 2 minutes each, etc. We know that $\alpha\in A$ iff $<\alpha,n>\in B$ for some $n\in\mathbb{N}$ iff given input $<\alpha,n>$ our procedure will return “yes” in some finite time $m$ . Of course, if $B$ is also decidable, then we can just, first, test whether $<\alpha,1>\in B$ until it produces “yes” or “no”, then $<\alpha,2>$ etc. One thing to note is that neither of the two procedures specified here will ever end if $\alpha\notin A$ .
Now, suppose that $A$ is effectively enumerable. We need to construct $B$ such that (*) holds. Suppose that a procedure $P$ will return “yes” for any input $\alpha\in A$ in a finite amount of time, while it will never return “yes” and even may run forever for any input $\alpha\notin A$ . Let us construct a decidable set $B$ that can be tested (both ways) using $P$ . For this we need to restrict somehow the amount of time that $P$ can run. So, let us restrict it by $n$ . Namely, we let $B$ be the set of pairs $<\alpha,n>$ 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 $P$ 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 $B$ satisfies (*), as if $\alpha\in A$ , then $P$ will produce “yes” after a fixed number of steps, and for any $n$ that is at least as large as the number of steps it takes to produce “yes” for $\alpha$ , $<\alpha,n>\in B$ . However, if $\alpha\notin A$ , then $P$ will never produce “yes”, and so there is no $n$ such that $<\alpha,n>\in B$ . Moreover, $B$ is decidable. Indeed, to test whether $<\alpha,n>\in B$ , all we need is to run $P$ with input $\alpha$ for $n$ units of time (steps of the algorithm). If it produces “yes”, then $<\alpha,n>\in B$ and we return “yes”, otherwise we return “no” (this case corresponds to both when $\alpha\notin A$ and when $\alpha\in A$ but it takes longer than $n$ units of time for $P$ to produce “yes”).
It is interesting to note, that if we take the set $B$ and procedure we constructed in the second part, and apply the algorithm from the first part back on $A$ to test whether $\alpha\in A$ , we will end up with a quite inefficient version of $P$ , where we first test $P$ with input $\alpha$ for 1 minute, then we test it (from scratch) for 2 minutes etc.