×

zbMATH — the first resource for mathematics

Undecidability and nonperiodicity for tilings of the plane. (English) Zbl 0197.46801

MSC:
52C20 Tilings in \(2\) dimensions (aspects of discrete geometry)
05B45 Combinatorial aspects of tessellation and tiling problems
03D35 Undecidability and degrees of sets of sentences
51M20 Polyhedra and polytopes; regular figures, division of spaces
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] Büchi, J. R.: Turing-machines and the Entscheidungsproblem. Math. Ann.148, 201-213 (1962). · Zbl 0118.01602 · doi:10.1007/BF01470748
[3] Cocke, J., Minsky, M.: Universality of tag systems withP=2. J. Assoc. Comput. Mach.11, 15-20 (1964). · Zbl 0149.12405
[4] Kahr, A. S., Moore, E. F., Wang, H.: Entscheidungsproblem reduced to the AEA case. Proc. Nat. Acad. Sci. U.S.A.48, 365-377 (1962). · Zbl 0102.00801 · doi:10.1073/pnas.48.3.365
[5] König, D.: Über eine Schlußweise aus dem Endlichen ins Unendliche. Acta Litt. Sci. Szeged3, 121-130 (1927). · JFM 53.0170.04
[6] Minsky, M. L.: Computation: Finite and infinite machines. Englewood Cliffs, N.J.: Prentice-Hall 1967. · Zbl 0195.02402
[7] Robinson, R. M.: Seven polygons which permit only nonperiodic tilings of the plane (abstract). Notices Amer. Math. Soc.14, 835 (1967).
[8] Wang, H.: Proving theorems by pattern recognition ? II. Bell System Tech. J.40, 1-41 (1961).
[9] ?: Dominoes and the AEA case of the decision problem, Mathematical theory of automata, p. 23-55. Brooklyn, N. Y.: Polytechnic Press 1963.
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.