# 2009/10 Undergraduate Module Catalogue

## MATH3163 Computability and Unsolvability

### 15 creditsClass Size: 50

**Module manager:** Professor S.B. Cooper**Email:** S.B.Cooper@leeds.ac.uk

**Taught:** Semester 1 View Timetable

**Year running** 2009/10

### Pre-requisite qualifications

MATH2040 or MATH2210 or equivalent### This module is mutually exclusive with

MATH5163M | Advanced Computability & Unsolvability |

**This module is approved as an Elective**

### Module summary

The abstract notion of Turing machine anticipated today's real-life computers, while the intrinsic limitations of computers were dramatically spotlighted by Gödel's theorem and the notion of a 'universal' Turing machine. This module gives an introduction to the novel concepts and powerful techniques of modern computability theory, and touches on some of the major research questions concerning the structure of the computable and non-computable universe, and the relevance of pure mathematics to computer science.### Objectives

On completion of this module, students should be able to:a) prove basic theorems on computable functions and computably enumerable sets;

b) construct recursive definitions and verify properties of them;

c) recognise different types of recursively enumerable sets;

d) carry out basic degree theoretic constructions.

### Syllabus

1. Historical background; Hilbert, algorithms and formalism; Gödel, Church, Turing and the formalisation of computability - and the discovery of incomputability; the consequences for Mathematics and the 'real world'. Indexing the computable functions; the universal machine; Kleene's recursion Theorem.

2. Primitive recursive functions; the -operator and (partial) recursive functions; Church's Thesis; (primitive) recursive relations and sets.

3. Turing machines, and Turing computable functions. The Church-Turing Thesis.

4. Gödel numbers for Turing machines the Turing machine, the Universal Turing Machine. The Fixed point Theorem.

5. Computably enumerable (c.e) and computable sets. sets and the Normal Form Theorem for c.e. sets; an incomputable c.e. set, and Turing machines with unsolvable halting problems; creative and simple sets.

6. Hilbert's Tenth Problem: Diophantine equations and sets; Davis' strategy and Matiasevich's theorem on the diophantine nature of Fibonacci sequences.

7. Models of computationally complex environments; many-one reducibility and equivalence; and the many-one degrees as the first attempt at a model.

8. Turing machines with oracles; basic properties of the Turing universe; the jump operator and the jump Theorem.

9. Degrees theoretic structure; forcing in the context of computability theory; 1-generic sets and applications; low degrees and sets which force their jumps.

10. The Friedberg-Muchnik theorem and finite injury priority arguments.

### Teaching methods

Delivery type | Number | Length hours | Student hours |

Example Class | 7 | 1.00 | 7.00 |

Lecture | 26 | 1.00 | 26.00 |

Private study hours | 117.00 | ||

Total Contact hours | 33.00 | ||

Total hours (100hr per 10 credits) | 150.00 |

### Methods of assessment

**Coursework**

Assessment type | Notes | % of formal assessment |

In-course Assessment | . | 15.00 |

Total percentage (Assessment Coursework) | 15.00 |

Normally resits will be assessed by the same methodology as the first attempt, unless otherwise stated

**Exams**

Exam type | Exam duration | % of formal assessment |

Standard exam (closed essays, MCQs etc) | 3 hr | 85.00 |

Total percentage (Assessment Exams) | 85.00 |

Normally resits will be assessed by the same methodology as the first attempt, unless otherwise stated

### Reading list

The reading list is available from the Library websiteLast updated: 12/04/2010

## Browse Other Catalogues

- Undergraduate module catalogue
- Taught Postgraduate module catalogue
- Undergraduate programme catalogue
- Taught Postgraduate programme catalogue

Errors, omissions, failed links etc should be notified to the Catalogue Team.PROD