Automata, Languages and Computation

Module code: CO2011

In this module we will be primarily concerned with what computers can do. It turns out that there are problems that cannot be solved by computer or, at least, by machines corresponding to the mathematical models of computers we shall present. It is clearly sensible to investigate which problems cannot be solved; there is no point trying to program a computer to solve a problem that is unsolvable!

A problem may be unsolvable in the sense that no computer program exists that will solve it or in the sense that any program that would solve it would take longer than the lifetime of the universe to run. We will look at some precise mathematical models of the process of computation; within these models, we will see what sort of tasks can be performed.

At first sight, it may appear that these models are unduly simple and do not really capture all the subtleties of the process of computation. The advantages of using such models is two-fold. First, they are very simple to reason about, so that we can reach our conclusions much more simply than (for example) considering actual hardware and software components in fine detail. Second, they have proved to be very robust, in that successive generations of computers have all been shown to be no more powerful than the most general model we will present, and so the analysis based on these models has been useful throughout the history of Computer Science, whereas an analysis based on the specifics of various machines and programming languages quickly becomes obsolete.