کاشی ونگ

این مجموعه 11تایی از کاشی های وانگ که هواپیما را مفروش می کند. اما فقط به صورت متناوبی.

کاشی‌های وانگ (یا دومینوهای وانگ )، که اولین بار توسط ریاضیدان، منطق‌دان و فیلسوف هائو وانگ در سال 1961 ارائه شد، دسته‌ای از سیستم‌های رسمی هستند؛ که به وسیله‌ی کاشی‌های مربع شکل رنگی به سمتی مدل شده­ اند که جلوه­ ی بصری دارند. یک مجموعه از این کاشی­ها انتخاب می‌شود، و نسخه‌هایی از کاشی‌ها به طرفین با رنگ‌های مطابق، بدون چرخش یا بازتاب، به هم متصل می‌شوند.

سوال اصلی در مورد مجموعه ای از کاشی های وانگ این است که آیا می تواند سطح صاف را پوشانده و یک صفحه بی‌نهایت کاملاً با این کاشی‌ها پر شود یا نه؟ سوال بعدی این است که آیا می توان این کار را به صورت تناوبی انجام داد؟

مسئله دومینو

نمونه ای اپوشاندن سطح با 13 کاشی.

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

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

مسئله الگوریتمی تعیین اینکه آیا یک مجموعه کاشی می‌تواند سطح را پوشش دهد به عنوان مسئله دومینو شناخته می‌شود.

به گفته شاگرد وانگ، رابرت برگر ،

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

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

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

مجموعه هایی تناوبی از کاشی

کاشی‌های وانگ با جایگزین کردن لبه های هر تکه همرنگ میشود – این مجموعه با مجموعه مینیمال Jeandel و Rao در تصویر بالا هم شکل است.

ترکیب نتیجه ­ای که برگر به دست آورد و مشاهده­ ی وانگ، نشان می‌دهد که باید مجموعه‌ای متناهی از کاشی‌های وانگ وجود داشته باشد که صفحه را پوشش داده، اما به طور غیر دوره‌ای. به صورت دوره‌ای . این شبیه به کاشی کاری پنروز یا آرایش اتم ها در یک شبه کریستال است. اگرچه مجموعه اصلی برگر شامل 20426 کاشی بود، او حدس زد که مجموعه‌های کوچک‌تری وجود دارد و سال‌های بعد در پایان‌نامه‌ی دکترای منتشر نشده‌ی خود، مجموعه‌های کوچک‌تری پیدا کرد. به عنوان مثال، مجموعه ای از 13 کاشی دوره ای توسط Karel Culik II در سال 1996 منتشر شد.

کوچکترین مجموعه کاشی های تناوبی توسط امانوئل ژاندل و مایکل رائو در سال 2015 با 11 کاشی و 4 رنگ کشف شد. آنها از یک جستجوی کامپیوتری جامع استفاده کردند تا ثابت کنند که 10 کاشی یا 3 رنگ برای تناوبی کردن کاشی ها کافی نیستندو این مجموعه، که در تصوی بالا نشان داده شده است، می‌توانید با دقت بیشتری در File:Wang 11 tiles.svg بررسی کنید.

تعمیم ها

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

کاربرد

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

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

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

در فرهنگ عامه

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

همچنین ببینید

• پازل تطبیق لبه

لینک های خارجی

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

This article "کاشی ونگ" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:کاشی ونگ. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

---

 Facebook Page

 Follow us on Twitter !

Read or create/edit this page in another language

• کاشی ونگ in English