Module 06-05934 (2011)

• introduce a variety of formal models of computation
• explain the significance of formal models from a practical and a foundational point of view
• make familiar with the fundamental results in the theory of computation
• explain the way in which formalisations are used to address real-life computational problems

• explain the basics of automata theory, formal language theory, computability theory, complexity theory and lambda calculus
• explain non-computability and non-decidability issues
• describe and use the connection between automata and languages
• explain and use lambda calculus as a theory of functional programming
• explain the connection between theory and applications

11 two-hour lectures, 11 one-hour exercise sessions, 2 one-hour review lectures

• Sessional: 1.5 hr examination (80%), continuous assessment (20%).
• Supplementary: 1.5 hr examination (100%).

1. Finite automata (4 hrs)
   • Finite automata and regular languages
   • Nondeterminism
   • Limitations of finite automata
2. Formal languages (2 hrs)
   • Grammars
   • Pushdown automata
3. Limits of computation (4 hrs)
   • The Halting Problem
   • Reducibility
4. Turing machines (4 hrs)
   • The basic model
   • Extensions and their equivalence with the basic model
   • Church's Thesis
5. Complexity Theory (4 hrs)
   • Complexity of Turing machine programs
   • The class P
   • The class NP
   • NP-complete problems
6. Formalising functional programming (4 hrs)
   • Rewriting as a computational paradigm
   • Lambda calculus
   • Typed lambda calculi