10
$\begingroup$

I am working on projects in solving ground state of generalized Ising models. One recent work involves tiling with basic tiles that filled the whole lattice. For example, we could obtain results: enter image description here

Every row corresponds to one constructible structure with basic tiles being "Generating configurations of the structure".

The resulting structures could be shown as followed:

enter image description here

9 and 12 are more complicated (can be periodic or aperiodic) shown as followed: enter image description here enter image description here

I realize (with the help of community), this is actually related to Wang tiles. So the first few steps I wish to approach this problem are looking into all established theorems on Wang tiles. Could someone suggest some relevant reference?

(PS:From engineering respective, I think we (in engineer department) commonly would agree that as long as we could keep tiling the plane to a sufficiently large extent( e.g use 100*100 tiles without conflict), then we blindly think these few basics tiles could tile the plane. So the undecidability is not too crucial...)

$\endgroup$
2

2 Answers 2

6
$\begingroup$

Original references (Wang's "Proving theorems by pattern recognition" and Berger's "The undecidability of the domino problem") are not very friendly. You may find some reviews around, though.

I'll suggest you to take a look at Jarkko Kari's website where you will find some introductory material and these slides for some basic notions and references.

$\endgroup$
3
$\begingroup$

If you are interested in Wang Tiling with Cellular Automata, which combines the two fields researched by Jarkko Kari as per Melquíades Ochoa, consider research in Erik Winfree's Algorithmic Tile Self-Assembly. He dives into Wang tiling and its specific applications in his Turing Complete (automata-esque) model. Here is a specific paper: https://authors.library.caltech.edu/22766/1/SAcircuits_DNA9_preprint.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.