Week 11
Topics covered in class
- Relative computability
- Turing reducibility
- Sets r.e. relative to a given set
- Jumps, Jump-theorem
- Connections between Turing reducibility, m-reducibility, Jumps
and relative recursive enumerability
Relevant sections in the textbook
Chapter 8: sections 1-4.
Recommended exercises from the book
Ch. 8.1: exercise 2. Ch 8.3 Ex. 2,3,5.