Friedberg’s Enumeration without Duplication

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:

(\exists t) the computation halts by time t

while “It’s total” looks like this:

(\forall n)(\exists t) the computation with input n halts by time t

So, an \exists prefix vs. \forall\exists. 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 Π2Wi=Wj if and only if

(\forall n)\big[\exists t (the computation for “n\in W_i” halts by time t) ↔

\exists t (the computation for “n\in W_j” halts by time t) \big]

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 W1, W2, …, 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 Sn 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 Sn‘s, and (b) no two of the Sn‘s are the same. I wrote up my own version of his proof, to understand it better.

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.

Leave a comment

Filed under Logic

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.