Course details
Semester
 Spring 2022
 Monday, January 31st to Friday, March 25th; Monday, April 25th to Friday, May 6th
Hours
 Live lecture hours
 10
 Recorded lecture hours
 0
 Total advised study hours
 40
Timetable
 Fridays
 12:05  12:55 (UK)
Description
The computational strength of a set is measured by its Turing degree. The collection of all Turing degrees has a rich structure and is the central object of study in computability theory. This course introduces the basic theory of the Turing degrees. Time permitting, the course also surveys contemporary research directions that connect to other areas of mathematics, such as reverse mathematics and algorithmic randomness.
Prerequisites
 A basic knowledge of firstorder logic.
 Familiarity with a formal model of computation, such as Turing machines, register machines, while programs, or similar.
 A basic knowledge of undecidability, such as manyone reducibility and the undecidability of the halting problem.
Syllabus
 Review of computable functions, computably enumerable sets, and undecidability.
 Turing reducibility.
 The arithmetical hierarchy.
 Basic structure of the Turing degrees.
 Basic structure of the computably enumerable Turing degrees.
 Trees and diagonally noncomputable functions.
 Reverse mathematics.
 Algorithmic randomness.
Lecturer

PS
Dr Paul Shafer
 University
 University of Leeds
Bibliography
Follow the link for a book to take you to the relevant Google Book Search page
You may be able to preview the book there and see links to places where you can buy the book. There is also link marked 'Find this book in a library'  this sometimes works well, but not always  you will need to enter your location, but it will be saved after you do that for the first time.
 Computability Theory (S. Barry Cooper, book)
 Computability Theory (Rebecca Weber, book)
 Degrees of Unsolvability (Manuel Lerman, book)
 Recursively Enumerable Sets and Degrees (Robert I. Soare, book)
 Subsystems of Second Order Arithmetic (Stephen George Simpson, book)
 Theory of Recursive Functions and Effective Computability (Hartley Rogers, book)
 Turing Computability (Robert I. Soare, book)
Assessment
The assessment for this course will be released on Monday 9th May 2022 at 00:00 and is due in before Monday 23rd May 2022 at 11:00.
Assessment for all MAGIC courses is via takehome exam which will be made available at the release date (the start of the exam period).
You will need to upload a PDF file with your own attempted solutions by the due date (the end of the exam period).
If you have kept uptodate with the course, the expectation is it should take at most 3 hoursâ€™ work to attain the pass mark, which is 50%.
Please note that you are not registered for assessment on this course.
Files
Only current consortium members and subscribers have access to these files.
Please log in to view course materials.
Lectures
Please log in to view lecture recordings.