A PA undecidable Domino Problem

Mark Carney, University of Leeds. Part of the proofs, constructions and computations seminar series.

After van Emde Boas (1996) it became clear that tilings have the ability to code significant amounts of behaviour and information in their combinatorial structure. We will demonstrate the general definitions, idea, and some results concerning tilings, as well as some results on small Universal Turing Tilings. We will then present a tiling that is in some specific sense undecidable in PA, showing that PA does not decide the Domino Problem for some specific tiling set.

Mark Carney, University of Leeds