Spring 2022 MATH 136 001 LEC
Incompleteness and Undecidability
Schedule:
Section | Days/Times | Location | Instructor | Class |
---|---|---|---|---|
001 LEC | TuTh 05:00PM - 06:29PM | Evans 9 | Theodore Slaman | 28137 |
Units | Enrollment Status | Session |
---|---|---|
4 | Open | 2022 Spring, January 18 - May 06 |
Additional Information:
Prerequisites Math 104 and 113 or consent of instructor
Description Functions computable by algorithm, Turing machines, Church's thesis. Unsolvability of the halting problem, Rice's theorem. Recursively enumerable sets, creative sets, many-one reductions. Self-referential programs. Godel's incompleteness theorems, undecidability of validity, decidable and undecidable theories.
Office
Office Hours
Required Text
Recommended Reading
Grading
Homework
Course Webpage