Est-il décidable de déterminer si une forme donnée peut carreler l'avion?

24

Je sais qu'il est indécidable de déterminer si un ensemble de tuiles peut carreler l'avion, un résultat de Berger utilisant des tuiles Wang . Ma question est de savoir s'il est également connu d'être indécidable pour déterminer si une seule tuile donnée peut carreler l'avion, un carrelage monoédrique .

Si cela reste instable, je serais intéressé de savoir quelle est la cardinalité minimale d'un ensemble de tuiles pour lesquelles il existe une preuve d'indécidabilité. (Je n'ai pas encore accédé à la preuve de Berger.)

reference-request co.combinatorics decidability undecidability Joseph O'Rourke
la source
Une autre preuve récente d'indécidabilité se trouve dans: Nicolas Ollinger; Les systèmes de substitution deux par deux et l'indécidabilité du problème domino ; Logic and Theory of Algorithms, 4th Conference on Computability in Europe, CiE 2008 ( pdf ) ... mais ils utilisent plus de tuiles (104) pour construire un jeu de tuiles apériodique (la preuve de Robinson utilise 56 tuiles)
Marzio De Biasi

Réponses:

23

Selon l'introduction de [1],

  • La complexité de déterminer si un seul polyomino tuile l'avion reste ouvert [2,3], et
  • Il existe une preuve d'indécidabilité pour les ensembles de 5 polyominos [4].

[1] Stefan Langerman, Andrew Winslow. Un algorithme à temps quasi-linéaire pour paver le plan de façon isohédrale avec un polyomino . Impressions électroniques ArXiv, 2015. arXiv: 1507.02762 [cs.CG]

[2] C. Goodman-Strauss. Questions ouvertes en mosaïque . En ligne, publié en 2000.

[3] C. Goodman-Strauss. Vous ne pouvez pas décider? indécis! Avis de l'American Mathematical Society, 57 (3): 343–356, 2010.

[4] N. Ollinger. Mosaïque de l'avion avec un nombre fixe de polyominos . Dans AH Dediu, AM Ionescu et C. Mart´ın-Vide, éditeurs, LATA 2009, volume 5457 de LNCS, pages 638–647. Springer, 2009.

Mangara
la source
14

Un commentaire étendu: un article récent de Demaine & al. prouve qu'une tuile suffit pour simuler un calcul arbitraire:

Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz, Robert T. Schweller, Andrew Winslow, Damien Woods; Une tuile pour les gouverner tous: Simuler n'importe quelle machine de Turing, système d'assemblage de tuiles ou système de carrelage avec une seule pièce de puzzle (2012)

mais le pavage n'est pas un pavage exact: "... Le système à un pavé de sortie nécessite que les pavés vivent sur le même réseau carré ou hexagonal, permet aux carreaux de tourner et est un pavage presque plan dans le sens où il laisse de minuscules espaces entre les tuiles. "

Marzio De Biasi
la source
Bien, c'est la réponse la plus rapide.
Mohammad Al-Turkistany,
@ MohammadAl-Turkistany: Il y a quelque temps, j'ai jeté un coup d'œil au papier mais j'ai oublié que le carrelage n'est pas exact ... J'ai modifié la réponse ... :-)
Marzio De Biasi