(Taken from the UC Berkeley Course Guide)
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.
a href="math53.html">MATH 53 MATH 54 and MATH 55
3 hours of lecture per week