Is the following problem known to be un/decidable? Problem: Given a finite configuration of Penrose tiles in the plane, determine if there is an extension of the configuration tiling the whole plane.
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ Yes. Definition by local matching rules implies the set of extendable patterns is co-recursively enumerable, and minimality implies it is recursively enumerable. $\endgroup$– Ville SaloJun 4 at 14:56
-
1$\begingroup$ By primitivity, for a patch of a particular radius, we know that we just need to look at the $n$th iterature of the substitution on a tile, where $n$ is a known function of $r$. If the patch is legal, it can be found in that supertile. If not, then it won't be found. $\endgroup$– Dan RustJun 4 at 17:18
-
$\begingroup$ @DanRust: FWIW we said almost the same thing $\endgroup$– Ville SaloJun 4 at 18:48
-
$\begingroup$ @VilleSalo haha sorry, I was thinking more about the substitution definition, and I saw you'd mentioned matching rules so figured I would give a different approach. $\endgroup$– Dan RustJun 4 at 20:30
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Apparently it is decidable, as proved in theorem 27 here: https://people.maths.ox.ac.uk/ritter/masterclasses/ritter-lectures-on-penrose-tilings.pdf