These notes on Simple Sets are a grabbag about the simple sets of recursion theory. If you don’t know what those are, you probably are not interested, but the Wikipedia article is nice and short and gives the basics.
The last result uses the “shiny black box” (see below), which seems like cheating, but isn’t!
I wrote up the notes sometime in the 1980s based on two papers, and on a lecture by Michael Stob at MIT (reporting on joint work with Maas and Shore). They discuss effectively simple sets and promptly simple sets.
The topics are unified by a common technique: Kleene’s recursion theorem. This says that if φe is a (computable) enumeration of the partial recursive functions, and if f is a (total) recursive function, then φe=φf(e) for some index e. (The theorem has the usual complement of variations, e.g., We=Wf(e) if We is an enumeration of the r.e. sets.) Kleene’s recursion theorem traces its ancestry back to Cantor’s diagonal argument, by way of Gödel’s incompleteness theorem and Turing’s Halting problem, so it very much belongs on this blog!
I always had a special affinity for uses of the theorem. The lecture by Stob gave a magical application, which Stob called the “shiny black box” method. (He attributed the term to someone else, I forget who. Maybe Harvey Friedman?) It combined the recursion theorem with Friedberg’s priority method. Truthfully, I found the method more interesting than the result. But maybe that’s just me.
As Stob put it, you give a construction to generate a series of r.e. sets, say Ve. While doing the construction, you assume you have a recursive function g giving you the indices of the sets: Ve=Wg(e). As I said, it seems like cheating, but it isn’t!
2 responses to “Simple Sets and the Recursion Theorem”
“Shiny little box”, used by Leo Harrington in a lecture at UCLA, late 70s or 80s.
— Thx for your blog Michael, informative and entertaining!
Thanks for the info!