Spring 2020 MATH 136 001 LEC
Incompleteness and Undecidability
Schedule:
Section | Days/Times | Location | Instructor | Class |
---|---|---|---|---|
001 LEC | TuTh 12:30PM - 01:59PM | Hearst Mining 310 | John Steel | 31363 |
Units | Enrollment Status | Session |
---|---|---|
4 | Open | 2020 Spring, January 21 - May 08 |
Additional Information:
Prerequisites 53, 54, and 55
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