Theory of Computation: Lecture 45. The main topics covered in this lesson include: space complexity; computability; non-trivial semantic properties; post correspondence problem; Presburger arithmetic; the Gödel’s theorem; the Clay mathematical society; . |