The first section of the course asks the question, what does it mean to compute? We start with the finite automata introduced in earlier years, and then generalise to pushdown automata, and show that they have more power. Next we generalize further to very simple abstract general computers, and argue they can do everything real computers can do. We then ask, can we solve every computational question? The answer, with which Turing shocked the mathematicians of the 1930s, is "no", with a remarkably easy but beautiful argument (introduced at the end of Inf2-IADS). We then explore some different, but always equivalent, ways of defining "a computer". We finish the section by asking how we can compare the difficulty of different problems, and introduce the idea of "reduction" as a way of compiling one problem into another. Technically, this covers register machines, undecidability, Turing machines, and reductions.
The second section thinks about how hard it is to solve solvable problems, leading to one of the most important problems in all mathematics, and the foundation of internet security. We start by reprising Inf2-IADS analysis of algorithms, and then discuss the idea of classifying problems as `tractable' (easy) or `intractable' (hard). We find that the idea of algorithms whose running time grows polynomially in the problem size is a good mathematical definition of `tractable', though not always a practical one. After making this more precise, we ask what happens if we're allowed to just check all the possible answers in parallel - does this give us more problem-solving power? The question is made precise by the concept of NP, and we show that there are "hardest" such problems, such as the famous Travelling Salesman. Although the question is easy to ask, nobody knows how to answer it. This is P = NP - if you can solve it, you win a million dollars, and fame for as long as civilization lasts. So far, NP problems are very hard to solve in practice, so we discuss how to deal with them. We finish the section by talking about much harder problems still. Technically, this section covers P, NP, hardness and completeness, Cook's Theorem, P = NP, and the complexity hierarchy above NP.
The third section takes brief look at a different way of seeing computation. Haskell needn't be seen as a programming language, it can be the computer itself. We'll show how the lambda-calculus (on which Haskell is based) can do all the computing our other models could, and how the halting problem was actually first solved (or rather unsolved) within lambda-calculus.
