## 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

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