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

Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: