Simple Sets and the Recursion Theorem

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 φef(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 Comments

Filed under Logic

2 responses to “Simple Sets and the Recursion Theorem

  1. ilias kastanas

    “Shiny little box”, used by Leo Harrington in a lecture at UCLA, late 70s or 80s.

    — Thx for your blog Michael, informative and entertaining!

Leave a Reply

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

WordPress.com Logo

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

Google photo

You are commenting using your Google 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.