Why the time increment in testing membership for a set? (Enderton's Logic, Th 17E) In Enderton's Logic, Theorem 17E says:
"A set $A$ of expression is effectively enumerable iff there exists an effective procedure that, given any expression $\epsilon$, produces the answer "yes" iff $\epsilon \in A$."
The converse of the proof says:
"Conversely, suppose that we have the procedure described in the theorem. We want to create a listing of $A$. The idea is to enumerate all expresssions, and to apply our given procedure to each. But we must budget our time sensibly. It is easy enough to enumerate effectively all expression:
$\epsilon_1, \epsilon_2, \epsilon_3,...$
Then proceed according to the following scheme:

*

*Spend one minute testing $\epsilon_1$, for membership in $A$ (using the given procedure).

*Spend two minutes testing $\epsilon_1$, then two minutes testing $\epsilon_2$.

*Spend three minutes testing $\epsilon_1$, three minutes testing $\epsilon_2$, and three minutes testing $\epsilon_3$.

And so forth. Of course whenever our procedure produces a "yes" answer, we put the accepted expression on the output list. Thus any member of $A$ will eventually appear on the list. (It will appear infinitely many times, unless we modify the above instructions to check for duplication."
My question is why does Enderton specify an increasing amount of time (e.g. 1 minute, 2 minutes, 3 minutes, etc) on each step? Enderton is a very careful writer, so it seems likely that there is a reason behind his choice.
 A: I presume the algorithm in question does not have a memory. That is, if you checked $\epsilon_1$ for membership for a minute, and after a minute the procedure has not terminated, you move on to $\epsilon_2$ and forget about $\epsilon_1$ (and all the work done on $\epsilon_1$ so far) . By repeatedly increasing the amount of time you check each $\epsilon_n$ in each round, you know that eventually you spend enough time to crack it (provided the answer is "yes").
A: The converse of your proof is to prove if a set is semidecidable then it's effectively enumerable. Per Enderton, semidecidability is defined as below:

A set A of expressions is semidecidable iff there exists
an effective procedure that, given any expression ε, produces the
answer “yes” iff ε ∈ A

And effective enumerablity is usually defined as:

A set is effectively enumerable if, and only if, it is the range of a total or partial
effectively computable function on the natural numbers

With this in mind, here the author just algorithmically formulated a total effectively computable function on the natural numbers to effectively list out all expressions which belong to the set A. It may not be the unique way, you can certainly devise some other deterministic algos to achieve same, but the approach provided here seems straightforward.
