Spring 2015 MATH 136 001 LEC

Incompleteness and Undecidability
Schedule: 
SectionDays/TimeLocationInstructorCCN
001 LECMWF 9-10A 3 EVANSFREITAG, J54212
Units/CreditFinal Exam GroupEnrollment
44: MONDAY, MAY 11, 2015 7-10PLimit:36 Enrolled:20 Waitlist:0 Avail Seats:16 [on 03/22/15]
Additional Information: 

Prerequisites: 53, 54, and 55.

Syllabus: 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: