Sigma^1_1-Complete Tilings

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.