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

### Like this:

Like Loading...

*Related*

This entry was posted on January 4, 2007 at 10:45 am and is filed under 117b, Turing degrees. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply