ویکی‌پدیا

پیش‌نویس:کاشی ونگ

این مجموعه 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 نیز تشکیل شوند. [۱۱]

کاربرد

ویرایش

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

چرا که کاشی‌پذیری به راحتی تضمین می‌شود و هر کاشی را می‌توان به صورت تصادفی انتخاب کرد. [۱۲] [۱۳] [۱۴] [۱۵] [۱۶]

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

در فرهنگ عامه

ویرایش

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

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

ویرایش
  • پازل تطبیق لبه

منابع

ویرایش
  1. ↑ Wang, Hao (1961), "Proving theorems by pattern recognition—II", Bell System Technical Journal, 40 (1): 1–41, doi:10.1002/j.1538-7305.1961.tb03975.x. Wang proposes his tiles, and conjectures that there are no aperiodic sets.
  2. ↑ Wang, Hao (November 1965), "Games, logic and computers", Scientific American, 213 (5): 98–106, doi:10.1038/scientificamerican1165-98. Presents the domino problem for a popular audience.
  3. ↑ Renz, Peter (1981), "Mathematical proof: What it is and what it ought to be", The Two-Year College Mathematics Journal, 12 (2): 83–103, doi:10.2307/3027370, JSTOR 3027370.
  4. ↑ ۴٫۰ ۴٫۱ ۴٫۲ Berger, Robert (1966), "The undecidability of the domino problem", Memoirs of the American Mathematical Society, 66: 72, MR 0216954. Berger coins the term "Wang tiles", and demonstrates the first aperiodic set of them. خطای یادکرد: برچسب <ref> نامعتبر؛ نام «berger» چندین بار با محتوای متفاوت تعریف شده است. (صفحهٔ راهنما را مطالعه کنید.).
  5. ↑ Robinson, Raphael M. (1971), "Undecidability and nonperiodicity for tilings of the plane", Inventiones Mathematicae, 12 (3): 177–209, Bibcode:1971InMat..12..177R, doi:10.1007/bf01418780, MR 0297572.
  6. ↑ ۶٫۰ ۶٫۱ Culik, Karel, II (1996), "An aperiodic set of 13 Wang tiles", Discrete Mathematics, 160 (1–3): 245–251, doi:10.1016/S0012-365X(96)00118-5, MR 1417576. (Showed an aperiodic set of 13 tiles with 5 colors.)
  7. ↑ Kari, Jarkko (1996), "A small aperiodic set of Wang tiles", Discrete Mathematics, 160 (1–3): 259–264, doi:10.1016/0012-365X(95)00120-L, MR 1417578.
  8. ↑ ۸٫۰ ۸٫۱ Jeandel, Emmanuel; Rao, Michaël (2021), "An aperiodic set of 11 Wang tiles", Advances in Combinatorics: 1:1–1:37, arXiv:1506.06492, doi:10.19086/aic.18614, MR 4210631. (Showed an aperiodic set of 11 tiles with 4 colors, and proved that fewer tiles or fewer colors cannot be aperiodic.) خطای یادکرد: برچسب <ref> نامعتبر؛ نام «jeandel» چندین بار با محتوای متفاوت تعریف شده است. (صفحهٔ راهنما را مطالعه کنید.).
  9. ↑ Culik, Karel, II; Kari, Jarkko (1995), "An aperiodic set of Wang cubes", Journal of Universal Computer Science, 1 (10): 675–686, doi:10.1007/978-3-642-80350-5_57, MR 1392428.
  10. ↑ Winfree, E.; Liu, F.; Wenzler, L.A.; Seeman, N.C. (1998), "Design and self-assembly of two-dimensional DNA crystals", Nature, 394 (6693): 539–544, Bibcode:1998Natur.394..539W, doi:10.1038/28998, PMID 9707114.
  11. ↑ Lukeman, P.; Seeman, N.; Mittal, A. (2002), "Hybrid PNA/DNA nanosystems", 1st International Conference on Nanoscale/Molecular Mechanics (N-M2-I), Outrigger Wailea Resort, Maui, Hawaii.
  12. ↑ Stam, Jos (1997), Aperiodic Texture Mapping (PDF). Introduces the idea of using Wang tiles for texture variation, with a deterministic substitution system.
  13. ↑ Neyret, Fabrice; Cani, Marie-Paule (1999), "Pattern-Based Texturing Revisited", Proceedings of the 26th annual conference on Computer graphics and interactive techniques - SIGGRAPH '99 (PDF), Los Angeles, United States: ACM, pp. 235–242, doi:10.1145/311535.311561, ISBN 0201485605. Introduces stochastic tiling.
  14. ↑ Cohen, Michael F.; Shade, Jonathan; Hiller, Stefan; Deussen, Oliver (2003), "Wang tiles for image and texture generation", ACM SIGGRAPH 2003 Papers on - SIGGRAPH '03 (PDF), New York, NY, USA: ACM, pp. 287–294, doi:10.1145/1201775.882265, ISBN 1-58113-709-5, archived from the original (PDF) on 2006-03-18.
  15. ↑ Wei, Li-Yi (2004), "Tile-based texture mapping on graphics hardware", Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware (HWWS '04), New York, NY, USA: ACM, pp. 55–63, doi:10.1145/1058129.1058138, ISBN 3-905673-15-0. Applies Wang Tiles for real-time texturing on a GPU.
  16. ↑ . Kopf, Johannes; Cohen-Or, Daniel; Deussen, Oliver; Lischinski, Dani (2006), "Recursive Wang tiles for real-time blue noise", ACM SIGGRAPH 2006 Papers on - SIGGRAPH '06, New York, NY, USA: ACM, pp. 509–518, doi:10.1145/1179352.1141916, ISBN 1-59593-364-6. Shows advanced applications.
  17. ↑ Kari, Jarkko (1990), "Reversibility of 2D cellular automata is undecidable", Cellular automata: theory and experiment (Los Alamos, NM, 1989), Physica D: Nonlinear Phenomena, vol. 45, pp. 379–385, Bibcode:1990PhyD...45..379K, doi:10.1016/0167-2789(90)90195-U, MR 1094882.
  18. ↑ Burnham, Karen (2014), Greg Egan, Modern Masters of Science Fiction, University of Illinois Press, pp. 72–73, ISBN 9780252096297.

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

ویرایش
برگرفته از «https://fa.wikipedia.org/w/index.php?title=پیش‌نویس:کاشی_ونگ&oldid=37398052»