אריחי ואנג
אריחי ואנג (באנגלית: 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
