2025 Fall
MATH 136 001 - LEC 001
Incompleteness and Undecidability
Andrew Marks
Class #:26091
Units: 4
Instruction Mode:
In-Person Instruction
Offered through
Mathematics
Current Enrollment
Total Open Seats:
45
Enrolled: 0
Waitlisted: 0
Capacity: 45
Waitlist Max: 5
Open Reserved Seats:
45 reserved for Mathematics and Applied Mathematics Majors, and Undeclared Students in the College of Letters & Science
Hours & Workload
3 hours of instructor presentation of course materials per week, and 9 hours of outside work hours per week.
Other classes by Andrew Marks
Course Catalog 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.
Rules & Requirements
Repeat Rules
Course is not repeatable for credit.
Reserved Seats
Reserved Seating For This Term
Current Enrollment
Open Reserved Seats:
45 reserved for Mathematics and Applied Mathematics Majors, and Undeclared Students in the College of Letters & Science
Textbooks & Materials
See class syllabus or https://calstudentstore.berkeley.edu/textbooks for the most current information.
Guide to Open, Free, & Affordable Course Materials
Associated Sections
None