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$.