WHY IS TILING HARD: The Tiling Machine Construction and Complexity of Mathematical Tiling Problems

While introducing mathematical tilings last time, the question of 'Why is Tiling Hard?' or 'How difficult is tiling?' came up briefly with little explanation given. This week, I wanted to dive deeper into the complexity of mathematical tiling problems and the tiling machine construction which presents a connection between Turing machines and tiling problems. Our dive into a bit of computational complexity theory concerning Turing machines and mathematical tilings will give us enough information to address our questions and help explain why a computer can't help you tile the plane.

=======================================================================
The tiling machine construction we use is derived from this 1971 paper by R.M. Robinson
https://users.cs.duke.edu/~reif/cours...

If your interested in the paper showing that Magic the Gathering is Turing Complete.
https://arxiv.org/abs/1904.09828

=======================================================================
_____________________
Last Video :    • WHAT IS THE DEFINITION OF A MATHEMATI...  
The CHALKboard:    / chalkboard  
Find the CHALKboard on Facebook: http://bit.ly/CHALKboard
_____________________

#CHALK #Undecidability #TilingMachine #TuringMachine #HaltingProblem