2009/10 Taught Postgraduate Module Catalogue

MATH5163M Advanced Computability & Unsolvability

15 creditsClass Size: 30

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

Taught: Semester 1 (Sep to Jan) View Timetable

Year running 2009/10

Pre-requisite qualifications

MATH2040 or MATH2210, or equivalent.

This module is mutually exclusive with

MATH3163

Computability and Unsolvability

This module is not 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. This is a challenging course and should only be attempted by students with a strong background in Pure Mathematics.

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.
e) appreciate the significance of Post's Theorem about the arithmetical hierarchy.

Syllabus

Turing machines, computable functions and their indexing, recursive programs and recursive functions, equivalence of computability with recursiveness, computably enumerable sets and undecidable problems, creative sets and simple sets, relationships with logic and complexity theory, oracle computations and relative computability, the degrees of unsolvability, the jump operator, 1-generic sets and applications, finite injury priority methods and the Friedberg-Muchnik theorem. Computing with oracles. The arithmetical hierarchy. Post's Theorem. Forcing and category.

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

Opportunities for Formative Feedback

Regular example sheets

Methods of assessment

Exams

Exam type	Exam duration	% of formal assessment
Standard exam (closed essays, MCQs etc)	3 hr	100.00
Total percentage (Assessment Exams)		100.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 website

Last updated: 22/03/2010

Disclaimer

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