Easy proofs of the undecidability of Wang's tiling problem?

Wang tiles are (by Wikipedia): "equal - sized squares with a shade on each side which can be prepared alongside (on a normal square grid) to make sure that abutting sides of surrounding floor tiles have the very same shade ; the floor tiles can not be revolved or reflected."

The common choice trouble related to them is: offered a set of floor tiles, can they floor tile the aircraft?

This trouble is recognized to be undecidable and also has a wonderful background (Wang initially offered a choice procedure, yet it functions just if the floor tiles create a routine tiling, while there exists collections which offer surge just to nonperiodic tilings). It has actually attracted me directly for a long time

The state - of - the - art evidence of undecidability I'm acquainted with is that of Raphael Robinson ("Undecidability and also Nonperiodicity for Tilings of the Plane, " Inventiones Mathematicae, 12 (3 ), 1971 pp. 177-- 209). It is fairly a hard evidence, and also I have actually never ever seen it in books.

I'm acquainted with a a lot easier variation - this moment the set just requires to floor tile a quadrant of the aircraft, and also the edge floor tile is currently offered. This trouble is a lot easier to take care of - the offered edge floor tile allows us to "run a Turing machine" in the tiling (each row is an arrangement) and also undecidability adheres to. Nonetheless, this outcome is largely a "folklore" variation - I do not remember it in books in all.

This brings about my inquiry: has Robinson is method been boosted yet continues to be mythology, therefore disappointed in books? Exists a reasonably straightforward evidence of the undecidability of the basic tiling trouble I'm missing out on?

2022-06-07 14:31:51
Source Share
Answers: 1

There's a newer proof given in "Two-by-Two Substitution Systems and the Undecidability of the Domino Problem", by Nicolas Ollinger. It seems to be available online at: http://hal.inria.fr/docs/00/26/01/12/PDF/sutica.pdf. Hopefully, it is easier to understand than Robinson's proof.

2022-07-21 07:30:48