(Covered by Todor Tsankov)
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 .