Section 1.7: Problem 8 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
Prove Theorem 17F. Remark: Two semidecision procedures make a whole.
Theorem 17F. A set of expressions is decidable iff both it and its complement (relative to the set of all expressions) are effectively enumerable.
If a set of expressions is decidable, then there is a procedure such that it can decide whether any expression . Then, to test whether we can run and return “yes” iff it returns “yes” (and do whatever we want in the other case), and to test whether we can run and return “yes” iff it returns “no” (and do whatever we want in the other case). Hence, both and are effectively enumerable (we use the definition given in Theorem 17E).
Conversely, if a set of expressions is such that both set and its complement are effectively enumerable, then there is a procedure effectively listing members of , and there is a procedure effectively listing members of (we use the initial definition given in the text). Now, given any expression , we run both procedures “simultaneously” until the expression appears in one of the lists. Once one procedure produces (and we know that, since either or , this should happen after a finite number of steps), two things happen, first, we know whether is in or in , and, second, we know that the other procedure will never produce . Hence, depending on which procedure, or , produced , we can decide that or , respectively.
Regarding “simultaneously”. We can either run two procedures simultaneously, using, for example, two computers, or just limit each one in time running and then switch to the other one (assuming we can continue from where we ended before), or use the trick from the text, i.e. run each one for 1 minute, then each one from scratch for 2 minutes etc. (without the assumption that we can continue from where we ended). The difference here compared to the proof of Theorem 17E, is that we have only two, and, hence, fixed and finite number of procedures to run, and one input only. When we have infinite number of procedures to run or infinitely many inputs to test (as in the proof of Theorem 17E), we cannot run them “simultaneously” directly (we would need infinite number of hardware units). Moreover, the assumption that we can continue from where we started also seems unreasonable in this case, because in any practical situation using any hardware to test, we may need too much memory to save all the states for each input still being tested. Yes, we stated that this is not something we bother with, but still, if there is a way to avoid unnecessary use of unrealistic amount of memory, we may want to provide an algorithm that does not use it, as is done in the proof of Theorem 17E (of course, at the expense of the time that is needed for the algorithm to find the answer, but without the assumption that we can continue from where we ended). Another thing to mention is that we cannot run the two procedures “simultaneously” by running each one until it produces one member and then switching to the other one, as we do not know beforehand whether or is infinite. For example, either set could be empty, and our algorithm in this case will stuck waiting for the corresponding procedure to ever produce at least one element.