There are several equivalent characterizations of the notion of being recursive in a function , namely:
- Belonging to the closure of under recursive functions and recursive operations.
- Being computable using a Turing machine with oracle .
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