On the domino problem of the Baumslag-Solitar groups
Nathalie Aubrun, Jarkko Kari · Theoretical Computer Science · 2021
In [1] we construct aperiodic tile sets on the Baumslag-Solitar groups BS(m,n). Aperiodicity plays a central role in the undecidability of the classical domino problem on Z2, and analogously to this we state as a corollary of the main construction that the Domino problem is undecidable on all Baumslag-Solitar groups. In the present work we elaborate on the claim and provide a full proof of this fact. We also provide details of another result reported in [1]: there are tiles that tile the Baumslag-Solitar group BS(m,n) but none of the valid tilings is recursive. The proofs are based on simulating piecewise affine functions by tiles on BS(m,n).