کاشی ونگ
کاشی ونگ که برای نخستین بار توسط یک ریاضیدان، منطقدان و فیلسوف چینی آمریکایی به اسم «هاو ونگ» در سال ۱۹۶۱ مطرح شد، یک کلاس از سیستم‌های صوری می‌باشد. این کاشی‌ها به صورت مربع‌های هم اندازه که هر ضلع آن به یک رنگ است و آن هارا به صورتی کنار هم می‌گذارند که هر دو ضلع همجوار دو مربع همجوار دارای یک رنگ باشند مدل می‌شود (کاشی‌ها نمی‌توانند چرخیده یا برعکس شوند).
سؤال اصلی در مورد یک مجموعه از کاشی‌های ونگ این است که آیا این مجموعه می‌تواند یک سطح نامحدود را به طور کامل با توجه به قوانین ذکر شده بپوشاند یا خیر.
مسئله دومینو
[ویرایش]در سال ۱۹۶۱، ونگ حدس زد که اگر یک مجموعه محدود از کاشی‌های ونگ بتوانند سطح را بپوشانند، آنگاه یک کاشی کاری متناوب نیز وجود دارد، یعنی، کاشی کاریی که از تکرار یک طرح کاشی کاری محدود در دو بعد ایجاد شود. ونگ همچنین مشاهده کرد که این حدس این مفهوم را می‌رساند که یک الگوریتم وجود دارد که تصمیم می‌گیرد آیا یک مجموعهٔ محدود مشخص از کاشی‌های ونگ می‌توانند سطح را بپوشانند یا نه. این قانون که دو کاشی کنار هم باید با یکدیگر مچ شوند در بازی دومینو، نیز دیده می‌شود، به همین خاطر به کاشی‌های ونگ دومینوهای ونگ نیز گفته می‌شود. مسئله الگوریتمی تعیین این که آیا سطح را می‌توان با یک مجموعه کاشی پوشاند با نام مسئله دومینو شناخته می‌شود. با استناد به سخنان دانشجوی ونگ، «رابرت برگر»،
مسئلهٔ دومینو با تمام مجموعه‌های دومینو در ارتباط است. این مسئله شامل تصمیم‌گیری برای این سؤال برای هر مجموعه دومینو است که آیا قابل حل است یا خیر. ما می‌گوییم که مسئله دومینو قابل حل یا غیرقابل حل است با توجه به اینکه آیا الگوریتمی وجود دارد که، با دادن مشخصات یک مجموعه اتفاقی دومینو، بتواند تصمیم بگیرد که آیا آن مجموعه قابل حل است یا نه.
جستارهای وابسته
[ویرایش]منابع
[ویرایش]- Wikipedia contributors, "wang tile" , Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/wiki/Wang_tile