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:
  1. Chapter 1: Exercises 1.3, 1.4, 1.7, 1.15, 1.24
  2. Chapter 3: 3.1, 3.6, 3.7, 3.11, 3.15; Chapter 4: 4.6, 4.12
  3. Chapter 5: Problems at this link.
  4. 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.
  5. Chapter 7: 7.12, 7.17, 7.24, 7.45

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