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.
- 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
Department of Mathematics & Statistics
Faculty Hall 6C
Murray State University
Office: (270) 809-2503
Fax: (270) 809-2314
Home: (270) 761-3751
Wesley Calvert's Web Page