Spring 2022 MATH 136 001 LEC

Incompleteness and Undecidability
Schedule: 
SectionDays/TimesLocationInstructorClass
001 LECTuTh 05:00PM - 06:29PMEvans 9Theodore Slaman28137
UnitsEnrollment StatusSession
4Open2022 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