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 (Sep to Jan) 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 website

Last updated: 12/04/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.BREP