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.