کاشی ونگ

بندانگشتی| این مجموعه ۱۱تایی از کاشی‌های وانگ که هواپیما را مفروش می‌کند. اما فقط به صورت متناوبی.|186x186پیکسل
**کاشی‌های وانگ** (یا **دومینوهای وانگ**)، که اولین بار توسط ریاضیدان، منطق‌دان و فیلسوف هائو وانگ در سال ۱۹۶۱ ارائه شد، دسته‌ای از سیستم‌های رسمی هستند؛ که به وسیلهٔ کاشی‌های مربع شکل رنگی به سمتی مدل شده‌اند که جلوهٔ بصری دارند. یک مجموعه از این کاشیها انتخاب می‌شود، و نسخه‌هایی از کاشی‌ها به طرفین با رنگ‌های مطابق، بدون چرخش یا بازتاب، به هم متصل می‌شوند.

## مسئله دومینو
بندانگشتی|225x225px| نمونه ای اپوشاندن سطح با ۱۳ کاشی.
در سال ۱۹۶۱، وانگ فرضیه‌ای را ارائه کرد که اگر مجموعه‌ای متناهی از کاشی‌های وانگ قادر به پوشش دادن صفحه باشند، آنگاه یک پوشش تناوبی نیز وجود دارد؛ در ریاضیات، یک پوشش تناوبی، پوششی است که معادل است با بردارهایی در شبکه دو بعدی ثابت اند. به عبارت دیگر، اگر بردارهایی از یک شبکه دو بعدی را به یک پوشش دوره‌ای بچسبانید، پوشش همچنان به شکل اولیه خود باقی می‌ماند.

او همچنین مشاهده کرد که این فرضیه به این معناست که الگوریتمی وجود دارد که تصمیم‌گیری اینکه آیا مجموعه محدودی از کاشی‌های وانگ می‌تواند سطح را پوشش دهد یا خیر. این ایده که کاشی‌های مجاور باید با یکدیگر هم‌خوانی داشته باشند، در بازی دومینو وجود دارد، بنابراین کاشی‌های وانگ به عنوان **دومینوهای وانگ** نیز شناخته می‌شوند. مسئله الگوریتمی تعیین اینکه آیا یک مجموعه کاشی می‌تواند سطح را پوشش دهد به عنوان مسئله دومینو شناخته می‌شود.

به گفته شاگرد وانگ، رابرت برگر،به عبارت دیگر، مسئله دومینو این است که آیا روش مؤثری وجود دارد که برای همه مجموعه‌های دادهشده، این مسئله را به درستی حل کند.

در سال ۱۹۶۶، برگر به صورت منفی مسئله دومینو را حل کرد. او با نشان دادن اینکه چگونه هر ماشین تورینگی را به مجموعه ای از کاشی‌های وانگ تبدیل می‌کند، ثابت کرد که هیچ الگوریتمی برای مشکل نمی‌تواند وجود داشته باشد، اگر و تنها اگر ماشین تورینگ متوقف نشود. تصمیم‌ناپذیر بودن مسئله توقف (مسئله آزمایش اینکه آیا ماشین تورینگ در نهایت متوقف می‌شود) منجر به نامعین بودن مسئله پوشش دادن وانگ شد

## مجموعه‌هایی تناوبی از کاشی
بندانگشتی| کاشی‌های وانگ با جایگزین کردن لبه‌های هر تکه همرنگ می‌شود &#x2013; این مجموعه با مجموعه مینیمال Jeandel و Rao در تصویر بالا هم شکل است.
ترکیب نتیجه ای که برگر به دست آورد و مشاهدهٔ وانگ، نشان می‌دهد که باید مجموعه‌ای متناهی از کاشی‌های وانگ وجود داشته باشد که صفحه را پوشش داده، اما به‌طور غیر دوره‌ای. *به صورت دوره‌ای*. این شبیه به کاشی کاری پنروز یا آرایش اتم‌ها در یک شبه کریستال است. اگرچه مجموعه اصلی برگر شامل ۲۰۴۲۶ کاشی بود، او حدس زد که مجموعه‌های کوچک‌تری وجود دارد و سال‌های بعد در پایان‌نامهٔ دکترای منتشر نشدهٔ خود، مجموعه‌های کوچک‌تری پیدا کرد. به عنوان مثال، مجموعه ای از ۱۳ کاشی دوره ای توسط Karel Culik II در سال 1996 منتشر شد.

