The decision problems about the periodic solutions of the domino problems

MaRDI QIDQ798644zbMATH OpenFDO

Authors Yucai Lin

Publication date 1984

Published in Chinese Annals of Mathematics. Series B (Search for Journal in Brave)

zbMATH Keywords

domino problemsperiodic solutions

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25)

Review text

The domino problems were raised for the purpose of studying the AEA case of the first-order predicate sentences. The unsolvability of the origin- constrained, the diagonal-constrained, and the unrestricted domino problems were shown in 1960-1966, and along with this the unsolvability of the cases \(E\&AEA\) and AEA were obtained. In this paper, by reducing the Post Correspondence Problem to (1) the problem of deciding whether or not the origin-constrained domino problem has periodic solutions and (2) the problem of deciding whether or not the unrestricted domino problem has periodic solutions, it is obtained that the above two decision problems are both unsolvable.

Recommendations

• The periodic domino problem revisited
• The undecidability of the domino problem
• Recurring Dominoes: Making the Highly Undecidable Highly Understandable
• scientific article; zbMATH DE number 3876591
• The Periodic Domino Problem Is Undecidable in the Hyperbolic Plane

Cited in

(3)

• The undecidability of iterated modal relativization
• The periodic domino problem revisited
• Domino Problem Under Horizontal Constraints

This page was built for publication: The decision problems about the periodic solutions of the domino problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q798644)