Spring 2013 MATH 136 001 LEC

Incompleteness and Undecidability
Schedule: 
SectionDays/TimeLocationInstructorCCN
001 LECMWF 3-4P 71 EVANSFREITAG, J54244
Units/CreditFinal Exam GroupEnrollment
412Limit:40 Enrolled:31 Waitlist:0 Avail Seats:9 [on 06/26/13]
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: