کاشی های وانگ
دومینوهای وانگ[ویرایش]
دومینوهای وانگ (یا کاشیهای وانگ) که در سال ۱۹۶۱ توسط ریاضی‌دان، منطق‌دان و فیلسوف هائو وانگ ابداع شده است، یک دسته از سیستم‌های رسمی هستند که به وسیله‌ی کاشیهای مربع شکل رنگی به سمتی مدل شده اند که جلوه ی بصری دارند. یک مجموعه از این کاشیها انتخاب می‌شود، و نسخه‌هایی از کاشیها به طرفین با رنگ‌های مطابق، بدون چرخش یا بازتاب، به هم متصل می‌شوند.[ویرایش]
سوال اصلی درباره مجموعه‌ای از تایل‌های وانگ این است که آیا می‌تواند سطح صاف را پوشانده و یک صفحه بی‌نهایت کاملاً با این کاشیها پر شود یا نه؟
سوال بعدی این است که آیا می‌توان این کار را به صورت الگوی دوره‌ای انجام داد؟
مسئله دومینوها[ویرایش]
در سال ۱۹۶۱، وانگ فرضیه‌ای را ارائه کرد که اگر مجموعه‌ای متناهی از کاشیهای وانگ قادر به پوشش دادن صفحه باشند، آنگاه یک پوشش تناوبی نیز وجود دارد؛ که در ریاضیات، یک پوشش دوره‌ای، یک پوشش است که در برابر ترجمه با بردارهایی در شبکه دو بعدی ثابت باشد به عبارت دیگر، اگر بردارهایی از یک شبکه دو بعدی را به یک پوشش دوره‌ای بچسبانید، پوشش همچنان به شکل اولیه خود باقی می‌ماند.
می‌تواند به الگوی دیوارپوشی با تکرار یک الگوی کوچک‌تر در سراسر آن، شباهت داشته باشد جایی که الگوی کلی، یک تکرار از یک الگوی کوچک‌تر است.
به عبارت دیگر، الگوی کاغذ دیواری نیز یک نوع پوشش دوره‌ای است که با تکرار یک الگوی کوچک‌تر، الگوی بزرگتر و کاملتری ایجاد می‌شود. وی همچنین مشاهده کرد که این فرضیه به وجود یک الگوریتم برای تصمیم‌گیری در مورد اینکه آیا یک مجموعه متناهی از تایل‌های وانگ می‌توانند صفحه را پوشش دهند یا خیر، منجر خواهد شد. ایده محدود کردن تایل‌های مجاور به یکدیگر برای هم‌خوانی، در بازی دومینوها وجود دارد، به همین دلیل تایل‌های وانگ نیز به عنوان دومینوهای وانگ شناخته می‌شوند. با استناد بر شاگرد وانگ، رابرت برگر، مسئله دومینو با کلاس تمامی مجموعه های دومینوها سروکار دارد. این شامل تصمیم گیری در مورد این است که هر مجموعه دومینو قابل حل است یا نه. مسئله دومینو حل شدنی یا نشدنی است بسته به اینکه که با در نظر گرفتن مشخصات یک مجموعه دومینوی خاص، الگوریتمی برای آن وجود دارد که تصمیم بگیرد حل شدنی هست یا نه.
غیرقابل حل بودن مسئله (مسئله تست کردن اینکه آیا یک ماشین تورینگ در نهایت متوقف می شود یا خیر) به معنای عدم قطعیت مسأله تایلینگ وانگ می‌باشد.
به عبارت دیگر، مسئله دومینو این است که آیا یک روش موثر برای این وجود دارد که برای همه مجموعه های دادهشده، این مسئله را به درستی حل کند.
در سال ۱۹۶۶، برگر به صورت منفی مسئله دومینو را حل کرد. او با نشان دادن اینکه چگونه هر ماشین تورینگی را به مجموعه‌ای از کاشیهای وانگ تبدیل میکند که صفحه را در صورت عدم خاتمه ماشین تورینگی پوشش می‌دهد، ثابت کرد که هیچ الگوریتمی برای این مسئله وجود ندارد. سپس، نامعین بودن مسئله خاتمه (مسئله آزمایش اینکه آیا یک ماشین تورینگی در نهایت خاتمه می‌یابد یا خیر) منجر به نامعین بودن مسئله پوشش دادن وانگ شد.
مجموعه متناوب از کاشی ها[ویرایش]
ترکیب نتیجهای که برگر به دست آورد و مشاهدهی وانگ، نشان می‌دهد که باید مجموعه‌ای متناهی از کاشیهای وانگ وجود داشته باشد که صفحه را پوشش داده، اما به طور غیر دوره‌ای.
این شبیه به پوشش کاشی پنروز یا ترتیب اتم‌ها در یک شبه کریستال است. اگرچه مجموعه‌ی اصلی برگر دارای 20.426 کاشی بود، او حدس زد که مجموعه‌های کوچکتری نیز وجود دارند، از جمله زیرمجموعه‌های مجموعه‌ی خود. همچنین در پایان‌نامه‌ی دکترای منتشر شده‌ی خود، تعداد کاشیها را به ۱۰۴ کاشی کاهش داد. در سال‌های بعد، مجموعه‌های کوچکتری پیدا شدند. برای مثال یک مجموعه از 13 کاشی نامتناوب توسط کارل کولیک دوم در سال 1996 منتشر شد.
تعمیم[ویرایش]
کاشیهای وانگ به صورت معمول در روش های مختلفی قابل تعمیم است، که همگی از لحاظ بالا نیز غیرقطعی هستند.
یک مجموعه کوچک از کاشیهای منبع پیش‌محاسبه شده یا دست‌ساز، به صورت بسیار ارزان و بدون تکرارهای مشخص و دوره‌ای قابل ترکیب است. در این حالت، کاشی های بدون تناوب سنتی ساختار بسیار منظم خود را نشان می‌دهند؛ مجموعه‌های با محدودیت کمتر که حداقل دو انتخاب کاشی برای هر دو رنگ لبه داده شده را تضمین میکنند، به دلیل قابلیت کاشی شدن آسان و انتخاب هر جزء کاشی به صورت تصادفی، رایج هستند. همچنین در اثبات‌های تصمیم‌پذیری نظریه ماشینهای بر پایه DNA هم استفاده شده است. برای مثال، مکعب های وانگ، مکعب هایی با اندازه یکسان و صفحات رنگی هستند و رنگ های لبه ها را می‌توان در هر سلسله چندضلعی مطابقت داد. کولیک و کاری مجموعه های متناوب آشکار وانگ را به نمایش گذاشته‌اند.
وینفری و همکارانش، امکان ساخت کاشی های مولکولی DNA را که همانند کاشی های وانگ عمل میکنند را، به روش پذیرفتنی نشان داده اند.
میتال و همکاران نشان داده اند که این تایل‌ها می توانند از پپتید نوکلئیک اسید (PNA) تشکیل شوند، که یک شبیه ساز مصنوعی پایدار DNA است.
کاشی های وانگ در هنر و فرهنگ[ویرایش]
در داستان کوتاه فرش های وانگ، که بعدها به رمانی با نام دیاسپورا (Diaspora) تبدیل شد، نویسنده گرگ ایگان، فرضیه ای را با جهان مطرح میکند که در آن موجودات ساکن و موجودات هوشمند با استفاده از الگوهای مولکولی پیچیده، به صورت کاشی های وانگ پیاده‌سازی شده‌اند.
منابع[ویرایش]