کوچک‌ترین مجموعه کاشی‌های تناوبی توسط امانوئل ژاندل و مایکل رائو در سال ۲۰۱۵ با ۱۱ کاشی و ۴ رنگ کشف شد. آنها از یک جستجوی کامپیوتری جامع استفاده کردند تا ثابت کنند که ۱۰ کاشی یا ۳ رنگ برای تناوبی کردن کاشی‌ها کافی نیستندو این مجموعه، که در تصوی بالا نشان داده شده است، می‌توانید با دقت بیشتری در File:Wang 11 tiles.svg بررسی کنید.

## تعمیم‌ها
کاشی‌های وانگ را به طرق مختلفی می‌توان تعمیم داد، که همگی همانگونه که گفته شد قابل تصمیم‌گیری نیستند. به عنوان مثال، *مکعب‌های وانگ* مکعب‌هایی با اندازه‌های مساوی و رنگی هستند و رنگ‌های مجاور را می‌توان روی هر سطح چند ضلعی مطابقت داد. کولیک و کاری مجموعه‌های متناوب از مکعب‌های وانگ را نشان داده‌اند. وینفری و همکارانش نشان داده‌اند که از مولکول DNA (دئوکسی ریبونوکلئیک اسید) می‌توان سطحی را به صورت دومینوی وانگی مفروش کرد. میتال و همکاران نشان داده‌اند که این کاشی‌ها همچنین می‌توانند از پپتید نوکلئیک اسید (PNA)، یک تقلید مصنوعی پایدار DNA نیز تشکیل شوند.

## کاربرد
کاشی‌های وانگ برای سنتز رویه‌ای بافت‌ها، ارتفاعات و سایر مجموعه‌های داده دو بعدی بزرگ و غیر تکراری استفاده شده‌اند. مجموعه کوچکی از کاشی‌های منبع از پیش محاسبه شده یا دست‌ساز را می‌توان بسیار ارزان و بدون تکرارهای خیلی واضح و نامتناوب مونتاژ کرد. در این مورد، کاشی‌کاری‌های دوره ای سنتی، نشان می‌دهد که ساختیار خیلی منظمی دارد. مجموعه‌هایی که محدودیت کمتری دارند و دو کاشی را انتخاب می‌کنند به دلیل سهولت در قابلیت کاشی شده و گزینش هر کاشی قابل اطمینان هستند، رایج است.

چرا که کاشی‌پذیری به راحتی تضمین می‌شود و هر کاشی را می‌توان به صورت تصادفی انتخاب کرد.

از نظریه دومینوی وانگ در اثبات تصمیم پذیری تئوری اتوماتای سلولی نیز استفاده شده است.

## در فرهنگ عامه
داستان کوتاه *فرش‌های وانگ*، که بعداً به رمان *دیاسپورا*، اثر گرگ ایگان تبدیل شد، دنیایی را فرض می‌کند که موجودات ساکن و هوشمند، که با الگوهای مولکولی پیچیده به‌صورت کاشی‌های وانگ اجرا شده‌اند، تجسم می‌کند.

## منابع

## پیوند به بیرون
* صفحه استیون داچ شامل تصاویر بسیاری از کاشی کاری‌های دوره ای است
* نمایش متحرک روش کاشی کاری ساده وانگ - به جاوا اسکریپت و HTML5 نیاز دارد

رده:مسئله‌های تصمیم‌ناپذیر
رده:نظریه محاسبات