Можно ли определить, может ли данная фигура покрывать плоскость?

24

Я знаю, что неразрешимо определить, может ли набор плиток укладывать плитку в результате того, что Бергер использовал плитки Ванга . Мой вопрос состоит в том, известно ли также, что неразрешимо определить, может ли один данный фрагмент мозаики составить плоскость - моноэдральный фрагмент .

Если это не будет решено, мне было бы интересно узнать, какова минимальная мощность множества плиток, для которых есть доказательство неразрешимости. (Я еще не получил доступ к доказательству Бергера.)

Джозеф О'Рурк
источник
Еще одно недавнее доказательство неразрешимости можно найти в: Николас Олингер; Системы подстановки две на две и неразрешимость проблемы домино ; Логика и теория алгоритмов, 4-я конференция по вычислимости в Европе, CiE 2008 ( pdf ) ... но они используют больше плиток (104) для построения апериодического набора плиток (доказательство Робинсона использует 56 плиток)
Марцио Де Биаси

Ответы:

23

Согласно введению [1],

  • Сложность определения того, остается ли одиночная полиомино черепица плоскостью открытой [2,3], и
  • Существует доказательство неразрешимости для множеств из 5-ти полиомино [4].

[1] Стефан Лангерман, Эндрю Уинслоу. Алгоритм квазилинейного времени для изоэдрального разбиения плоскости на полиомино . ArXiv e-prints, 2015. arXiv: 1507.02762 [cs.CG]

[2] С. Гудман-Штраус. Открытые вопросы в плитке . Онлайн, опубликовано 2000.

[3] С. Гудман-Штраус. Не можете решить? undecide! Уведомления Американского математического общества, 57 (3): 343–356, 2010.

[4] Н. Оллингер. Черепица плоскости с фиксированным количеством полиомино . В AH Dediu, AM Ionescu и C. Mart´in-Vide, редакторы, LATA 2009, том 5457 LNCS, страницы 638–647. Springer, 2009.

Mangara
источник
14

Расширенный комментарий: недавняя статья Demaine & al. доказывает, что одной плитки достаточно для имитации произвольного вычисления:

Эрик Д. Демейн, Мартин Л. Демейн, Шандор П. Фекете, Мэтью Дж. Патитц, Роберт Т. Швеллер, Эндрю Уинслоу, Дэмиен Вудс; Одна плитка для управления всеми: имитация любой машины Тьюринга, системы сборки плитки или системы плитки с помощью одного кусочка головоломки (2012)

но мозаика не является точной мозаикой: «... Выходная система с одной плиткой требует, чтобы плитки располагались на одной и той же квадратной или гексагональной решетке, позволяла вращать плитки и была почти плоской плиткой в ​​том смысле, что она оставляла крошечные промежутки между плитки. ... "

Марцио де Биаси
источник
Хорошо, это самый быстрый ответ.
Мухаммед Аль-Туркистани
@ MohammadAl-Turkistany: Некоторое время назад я быстро взглянул на газету, но забыл, что тайлинг не точный ... Я изменил ответ ... :-)
Марцио Де Биаси