- 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.