116b- Lecture 16 | Computability Theory

116b- Lecture 16

(Covered by Todor Tsankov)

We defined the analog $K_X$ of the halting problem for any oracle $X$ and showed that any set r.e. in $X$ is many-to-one reducible to $K_X$ (in particular, it is recursive in $K_X$ ). Hence, $K_X$ is a complete $\Sigma_1(X)$ set and no such set is recursive in $X$ .

We proved the $S$ – $m$ – $n$ (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 ${\mathbb N}$ and $\emptyset$ .

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.

Leave a comment Cancel reply