Computing Theory

Catalog description

The goal of this course is to understand the fundamental limits on what can be efficiently computed in our universe and other possible universes. These limits reveal deep and mysterious properties about information, knowledge, and processing, as well as practical issues about what can and cannot be computed. The course introduces the foundations of automata theory, computability theory, and complexity theory. Shows relationship between automata and formal languages. Addresses the issue of which problems can be solved by computational means (decidability vs undecidability), and introduces concepts related to computational complexity of problems. Lecture, 3 hours.