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
 11:05  11:55
Course forum
Visit the MAGIC107 forum
Description
This is an introductory course on computability theory, the branch of mathematical logic concerned with classifying sets of natural numbers by how much extra information is needed to describe them by computer programs. The computational strength of a set is intimately tied to the complexity of its definition, thus, more generally, computability theory is the study of definable sets of natural numbers. Any countable mathematical object, such as a countable ring or a countable graph, can be coded by a set of natural numbers. A continuous function on the reals, for example, can be coded by a set of natural numbers too. Thus the techniques and results of computability theory can be applied to describe the complexities of all manner of mathematical objects.
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.
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
The following prerequisites are preferable but not essential:
 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
Core topics:
 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
No bibliography has been specified for this course.
Assessment
Attention needed
Assessment information will be available nearer the time.
Lectures
Please log in to view lecture recordings.