Short Description

This unit will go back to the early days of computing, long before any physical machines existed which would be recognisable today as computers. Do computational problems exist which have no possible ‘method’ for solving? And when a ‘method’ exists, on which resources does it rely upon, and what is its cost? In this unit, students will learn that to answer these questions, they must investigate formally what a 'method' actually is, and appreciate its limits, as well as learn about some unsolvable problems. Students will learn some techniques that are used in many modern systems, including the core component of how compilers are able to process source code when programming. This unit also covers how formal computation models can be used to reason about the relative speed or complexity of various algorithms without needing to write any actual code. 

You’ll learn to:

• Demonstrate an understanding of the fundamental models of computation and the corresponding classes of formal languages, suitably expressed
• Design and apply algorithms for specific computational problems involving languages and computational models of appropriate types (e.g. automata)
• Prove formally that some computational problems are undecidable within a particular class of computational models
• Demonstrate an understanding of the role of grammars in the context of parsing algorithms, by applying the theoretical knowledge to concrete cases
• Give upper bounds on complexities of some decidable computational problems