## 117b – Turing degrees – Lecture 1

There are several equivalent characterizations of the notion of being recursive in a function $f$, namely:

•  Belonging to the closure of ${f}$ under recursive functions and recursive operations.
•  Being computable using a Turing machine with oracle $f$.

The key tool to use this notion is the enumeration theorem.

This material should just be a generalization of notions and results studied in 117a. The following references may be useful for this part of the course:

• Mathematical Logic,  part II, by R. Cori and D. Lascar. OUP (2001), 0 -19-850050-5
• Computability: An introduction to recursive function theory, by N. Cutland. Cambridge Univerity Press (1980), 0-521-294657
• Theory of recursive functions and effective computability, by H. Rogers. MIT press (1987), 0-262-68052-1
• Computability theory, by B. Cooper. CRC Press (2003), 1-58488-237-9
• Degrees of unsolvability: Local and global theory, by M. Lerman. Springer (1983), 0-387-12155-2