MAC 2055 THEORY OF COMPUTATION

This course provides an introduction to the theory of computation, which essentially deals with the question: What are the fundamental capabilities and limitations of computers? Topics include: regular languages, context-free languages, the Church-Turing thesis, decidability, reducibility, time complexity, space complexity, intractability.