Spring 2020 MATH 136 001 LEC

Incompleteness and Undecidability
Schedule: 
SectionDays/TimesLocationInstructorClass
001 LECTuTh 12:30PM - 01:59PMHearst Mining 310John Steel31363
UnitsEnrollment StatusSession
4Open2020 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