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