חוק 30
חוק 30 הוא חוק בינארי חד-ממדי של אוטומט תאי שהוצג על ידי סטיבן וולפרם בשנת 1983.[1] וולפרם תיאר אותו כ"החוק האהוב עלי בכל הזמנים"[2] ופירט עליו בספרו, "A New Kind of Science". לפי שיטת הסיווג של וולפרם, חוק 30 הוא חוק ברמה 3, המציג התנהגות כאוטית.
חוק זה מעורר עניין מיוחד, משום שהוא יוצר דוגמאות מורכבות ואקראיות לכאורה על ידי כללים פשוטים ומוגדרים היטב. לכן, וולפרם מאמין שחוק 30, ואוטומט תאי בכלל, הם המפתח להבנה כיצד חוקים פשוטים יוצרים מבנים והתנהגויות מורכבים בטבע. לדוגמה, דפוס צבע שמייצג חוק 30 מופיע על קונכייתו של מין של חלזון ימי הנקרא חרוטון הטקסטיל. בנוסף, חוק 30 שימש כמחולל מספרים אקראיים בתוכנה שיצר וולפרם, Mathematica, והוצע גם לשימוש כצופן זרם בקריפטוגרפיה. עם זאת, בחינתו של חוק 30 כמייצר מספרים רנדומליים במבחן כי בריבוע הציגה תוצאות ירודות בהשוואה לחוקים אחרים המבוססים על אוטומט תאי.[3]
מערכת כללים
בכל האוטומטים התאיים היסודיים של וולפרם, אינסוף מערכים חד-ממדיים של תַאֵי אוטומט תאי נלקחים בחשבון, כאשר כל תא נמצא במצב התחלתי כלשהו. במרווחי זמן בדידים, כל תא משנה ספונטנית את מצבו, בהתבסס על מצבו הנוכחי ומצבם של שני התאים השכנים לו. עבור חוק 30, מערכת הכללים שקובעת את המצב הבא של האוטומט הם:
| דפוס נוכחי | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|---|
| מצבו החדש של התא האמצעי | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
מבנים ותכונות
הדפוס הבא נוצר ממצב התחלתי שבו תא יחיד במצב "1" (שחור) מוקף בתאים במצב "0" (לבן).
פה, הציר האנכי מייצג זמן (עם הירידה בציר האנכי הזמן עולה) וכל קטע בציר האופקי מייצג את מצבם של כל התאים במערך בנקודת זמן מסוימת במהלך התפתחות הדוגמה. מספר מוטיבים מופיעים במבנה, כמו הופעות תכופות של משולשים לבנים ורצועת דפוס קבועה בצדו השמאלי של המבנה; עם זאת, למבנה כולו אין דפוס שאפשר להבחין בו. מספר התאים השחורים בדור נקבע על ידי הרצף:
- 1, 3, 3, 6, 4, 9, 5, 12, 7, 12, 11, 14, 12, 19, 13, 22, 15, 19, ... (סדרה A070952, באתר OEIS – האנציקלופדיה המקוונת לסדרות של מספרים שלמים)
והוא בערך .
כפי שניתן לראות בתמונה הנ"ל, חוק 30 מייצר לכאורה אקראיות למרות העדר כל דבר שיכול להחשב במידה סבירה כקלט אקראי. סטיבן וולפרם הציע להשתמש בטור האמצעי כמחולל פסבדו אקראי; הוא עבר מבחני רנדומליות סטנדרטיים רבים, ווולפרם השתמש בחוק זה בתוכנה Mathematica ליצירת מספרים שלמים אקראיים. למרות שחוק 30 מייצר אקראיות בדפוסי קלט רבים, יש אינסוף דפוסי קלט שמביאים לדפוסים חוזרים. דוגמה טריוויאלית לדפוס כזה היא דפוס קלט המורכב מ-"0" בלבד. דוגמה טריוויאלית פחות, שמצא מתיו קוק, היא קלט המורכב מאינסוף חזרות על הדפוס '00001000111000', עם חזרות אפשריות שמופרדות על ידי שש "1". דוגמאות נוספות רבות נמצאו על ידי Frans Faase, ראו דפוסים חוזרים בחוק 30.
קישורים חיצוניים
הערות שוליים
- ^ Wolfram, S. (1983). "Statistical mechanics of cellular automata". Rev. Mod. Phys. 55: 601–644. doi:10.1103/RevModPhys.55.601.
- ^ On Starting a Long-Term Company, S. Wolfram, 2005.
- ^ Sipper, Moshe; Tomassini, Marco (1996). "Generating parallel random number generators by cellular programming". International Journal of Modern Physics C. 7 (2): 181–190. doi:10.1142/S012918319600017X.
{{cite journal}}: תחזוקה - ציטוט: multiple names: authors list (link)
23770655חוק 30