×

zbMATH — the first resource for mathematics

Undecidable tiling problems in the hyperbolic plane. (English) Zbl 0354.50006
In his earlier paper [Invent. Math. 12, 177–209 (1970; Zbl 0197.46801)] the author proposed the problem of extending to the hyperbolic plane the undecidability and nonperiodicity results known for tilings of the Euclidean plane. In the present paper he succeeds in extending the undecidability results for the simplest case, that is, the origin-constrained case. He also finds a set of 49 polygons for which the completion problem is undecidable. The other problems remain open.
Reviewer: R. M. Robinson

MSC:
51M10 Hyperbolic and elliptic geometries (general) and generalizations
05B45 Combinatorial aspects of tessellation and tiling problems
03D35 Undecidability and degrees of sets of sentences
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] Berger, R.: The undecidability of the domino problem. Mem. Amer. Math. Soc. no.66 (1966) · Zbl 0199.30802
[2] Gardner, M.: Extraordinary nonperiodic tiling that enriches the theory of tiles. Sci. Amer.236, no. 1, 110?121 (1977) · doi:10.1038/scientificamerican0177-110
[3] Hanf, W.: Nonrecursive tilings of the plane ? I. J. Symbolic Logic39, 283?285 (1974) · Zbl 0299.02054 · doi:10.2307/2272640
[4] Myers, D.: Nonrecursive tilings of the plane ? II. J. Symbolic Logic39, 286?294 (1974) · Zbl 0299.02055 · doi:10.2307/2272641
[5] Robinson, R.M.: Undecidability and nonperiodicity for tilings of the plane. Invent. Math.12, 177?209 (1971) · Zbl 0207.51305 · doi:10.1007/BF01418780
[6] Wang, H.: Proving theorems by pattern recognition ? II. Bell System Tech. J.40, 1?41 (1961) · doi:10.1002/j.1538-7305.1961.tb03975.x
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.