114C. Computability Theory (Formerly numbered 114A). Lecture, three hours; discussion, one hour. Requisite: course 110A or 131A or Philosophy 135. Effectively calculable, Turing computable, and recursive functions; Church/Turing thesis. Normal form theorem; universal functions; unsolvability and undecidability results. Recursive and recursively enumerable sets; relative recursiveness, polynomial-time computability. Arithmetical hierarchy. P/NP or letter grading.

If a function can be precisely defined, does that mean we can write a computer program for it? Math 114C looks at Turing machines and other models for making the concept of effective computability into genuine mathematics. The unsolvability of the halting problem demonstrates the existence of purely theoretical barriers to computability. There are decidable sets, effectively enumerable sets, and others.