MAGIC107: Computability Theory and algorithmic randomness

Course details

A specialist MAGIC course

Semester

Spring 2025
Monday, January 27th to Friday, April 4th

Hours

Live lecture hours
10
Recorded lecture hours
0
Total advised study hours
40

Timetable

Fridays
12:05 - 12:55 (UK)

Course forum

Visit the https://v2.maths-magic.ac.uk/forums/magic107-computability-theory-and-algorithmic-randomness

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. 

Prerequisites

The following prerequisites are preferable but not essential:
  • A basic knowledge of first-order 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 many-one 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 non-computable functions.
Additional topics and applications:
  • 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.

  • Algorithmic Randomness and Complexity (Rodney G. Downey and Denis R. Hirschfeldt, book)
  • An Introduction to Kolmogorov Complexity and Its Applications (Ming Li and Paul Vitányi, book)
  • Computability and Randomness (André Nies, book)
  • 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)
  • 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 Tuesday 22nd April 2025 at 00:00 and is due in before Monday 5th May 2025 at 11:00.

Assessment for all MAGIC courses is via take-home 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 up-to-date 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.