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 $A$ is decidable, then there is a procedure $P$ such that it can decide whether any expression $\alpha\in A$ . Then, to test whether $\alpha\in A$ we can run $P$ and return “yes” iff it returns “yes” (and do whatever we want in the other case), and to test whether $\alpha\in\overline{A}$ we can run $P$ and return “yes” iff it returns “no” (and do whatever we want in the other case). Hence, both $A$ and $\overline{A}$ are effectively enumerable (we use the definition given in Theorem 17E).

Conversely, if a set of expressions $A$ is such that both set $A$ and its complement $\overline{A}$ are effectively enumerable, then there is a procedure $P$ effectively listing members of $A$ , and there is a procedure $\overline{P}$ effectively listing members of $\overline{A}$ (we use the initial definition given in the text). Now, given any expression $\alpha$ , we run both procedures “simultaneously”$^{*}$ until the expression $\alpha$ appears in one of the lists. Once one procedure produces $\alpha$ (and we know that, since either $\alpha\in A$ or $\alpha\in\overline{A}$ , this should happen after a finite number of steps), two things happen, first, we know whether $\alpha$ is in $A$ or in $\overline{A}$ , and, second, we know that the other procedure will never produce $\alpha$ . Hence, depending on which procedure, $P$ or $\overline{P}$ , produced $\alpha$ , we can decide that $\alpha\in A$ or $\alpha\notin A$ , 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 $A$ or $\overline{A}$ 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.