Spring 2021 MATH 136 001 LEC

Incompleteness and Undecidability
Schedule: 
SectionDays/TimesLocationInstructorClass
001 LECMoWeFr 01:00PM - 01:59PMInternet/OnlinePierre A Simon26682
UnitsEnrollment StatusSession
4Open2021 Spring, January 19 - May 07
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