# Models of Computation: 2012-2013

| |

| |

| Michaelmas Term 2012 (16 lectures) |

## Overview

This course introduces the classical mathematical models used to analyse computation, including finite state automata, grammars, and Turing Machines.A computer scientist should be able to distinguish between what can be computed and what cannot. This distinction can only be made with a good scientific model of computers and computation. This course introduces the powerful idea of using a mathematical model to analyse computation.

This course describes a number of different models of computation which were proposed and analysed over the past century. Many of these models were found to be equivalent, in the sense that they allow exactly the same computations to be carried out. Other models were shown to be less powerful, but simpler to implement, and so useful for some purposes.

## Synopsis

**Part 1: Finite-state machines and regular languages **

- General introduction. The FSM model. DFA's. Transition diagrams. Examples.
- NFA. The subset construction. Reduction of NFA to DFA.
- Regular Languages. Closure properties. Constructions on machines.
- Regular expressions. Some regular algebra. Algebraic laws.
- Compiling regular expressions into NFA's, and vice versa.
- Regular grammars. Equivalence to regular languages.
- Limits to FSM's. The Pumping Lemma.
- Context-free Languages and Pushdown Automata. The Chomsky hierarchy.

**Part 2: Turing machines and computability**

- Turing's Analysis of computation. The Turing machine model: FSM's plus memory (the "tape").
- The intuitive notion of computability. Decision problems. Encoding problems as sets of strings.
- Expressive power of Turing machines. Church's thesis.
- Undecidable problems. Diagonalization. The halting problem.
- Survey of decidable and undecidable problems. A glimpse beyond: complexity, P=NP?

## Syllabus

The finite-state machine. DFA and NFA and their equivalence. Regular languages and regular expressions. Regular grammars. The pumping lemma.The Turing machine. Church's Thesis. Decision problems and undecidability. The halting problem. Chomsky grammars.

## Reading list

**Primary Text**

- M Sipser, Introduction to the Theory of Computation, PWS Publishing Company, January 1997.

**Background Reading**

- J E Hopcroft, R Motwani and J D Ullman, Introduction to Automata Theory, Languages and Computation,Addison-Wesley, Second edition, 2001.
- G. Boolos and R. Jeffrey, Computability and Logic, Cambridge University Press, 3rd Edition, 1989.

## Taking our courses

**This form is not to be used by students studying for a degree in the
Department of Computer Science, or for Visiting Students who are registered for
Computer Science courses**

Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.