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

About 2 years old · traced to

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.

References

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).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.