# Math 691-01: Computability Theory

### Be alert for other information posted here in the future.

- The following titles are on reserve for this class in the library, and may be helpful to you:
- B. Cooper, "Computability Theory." The most up-to-date, comprehensive technical treatment I know from a mathematical perspective.
- N. Cutland, "Computability." An older book, very basic and rather narrow, but recommended under the table by many graduate students to one another as the right place to get intuition.
- M. Sipser, "Introduction to the Theory of Computation." Our text for the course, and favored by many computer scientists for its deeper discussion of automata and complexity.

- Syllabus
- Problems:
- Chapter 1: Exercises 1.3, 1.4, 1.7, 1.15, 1.24
- Chapter 3: 3.1, 3.6, 3.7, 3.11, 3.15; Chapter 4: 4.6, 4.12
- Chapter 5: Problems at this link.
- Chapter 6 :6.7, 6.8, 6.23; Show that there are Turing-incomparable sets. Also, show that there are recursively enumerable sets S_0 and S_1 such that no computable set includes all of S_0 and none of S_1.
- Chapter 7: 7.12, 7.17, 7.24, 7.45

Send correspondence to

Wesley Calvert
Department of Mathematics & Statistics
Faculty Hall 6C
Murray State University
Murray, Kentucky
Office: (270) 809-2503
Fax: (270) 809-2314
Home: (270) 761-3751

Wesley Calvert's Web Page

*wesley.calvert@murraystate.edu*