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

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 )

Google photo

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

Twitter picture

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

Facebook photo

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

Connecting to %s

%d bloggers like this: