2005/06 Undergraduate Module Catalogue

MATH3163 Computability and Unsolvability

15 creditsClass Size: 100

Taught: Semester 1 (Sep to Jan) View Timetable

Year running 2005/06

Pre-requisites

MATH 2040 or MATH 2210, or equivalent.

This module is approved as an Elective

Objectives

To introduce, via a standard machine-model, the broad concepts and more detailed notions of the pure mathematical theory of computable functions, decidable and undecidable mathematical theories. To develop the basic structural properties of the computable and non-computable universe. On completion of this module, students should be able to: prove basic theorems on computable functions and computably enumerable sets; construct recursive definitions and verify properties of them; recognise different types of recursively enumerable sets; carry out basic degree theoretic constructions.

Syllabus

Turing machines or register 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. Topics to be covered:Historical background; pure mathematical models of computation; Turing machines; register machines.Indexing the computable functions; the universal machine; Kleene's recursion Theorem.Recursive programs; recursive functions; equivalence of recursiveness and computability; Church's Thesis.Primitive recursion; Ackermann's function; computational complexity; the computable universe.Unsolvability of the Halting Problem; recursively enumerable sets; creative sets; simple sets; Gvdels Incompleteness Theorem.Relative recursiveness; degrees of unsolvability and the non-computable universe; the jump operator.Degrees below 0' and 1-generic degrees; recursively enumerable degrees; finite injury priority constructions and the Friedberg-Muchnik theorem; further applications of priority.

Teaching methods

Hours: Lectures: 26; Tutorials: 0; Practicals: 0; Other hours: 7 examples classes. Monitoring of progress: Regular example sheets.

Methods of assessment

85% 3 hour examination at end of semester; 15% coursework.

Reading list

The reading list is available from the Library website

Last updated: 23/03/2007

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