We defined the analog of the halting problem for any oracle and showed that any set r.e. in is many-to-one reducible to (in particular, it is recursive in ). Hence, is a complete set and no such set is recursive in .
We proved the -- (or index function) theorem and Kleene’s recursion (or fixed point) theorem. Finally, we introduced the notion of an index set and proved Rice’s theorem that the only recursive index sets are and .
This entry was posted on March 4, 2008 at 9:48 am and is filed under 116b. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.
