Я знаю, что неразрешимо определить, может ли набор плиток укладывать плитку в результате того, что Бергер использовал плитки Ванга . Мой вопрос состоит в том, известно ли также, что неразрешимо определить, может ли один данный фрагмент мозаики составить плоскость - моноэдральный фрагмент .
Если это не будет решено, мне было бы интересно узнать, какова минимальная мощность множества плиток, для которых есть доказательство неразрешимости. (Я еще не получил доступ к доказательству Бергера.)
reference-request
co.combinatorics
decidability
undecidability
Джозеф О'Рурк
источник
источник
Ответы:
Согласно введению [1],
[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.
источник
Расширенный комментарий: недавняя статья Demaine & al. доказывает, что одной плитки достаточно для имитации произвольного вычисления:
Эрик Д. Демейн, Мартин Л. Демейн, Шандор П. Фекете, Мэтью Дж. Патитц, Роберт Т. Швеллер, Эндрю Уинслоу, Дэмиен Вудс; Одна плитка для управления всеми: имитация любой машины Тьюринга, системы сборки плитки или системы плитки с помощью одного кусочка головоломки (2012)
но мозаика не является точной мозаикой: «... Выходная система с одной плиткой требует, чтобы плитки располагались на одной и той же квадратной или гексагональной решетке, позволяла вращать плитки и была почти плоской плиткой в том смысле, что она оставляла крошечные промежутки между плитки. ... "
источник