Вікіпедія

Плитки Вана

клас формальних систем

Плитки Вана (або доміно Вана), вперше запропоновані математиком, логіком і філософом Хао Ваном[ru] в 1961, — це клас формальних систем. Вони моделюються візуально за допомогою квадратних плиток з розфарбуванням кожного боку. Визначається набір таких плиток (наприклад, як на ілюстрації), потім копії цих плиток прикладаються одна до одної з умовою узгодження кольорів сторін, але без обертання або симетричного відображення плиток.

Цей набір з 11 плиток Вана може заповнити площину тільки аперіодично.
Приклад замощення Вана 13-ма плитками.

Основне питання про набір плиток Вана — чи можуть вони замостити площину чи ні, тобто чи можна площину заповнити таким способом. Наступне питання, чи можна її заповнити у вигляді періодичного візерунка.

Задача доміно ред.

В 1961 році Ван висловив гіпотезу, що якщо скінченне число плиток Вана може замостити площину, то існує періодичне замощення, тобто мозаїка, інваріантна відносно паралельного перенесення на вектор у двовивимірній решітці на зразок шпалер. Він також зауважив, що ця гіпотеза має наслідком існування алгоритму, що визначає, чи може даний скінченний набір плиток Вана замостити площину[1][2]. Ідея обмеження з'єднання суміжних плиток виникла в грі доміно, так що плитки Вана відомі також під назвою доміно Вана[3], а алгоритмічна задача визначення, чи можуть плитки замостити площину, здобула популярність як задача доміно[4].

За словами студента Вана Роберта Бергера[en] [4] ,

Задача доміно має справу з класом усіх наборів доміно. Задача полягає у визначенні для кожного набору доміно, можливе чи ні замощення. Ми говоримо, що задачу доміно розв'язна або нерозв'язна, залежно від того, існує чи ні алгоритм, який за заданим набором довільного набору доміно визначає, можна розв'язати чи ні задачу замощення для цього набору.

Іншими словами, в задачі доміно запитується, чи існує ефективний метод, який правильно розв'язує задачу для заданих наборів доміно.

1966 року Бергер розв'язав задачу доміно, спростувавши гіпотезу Вана. Він довів, що не може існувати алгоритму, показавши, як перетворити будь-яку машину Тюрінга на набір плиток Вана, так що плитки замощують площину тоді й лише тоді, коли машина Тюрінга не зупиняється. З неможливості розв'язати проблему зупинки (завдання перевірки, чи зупиниться, зрештою, машина Тюрінга) тоді випливає неможливість розв'язати задачу замощення Вана[4][4].

Апериодичні набори плиток ред.

Комбінація результату Бергера зі спостереженням Вана показує, що повинен існувати скінченний набір плиток Вана, які замощують площину, але лише неперіодично. Цю властивість має мозаїка Пенроуза і розташування атомів у квазікристалі. Хоча оригінальний набір Бергера містив 20 426 плиток, він припустив, що менші набори можуть також існувати, зокрема підмножини його оригінального набору, та в опублікованих тезах його дисертації він скоротив число плиток до 104. Пізніше знайдено ще менші набори[5][6][7]. Наприклад, набір з 11 плиток і 4 кольорів, наведений вище, є неперіодичним набором, і його відкрили Еммануель Жандель і Майкл Рао в 2015 році, використовуючи повний перебір для доведення того, що 10 плиток або 3 кольорів недостатньо для аперіодичності[8].

Узагальнення ред.

Плитки Вана можна узагальнити різними способами й усі вони також нерозв'язні у вищенаведеному розумінні. Наприклад, куби Вана — це куби однакового розміру з розфарбованими гранями, які мають поєднуватися за кольором при створенні багатогранних замощень (стільників). Кулик і Карі показали неперіодичні набори кубів Вана[9]. Вінфрі та ін. показали можливість створення молекулярних «плиток» на основі ДНК (дезоксирибонуклеїнової кислоти), які можуть діяти на зразок плиток Вана[10]. Міттал і ін. показали, що з цих плиток можна скласти пептидо-нуклеїнові кислоти (ПНК), стійкі штучні подоби ДНК[11].

Застосування ред.

Плитки Вана нещодавно стали популярним засобом створення алгоритмічних текстур, полів висот та інших великих неповторюваних двовимірних наборів даних. Невелике число заздалегідь обчислених або створених вручну плиток можна зібрати швидко і дешево без очевидних повторень та періодичності. В цьому випадку звичайні неперіодичні мозаїки показали б свою структуру. Набори зі значно меншими обмеженнями, які забезпечують вибір щонайменше двох варіантів для будь-яких двох кольорів сторін, більш прийнятні, оскільки замощуваність легко забезпечується і кожну плитку можна обрати псевдовипадково[12][13][14][15]. Плитки Вана використовуються також під час перевірки розв'язності теорії клітинних автоматів[16].

В культурі ред.

Коротке оповідання Грега Ігена «Килим Вана», згодом розширене до роману «Діаспора»[en], розповідає про всесвіт, заповнений організмами і мислячими істотами у вигляді плиток Вана, утвореними візерунками складних молекул[17].

Див. також ред.

Примітки ред.

  1. ↑ Wang, 1961, с. 1–41.
  2. ↑ Wang, 1965, с. 98–106.
  3. ↑ Renz, 1981, с. 83–103.
  4. ↑ а б в г Berger, 1966, с. 72.
  5. ↑ Robinson, 1971, с. 177–209.
  6. ↑ Culik, 1996, с. 245–251.
  7. ↑ Kari, 1996, с. 259–264.
  8. ↑ Jeandel, Emmanuel; Rao, Michael (2015), An aperiodic set of 11 Wang tiles, CoRR, arXiv:1506.06492. (Показано неперіодичний набір з 11 плиток з 4 кольорами)}
  9. ↑ Culik, Kari, 1995, с. 675–686.
  10. ↑ Winfree, Liu, Wenzler, Seeman, 1998, с. 539–544.
  11. ↑ Lukeman, Seeman, Mittal, 2002.
  12. ↑ Stam, 1997.
  13. ↑ Cohen, Shade, Hiller, Deussen, 2003, с. 287–294.
  14. ↑ Wei, 2004, с. 55–63.
  15. ↑ Kopf, Cohen-Or, Deussen, Lischinski, 2006, с. 509–518.
  16. ↑ Kari, 1990, с. 379–385.
  17. ↑ Burnham, 2014, с. 72–73.

Література ред.

Посилання ред.

Отримано з https://uk.wikipedia.org/w/index.php?title=Плитки_Вана&oldid=36636371