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

Advertisements

## Leave a Reply