# Sigma^1_1-Complete Tilings

**Date**: Wednesday 20 February 2019, 14:00 – 15:00**Location**: Mathematics Level 8, MALL 1, School of Mathematics**Type**: Proofs, Constructions and Computations, Seminars, Pure Mathematics**Cost**: Free

#### Mark Carney, University of Leeds. Part of the Proof, Constructions and Computations Seminar Series

It is well known that the Domino Problem - the question of whether a given set of prototiles S can tile the plane - is equivalent to the Halting Problem for finite sets of prototiles. We present some results that show that for computable, infinite sets of prototiles, the Domino Problem is Sigma^1_1-complete, being equivalent to the question of the ill-foundedness of infinite trees.