אריחי ואנג
אריחי ואנג (באנגלית: Wang tile) אשר הומצאו על ידי הלוגיקאי האו ואנג (Hao Wang) הם סוג של בעיית ריצוף המישור. האריחים הם ריבועים שכל צלע שלהם צבועה בצבע כלשהו, כאשר צלעות שונות של אותו האריח יכולות להיות צבועות בצבעים שונים. כל אריח יכול להיות מוצב רק באוריינטציה המקורית שלו, ולא ניתן לסובב אריחים. הבעיה כוללת כלל פשוט, מותר להניח שני ריבועים זה ליד זה רק אם הצלעות שלהם שנוגעות זו בזו צבועות באותו הצבע.
עיקר העניין באריחי ואנג הוא בשאלה האם קבוצה נתונה של אריחי ואנג יכולה לרצף את המישור (או בהכללה לרצף משטח כלשהו). אריחי ואנג היו ועודם נושא למחקר במדעי המחשב, וכן יש להם שימושים בגרפיקה ממוחשבת.
אריחי ואנג וריצופים לא מחזוריים
בשנת 1961 הלוגיקאי האו ואנג (Hao Wang) עסק בבעיית הדומינו, שהיא בעיית הכרעה, הדורשת לזהות האם אוסף נתון של אריחים יכול לרצף את המישור או לא. ואנג הראה כי ישנו אלגוריתם הפותר בעיה זו, בתנאי שכל אוסף סופי של אריחים המרצף את המישור יכול לרצף אותו בצורה מחזורית. החל משנת 1966 החלו להתגלות אוספים של אריחים שמהווים דוגמאות נגדיות: הם מסוגלים לרצף את המישור רק בצורה לא מחזורית, ואלו נקראים על שמו אריחי ואנג. קרובה לזה בעיית הגרעין, השואלת אם אפשר לרצף את המישור באוסף נתון של אריחים, כשמתחילים מתצורה מסוימת של האריחים.
בשנת 1966 הצליח רוברט ברגר (Robert Berger) למצוא אוסף שמכיל 20,426 אריחי ואנג. בהמשך הצליח ברגר לצמצם את מספר האריחים ל-104, והנס לאוכלי (Hans Läuchli) הצליח להוריד את המספר ל-40. בשנת 1971 הצליח רפאל רובינסון (Raphael M. Robinson) ליצור אוסף אריחי ואנג המכיל רק 6 אריחים. פרט להפרכת השערתו של ואנג, ברגר ורובינסון גם הציגו הוכחה לכך שלא קיים אלגוריתם מהסוג המבוקש - כלומר, בעיית הדומינו היא בעיה לא כריעה. ההוכחה מתבססת על ביצוע סימולציה של ריצת מכונת טיורינג באמצעות אריחי ואנג והתבססות על אי כריעות בעיית העצירה. בכך מודגם שבעיות ריצוף "מסתירות" בתוכן מודל חישובי לא טריוויאלי.
נושא זה זכה לפרסום רב בשנת 1973 כאשר הפיזיקאי רוג'ר פנרוז מצא שלושה סטים של שני אריחים (אמנם לא אריחי ואנג) בלבד שבאמצעותם אפשר לרצף את המישור אך לא בצורה מחזורית. ריצופים אלו, הקרויים 'ריצופי פנרוז' זכו להד נרחב וקשורים לגבישים כמו-מחזוריים. בשנת 1977 פרסם רוברט אמן (Robert Ammann) כמה סטים נוספים.
לקריאה נוספת
- H. Wang, Proving theorems by pattern recognition—II, Bell System Tech. Journal 40(1), 1961, pp. 1–41
- H. Wang, Games, logic and computers, Scientific American, 1965, pp. 98–106
- R. Berger, The undecidability of the domino problem, Memoirs Amer. Math. Soc. 66, 1966
- M. F. Cohen, J. Shade, S. Hiller, and O. Deussen, Wang Tiles for image and texture generation, In ACM SIGGRAPH 2003 Papers, (San Diego, California, July 27–31, 2003), SIGGRAPH '03. ACM Press, New York, NY, 2003, pp. 287–294
- K. Culik, An aperiodic set of 13 Wang tiles, Discrete Mathematics 160, 1996, pp. 245–251.
- J. Kari, A small aperiodic set of Wang tiles, Discrete Mathematics 160, 1996, pp. 259–264.
- K. Culik and J. Kari, An aperiodic set of Wang cubes, Journal of Universal Computer Science 1, 1995, pp. 675–686
- E. Winfree, F. Liu, L.A. Wenzler, and N.C. Seeman, Design and Self-Assembly of Two-Dimensional DNA Crystals, Nature 394, 1998, pp. 539–544.
- P. Lukeman, N. Seeman and A. Mittal, Hybrid PNA/DNA Nanosystems, In 1st International Conference on Nanoscale/Molecular Mechanics (N-M2-I), Outrigger Wailea Resort, Maui, Hawaii, 2002