Recursively enumerable (r.e.) sets are “semi-decidable”: if *x* belongs to an r.e. set *W*, then there’s a terminating computation proving that fact. But there may not be any way to verify that *x* does *not* belong to *W*. The founding theorem of recursion theory—the unsolvability of the Halting Problem—furnishes an r.e., non-recursive set. For this set, we have a program listing what’s *in W*, but no program listing what’s *out*.

“Does this program halt on this input?” is the easiest non-recursive question you can ask; that’s the moral of Kleene’s Arithmetical Hierarchy. Asking whether a partial recursive function is total is an *essentially harder question*. “It halts” looks like this:

the computation halts by time *t*

while “It’s total” looks like this:

the computation with input *n* halts by time *t*

So, an prefix vs. . With a standard notation, “It halts” is Σ_{1}, while “It’s total” is Π_{2}.

The question, “Are these two r.e. sets the same?” is also Π_{2}. *W _{i}*=

*W*if and only if

_{j} (the computation for “” halts by time *t*) ↔

(the computation for “” halts by time *t*)* *

You would think that *listing the r.e. sets without duplication* shared at least the same degree of difficulty. After all, the obvious procedure is to go through the list *W*_{1}, *W*_{2}, …, crossing out duplicates.

Remarkably, Richard Friedberg found a way to list the r.e. sets without duplication, using a partial recursive function! To be precise, he described a partial recursive function ψ(*x*,*n*) with these two properties: if we let *S _{n}* be the set of

*x*‘s for which the computation of ψ(

*x*,

*n*) halts, then (a) every r.e. set appears in the list of all the

*S*‘s, and (b) no two of the

_{n}*S*‘s are the same. I wrote up my own version of his proof, to understand it better.

_{n}Friedberg did this with the *priority method*, which he discovered as an undergrad; he used it to solve a celebrated open question (Post’s problem).

On a personal note, Friedberg was my freshman college physics professor. I only found out about his work in recursion theory years later. One of the best and nicest professors I’ve had.