March 20, 2024Open Access

A proof of Ollinger's conjecture: undecidability of tiling the plane with a set of 8 polyominoes

Key Points

Key points are not available for this paper at this time.

Abstract

We give a proof of Ollinger's conjecture that the problem of tiling the plane with translated copies of a set of 8 polyominoes is undecidable. The techniques employed in our proof include a different orientation for simulating the Wang tiles in polyomino and a new method for encoding the colors of Wang tiles.

Read Full Paperexternally

Bookmark

View Full Paper

Cite This Study

Yang et al. (Wed,) studied this question.

synapsesocial.com/papers/68e733cdb6db6435876ad9eb https://doi.org/https://doi.org/10.48550/arxiv.2403.13472

Also Consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

1Undecidability of Translational Tiling of the Plane with Four Tiles2025
2Undecidability of Tiling the Plane with a Fixed Number of Wang Bars2026
3Undecidability of Translational Tiling of the 4-dimensional Space with a Set of 4 Polyhypercubes2024
4Two Tiling is Undecidable2025
5Undecidability of Translational Tiling with 2 Polycubes2025

Bookmark

View Full Paper