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.

Review Summary

Clarity
N/A
Organization
N/A
Time
N/A
Overall
N/A

Course

Instructor
Tyler Arant
Previously taught
23W 21W

Previous Grades

Grade distributions not available.