Ollinger's conjecture on undecidability of 8-, 9-, and 10-polyomino tiling

From papers

For a fixed positive integer kk, the kk-polyomino tiling problem asks whether there is an algorithm deciding whether a set of kk polyominoes can tile the plane by translated copies from the set. Ollinger's conjecture. The kk-polyomino tiling problem is undecidable for k=8,9,10k=8,9,10. Ollinger had already proved undecidability for k=11k=11, while the conjecture was motivated by the existence of an aperiodic set of 88 polyominoes. The present paper claims to prove the conjecture by establishing the k=8k=8 case; the cases k=9,10k=9,10 then follow by adding redundant polyominoes.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Chao Yang and Zhujun Zhang, “A proof of Ollinger's conjecture: undecidability of tiling the plane with a set of 8 polyominoes”, arXiv:2403.13472 (2024).

Solutions 0

No solutions have been posted yet.