116b- Lecture 17

March 4, 2008

We proved the Rice, Shapiro, McNaughton theorem characterizing \Sigma_1 index sets.

We also showed that there incomparable Turing degrees below {\bf 0}'.


116b- Lecture 16

March 4, 2008

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

116b- Lecture 15

March 4, 2008

We proved that the class of functions computable by means of Turing machines coincides with the class of recursive functions. Together with the characterization of the recursive functions as those admitting \Sigma_1 graphs, one can see this result as empirical evidence for Church’s thesis, the claim that the intuitive notion of “algorithmically computable” is correctly formalized in the notion of recursive. An immediate consequence of this result is the existence of universal Turing machines.

We defined machines with oracles and stated the corresponding result: Given an oracle X\subseteq\mathbb{N}, a function f: \mathrm{dom}(f) \subseteq \mathbb{N}^k\to\mathbb{N} is computable by a Turing machine with oracle X iff f is recursive in X (meaning that it is built up from \chi_X and the basic functions by composition, recursion and minimalization) iff f has a graph \Sigma_1 definable in the structure (\mathbb{N},+,\times,0,1,<,X). We then defined the partial order A\le_T B among subsets of \mathbb{N} which holds iff \chi_A is recursive in B.